Coding

LeetCode Pascal’s Triangle Solution

0
(0)

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. 🙂

Lessons Learnt

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.

How useful was this post?

Click on a star to rate it!

Average rating 0 / 5. Vote count: 0

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

0 0 votes
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments