# Leetcode 118. Pascal’s Triangle

# 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:

# 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

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