# Pascal's Triangle
**Difficulty:** EASY
[External](https://leetcode.com/problems/pascals-triangle)
Canonical: https://scaleengineer.com/dsa/problems/pascal's-triangle
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Cisco](https://scaleengineer.com/companies/cisco), [Deloitte](https://scaleengineer.com/companies/deloitte), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Google](https://scaleengineer.com/companies/google), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Oracle](https://scaleengineer.com/companies/oracle), [Uber](https://scaleengineer.com/companies/uber), [Wix](https://scaleengineer.com/companies/wix), [Yahoo](https://scaleengineer.com/companies/yahoo), [tcs](https://scaleengineer.com/companies/tcs), [Virtusa](https://scaleengineer.com/companies/virtusa), [Mitsogo](https://scaleengineer.com/companies/mitsogo), [X](https://scaleengineer.com/companies/x), [HSBC](https://scaleengineer.com/companies/hsbc)
---
## Problem
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:

![](https://assets.glich.co/dsa/pascal's-triangle/image0.gif) 

**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`

# Approaches
## Brute Force using Recursion
This approach directly translates the mathematical definition of Pascal's Triangle into a recursive function. Each element `T(i, j)` is calculated by the recursive formula `T(i, j) = T(i-1, j-1) + T(i-1, j)`. The base cases are the edges of the triangle, where `T(i, 0) = 1` and `T(i, i) = 1`.
**Time:** O(2^numRows) · **Space:** O(numRows^2)
**Pros:** Simple to understand as it directly follows the mathematical definition.
**Cons:** Extremely inefficient due to massive redundant computations.; Will likely result in a 'Time Limit Exceeded' error for larger inputs.
### Explanation
We define a helper function, say `getValue(row, col)`, that computes the value at a specific position in the triangle. The main function iterates from `row = 0` to `numRows - 1`. For each `row`, it iterates from `col = 0` to `row`. In the inner loop, it calls `getValue(row, col)` to compute the element and adds it to the current row's list.

The `getValue(row, col)` function works as follows: if `col` is 0 or `col` is equal to `row`, it returns 1 (base case). Otherwise, it makes two recursive calls: `getValue(row - 1, col - 1)` and `getValue(row - 1, col)`, and returns their sum.

This method is straightforward but highly inefficient because it re-computes the same values multiple times. For instance, calculating `T(5, 2)` requires `T(4, 1)` and `T(4, 2)`, and both of these require `T(3, 1)`, leading to redundant calculations.

```java
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> triangle = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                row.add(computeValue(i, j));
            }
            triangle.add(row);
        }
        return triangle;
    }

    private int computeValue(int row, int col) {
        if (col == 0 || col == row) {
            return 1;
        }
        return computeValue(row - 1, col - 1) + computeValue(row - 1, col);
    }
}
```
### Algorithm
*   Create a main list `triangle` to store the result.
*   Loop for `i` from 0 to `numRows - 1`:
    *   Create a new list `currentRow`.
    *   Loop for `j` from 0 to `i`:
        *   Calculate the value at `(i, j)` using a recursive helper function `computeValue(i, j)`.
        *   Add the value to `currentRow`.
    *   Add `currentRow` to `triangle`.
*   Return `triangle`.

**Helper function `computeValue(row, col)`:**
*   If `col == 0` or `col == row`, return 1.
*   Return `computeValue(row - 1, col - 1) + computeValue(row - 1, col)`.

## Dynamic Programming
This is the most efficient and standard approach. It builds the triangle row by row, using the previously generated row to compute the current row. This avoids the redundant calculations of the recursive approach by storing and reusing intermediate results.
**Time:** O(numRows^2) · **Space:** O(numRows^2)
**Pros:** Efficient and easy to implement.; Avoids re-computation by building upon previous results.
**Cons:** Requires space to store the entire triangle, which is proportional to numRows^2.
### Explanation
We initialize the result list, `triangle`, and add the first row, `[1]`. We then iterate from the second row (`i = 1`) up to `numRows - 1`. In each iteration, we get a reference to the previous row (`prevRow`). We create a new list for the current row (`currentRow`).

The first element of any row is always 1, so we add it to `currentRow`. Next, we iterate through the elements of `prevRow` from the first to the second-to-last element. For each position `j` in the current row (from 1 to `i-1`), the value is the sum of the elements at indices `j-1` and `j` of the `prevRow`. The last element of any row is also always 1, so we add it to `currentRow`. Finally, we add the fully constructed `currentRow` to our `triangle`. This process continues until all `numRows` have been generated.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> triangle = new ArrayList<>();

        if (numRows == 0) {
            return triangle;
        }

        // First row
        List<Integer> firstRow = new ArrayList<>();
        firstRow.add(1);
        triangle.add(firstRow);

        for (int i = 1; i < numRows; i++) {
            List<Integer> prevRow = triangle.get(i - 1);
            List<Integer> currentRow = new ArrayList<>();

            // First element of each row is 1
            currentRow.add(1);

            // Each triangle element (other than the first and last of each row)
            // is generated by adding the two elements above it.
            for (int j = 1; j < i; j++) {
                currentRow.add(prevRow.get(j - 1) + prevRow.get(j));
            }

            // Last element of each row is 1
            currentRow.add(1);

            triangle.add(currentRow);
        }

        return triangle;
    }
}
```
### Algorithm
*   Initialize an empty list of lists, `triangle`.
*   If `numRows` is 0, return `triangle`.
*   Create the first row `[1]` and add it to `triangle`.
*   Loop for `i` from 1 to `numRows - 1`:
    *   Get the previous row: `prevRow = triangle.get(i - 1)`.
    *   Create a new list `currentRow`.
    *   Add 1 to `currentRow`.
    *   Loop for `j` from 1 to `i - 1`:
        *   Calculate `sum = prevRow.get(j - 1) + prevRow.get(j)`.
        *   Add `sum` to `currentRow`.
    *   Add 1 to `currentRow`.
    *   Add `currentRow` to `triangle`.
*   Return `triangle`.

# Solutions
### Java

```java
class Solution { public List < List < Integer >> generate ( int numRows ) { List < List < Integer >> f = new ArrayList <>(); f . add ( List . of ( 1 )); for ( int i = 0 ; i < numRows - 1 ; ++ i ) { List < Integer > g = new ArrayList <>(); g . add ( 1 ); for ( int j = 0 ; j < f . get ( i ). size () - 1 ; ++ j ) { g . add ( f . get ( i ). get ( j ) + f . get ( i ). get ( j + 1 )); } g . add ( 1 ); f . add ( g ); } return f ; } }
```

### JavaScript

```javascript
/** * @param {number} numRows * @return {number[][]} */ var generate =
  function (numRows) {
    const f = [[1]];
    for (let i = 0; i < numRows - 1; ++i) {
      const g = [1];
      for (let j = 0; j < f[i].length - 1; ++j) {
        g.push(f[i][j] + f[i][j + 1]);
      }
      g.push(1);
      f.push(g);
    }
    return f;
  };

```

### CPP

```cpp
class Solution { public: vector < vector < int >> generate ( int numRows ) { vector < vector < int >> f ; f . push_back ( vector < int > ( 1 , 1 )); for ( int i = 0 ; i < numRows - 1 ; ++ i ) { vector < int > g ; g . push_back ( 1 ); for ( int j = 0 ; j < f [ i ]. size () - 1 ; ++ j ) { g . push_back ( f [ i ][ j ] + f [ i ][ j + 1 ]); } g . push_back ( 1 ); f . push_back ( g ); } return f ; } };
```

### Python

```python
class Solution : def generate ( self , numRows : int ) -> List [ List [ int ]]: f = [[ 1 ]] for i in range ( numRows - 1 ): g = [ 1 ] + [ a + b for a , b in pairwise ( f [ - 1 ])] + [ 1 ] f . append ( g ) return f
```