LeetCode Pascal’s Triangle Solution

Given an integer numRows, return the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[1]]

Constraints:

• 1 <= numRows <= 30

Solution

In order to understand the problem I looked at the animated picture above which gave me a clearer view of what is Pascal’s triangle. Indeed, a picture is worth thousand words. 🙂

Once I understood what is a Pascal triangle, it is where each number is sum of two numbers above it, I started thinking of the algorithm for generating rows. We would go from top to bottom. First row will have just one element valued 1. Now image that first row has 3 elements instead of one, first element is NULL (imagine it has value 0), second element is 1, third element is again NULL (imagine it with value 0). Now in order to derive values of next row, you add these 3 elements in pairs of two.

NULL + 1 = 1

1 + 1 = 2

1 + NULL = 1

So your next row will have elements 1,2,1. Imagine again that this row has NULL elements in front and back. So it can be thought as NULL, 1, 2, 1, NULL.

So to derive next row you simple add adjacent numbers

NULL + 1 = 1

1 + 2 = 3

2 + 1 = 3

1 + NULL = 1

So the row will be 1,3,3,1. We can keep doing this and keep adding these lists into a List of List of Integers till we do this for N times. That should be our answer.

Below is Java code implementation for the same.

 public List<List<Integer>> generate(int numRows) {
       List<List<Integer>> rowList = new ArrayList<>();
       List<Integer> row1 = new ArrayList<>();
       row1.add(1);
       rowList.add(row1);
       int n = 1; 
       while (n<numRows) {
          List<Integer> lastRow = rowList.get(rowList.size()-1);
          List<Integer> currentRow = new ArrayList<>();
          currentRow.add(1); 
          for (int i=0; i<lastRow.size()-1; i++) {
              int currentNum = lastRow.get(i);
              int nextNum = lastRow.get(i+1);
              currentRow.add(currentNum+nextNum);
          }
          currentRow.add(1);
          rowList.add(currentRow);
          n++; 
       }
       return rowList; 
         
    }

And below is how fast it is. As you can see this is the fastest solution submitted ever on LeetCode. 🙂

If you can solve the problem in your mind, you can solve the problem with code. For these kind of problems see how you can derive smaller rows (Row 1 from Row 0, Row 2 from Row 1 and so on). And then you can apply same logic to derive rows of any length and eventually reach the solution.