Leetcode 118. Pascal’s Triangle

Accepted Code

Problem Statement

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:

Took from Leetcode.com

Test Cases

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

Approach

This is a pretty straight forward approach. We can just apply the logic for the Pascal’s triangle. ie each number is the sum of the two numbers directly above.

We start with the very top row with value 1. Then for the next row, it will be sum of two numbers directly above. We have only just 1 above. So the next row will be 1 1.
For the next row, we start with 1 at the very edge. Then sum of 2 numbers, ie 1 1 which is directly above which will be 2. Then 1 on the other edge.
So one thing is pretty sure, on the two boundaries we have 1’s and in between we just take 2 numbers from the previous row, or directly from above.

Algorithm

1. Initialise an empty list and add 1 to it. Add this list to the result list.
2. Start traversing from i = 1 to numRows given as input.
3. Create a new list, say current and add to 1. Note : On both end we have 1.
4. Take the previous row, which can be obtained as list.get(i — 1).
5. Traverse from j=1 to i and calculate the sum of 2 numbers from the above which we calculated on step 3.
6. Add this sum to a new list, which is current.
7. Finally add one more 1 to the current list as we know both the ends we have 1.
8. Add this current to the result list as we are done with the current row.
9. Return the result list.

Time and Space Complexity

We are traversing 2 times at a time via loop, so the time complexity will be O(numRow²).

Space complexity will be O(numRow) as we are storing that many amount of rows.

Note : please correct me if I made any mistake. Thank you.

Code

Java Code

LeetCodeTopInterviewQuestions/19_Pascals_Triangle.java at master ·…