# Pascal's Triangle II
**Difficulty:** EASY
[External](https://leetcode.com/problems/pascals-triangle-ii)
Canonical: https://scaleengineer.com/dsa/problems/pascal's-triangle-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Yahoo](https://scaleengineer.com/companies/yahoo)
---
## Problem
Given an integer `rowIndex`, return the `rowIndexth` (**0-indexed**) row of the **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-ii/image0.gif) 

**Example 1:**

**Input:** rowIndex = 3
**Output:** [1,3,3,1]

**Example 2:**

**Input:** rowIndex = 0
**Output:** [1]

**Example 3:**

**Input:** rowIndex = 1
**Output:** [1,1]

**Constraints:**

* `0 <= rowIndex <= 33`

**Follow up:** Could you optimize your algorithm to use only `O(rowIndex)` extra space?

# Approaches
## Brute-Force Recursion
This approach directly translates the recursive definition of Pascal's Triangle, `C(n, k) = C(n-1, k-1) + C(n-1, k)`, into a recursive function. To get the entire `rowIndex`-th row, we call this function for each column index from 0 to `rowIndex`.
**Time:** O(2^rowIndex) · **Space:** O(rowIndex)
**Pros:** Simple to understand as it directly models the mathematical definition of Pascal's Triangle.
**Cons:** Extremely inefficient due to a massive number of redundant computations.; Will likely result in a 'Time Limit Exceeded' error for even moderately large values of `rowIndex`.
### Explanation
We define a recursive function, say `pascalValue(row, col)`, which computes the value at a specific position in the triangle.
The base cases for the recursion are when `col == 0` or `col == row`, in which case the value is 1.
For any other position `(row, col)`, the value is the sum of `pascalValue(row - 1, col - 1)` and `pascalValue(row - 1, col)`.
To generate the final result, we create a list and iterate from `k = 0` to `rowIndex`, populating the list with the results of `pascalValue(rowIndex, k)`.
This method is highly inefficient because it recomputes the same values multiple times. For example, calculating the value at `(5, 2)` and `(5, 3)` both require computing the value at `(4, 2)`, leading to an exponential number of overlapping subproblems.

```java
class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<>();
        for (int k = 0; k <= rowIndex; k++) {
            row.add(pascalValue(rowIndex, k));
        }
        return row;
    }

    private int pascalValue(int row, int col) {
        if (col == 0 || col == row) {
            return 1;
        }
        // Recursive step
        return pascalValue(row - 1, col - 1) + pascalValue(row - 1, col);
    }
}
```
### Algorithm
1. Create an empty list `result` to store the row.
2. Loop with an index `k` from `0` to `rowIndex`.
3. In each iteration, call a recursive helper function, `pascalValue(rowIndex, k)`, to compute the element at that position.
4. Add the value returned by the helper function to the `result` list.
5. The `pascalValue(row, col)` helper function is defined as follows:
   - **Base Case:** If `col` is `0` or `col` is equal to `row`, return `1`.
   - **Recursive Step:** Otherwise, return the sum of `pascalValue(row - 1, col - 1)` and `pascalValue(row - 1, col)`.

## Dynamic Programming with Full Triangle
This approach builds the entire Pascal's Triangle row by row, up to the desired `rowIndex`. It stores all the generated rows in a list of lists and finally returns the last one.
**Time:** O(rowIndex^2) · **Space:** O(rowIndex^2)
**Pros:** Avoids redundant calculations present in the recursive approach.; Conceptually straightforward to implement.
**Cons:** Uses excessive space by storing all rows of the triangle, which is not necessary for this problem.
### Explanation
Instead of recomputing values, we can use dynamic programming. We build the triangle from the top down. We start by creating the first row `[1]`. Then, for each subsequent row `i`, we generate its elements using the values from the previously computed row `i-1`. The `j`-th element of row `i` is the sum of the `(j-1)`-th and `j`-th elements of row `i-1`. We store all these rows in a list of lists. While this is much more efficient than the recursive approach, it uses more space than required.

```java
class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<List<Integer>> triangle = new ArrayList<>();
        
        // First row
        triangle.add(new ArrayList<>());
        triangle.get(0).add(1);
        
        for (int i = 1; i <= rowIndex; i++) {
            List<Integer> row = new ArrayList<>();
            List<Integer> prevRow = triangle.get(i - 1);
            
            row.add(1); // First element of each row is 1
            
            for (int j = 1; j < i; j++) {
                row.add(prevRow.get(j - 1) + prevRow.get(j));
            }
            
            row.add(1); // Last element of each row is 1
            triangle.add(row);
        }
        
        return triangle.get(rowIndex);
    }
}
```
### Algorithm
1. Initialize a list of lists, `triangle`.
2. Add the first row, `[1]`, to `triangle`.
3. Loop with an index `i` from `1` to `rowIndex`.
   - In each iteration, get the previous row `prevRow` from `triangle.get(i-1)`.
   - Create a new list `currentRow`.
   - Add `1` as the first element of `currentRow`.
   - Loop with an index `j` from `1` to `i-1`.
     - Calculate the sum `prevRow.get(j-1) + prevRow.get(j)` and add it to `currentRow`.
   - Add `1` as the last element of `currentRow`.
   - Add `currentRow` to the `triangle`.
4. After the loops complete, return the list at index `rowIndex` from `triangle`.

## Space-Optimized Dynamic Programming
This approach improves upon the previous DP method by realizing that to compute the current row, we only need the previous row. This allows us to reduce the space complexity significantly by using only a single list and updating it in-place.
**Time:** O(rowIndex^2) · **Space:** O(rowIndex)
**Pros:** Very space-efficient, using only `O(rowIndex)` extra space, which satisfies the follow-up question.; Maintains the simplicity of the DP approach.
**Cons:** The time complexity is still quadratic, which is not optimal.
### Explanation
We can optimize the space complexity of the DP approach to `O(rowIndex)`. We only need to store one row at a time. To compute the next row, we can modify the current row in-place. The key insight is to perform the updates from right to left. If we update from left to right, we would overwrite values that are still needed for subsequent calculations in the same row. By iterating backwards, we use the 'old' values from the previous row's computation before they are updated.

For each new row `i`, we first conceptually have the `(i-1)`-th row. The `i`-th row will have one more element. We can add a `1` at the end and then update the values from right to left.

```java
class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<>();
        row.add(1); // Corresponds to row 0

        for (int i = 1; i <= rowIndex; i++) {
            // Update existing elements from right to left
            for (int j = i - 1; j > 0; j--) {
                row.set(j, row.get(j) + row.get(j - 1));
            }
            // Add the last element for the new row
            row.add(1);
        }
        return row;
    }
}
```
### Algorithm
1. Initialize a list `row` with the first element `1`.
2. Loop with an index `i` from `1` to `rowIndex`. This outer loop corresponds to building each row from 1 to `rowIndex`.
3. Inside the loop, iterate backwards from `j = i - 1` down to `1`.
   - Update the element at index `j` by adding the element at `j-1` to it: `row.set(j, row.get(j) + row.get(j-1))`.
4. After the inner loop, append a `1` to the end of the list `row`. This completes the `i`-th row.
5. After the outer loop finishes, `row` will hold the `rowIndex`-th row of Pascal's triangle.

## Mathematical Formula using Binomial Coefficients
This is the most efficient approach. It leverages the mathematical formula for Pascal's Triangle elements. The element at row `n` and column `k` is the binomial coefficient `C(n, k)`. We can calculate each element of the row iteratively in a single pass.
**Time:** O(rowIndex) · **Space:** O(rowIndex)
**Pros:** Optimal time complexity of `O(rowIndex)`.; Optimal space complexity of `O(rowIndex)` (required for the output).
**Cons:** Requires knowledge of the mathematical properties of binomial coefficients.; Care must be taken to use a `long` for intermediate calculations to prevent overflow, even if the final result fits in an `int`.
### Explanation
The `k`-th element (0-indexed) of the `n`-th row is given by the binomial coefficient `C(n, k)`. Instead of calculating factorials, which can lead to overflow, we can use the multiplicative formula which relates adjacent coefficients: `C(n, k) = C(n, k-1) * (n - k + 1) / k`.

We can generate the entire `rowIndex`-th row in a single pass. We start with the first element, `C(rowIndex, 0)`, which is 1. Then, we loop from `k = 1` to `rowIndex`, calculating each subsequent element using the value of the previous element and the formula above. This avoids nested loops and results in a linear time complexity.

```java
class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<>(rowIndex + 1);
        long val = 1;
        
        for (int k = 0; k <= rowIndex; k++) {
            row.add((int) val);
            // Calculate the next value in the row
            // C(n, k+1) = C(n, k) * (n-k) / (k+1)
            val = val * (rowIndex - k) / (k + 1);
        }
        
        return row;
    }
}
```
### Algorithm
1. Create an empty list `row`.
2. Initialize a `long` variable `val = 1`. This will hold the current coefficient value.
3. Loop with an index `k` from `0` to `rowIndex`.
   - Add the current `val` (cast to an `int`) to the `row` list.
   - Update `val` for the next iteration using the formula: `val = val * (rowIndex - k) / (k + 1)`.
4. Return the `row` list.

# Solutions
### Java

```java
class Solution {
public
  List<Integer> getRow(int rowIndex) {
    List<Integer> f = new ArrayList<>();
    for (int i = 0; i < rowIndex + 1; ++i) {
      f.add(1);
    }
    for (int i = 2; i < rowIndex + 1; ++i) {
      for (int j = i - 1; j > 0; --j) {
        f.set(j, f.get(j) + f.get(j - 1));
      }
    }
    return f;
  }
}

```

### JavaScript

```javascript
/** * @param {number} rowIndex * @return {number[]} */ var getRow = function (
  rowIndex,
) {
  const f = Array(rowIndex + 1).fill(1);
  for (let i = 2; i < rowIndex + 1; ++i) {
    for (let j = i - 1; j; --j) {
      f[j] += f[j - 1];
    }
  }
  return f;
};

```

### CPP

```cpp
class Solution {
public:
  vector<int> getRow(int rowIndex) {
    vector<int> f(rowIndex + 1, 1);
    for (int i = 2; i < rowIndex + 1; ++i) {
      for (int j = i - 1; j; --j) {
        f[j] += f[j - 1];
      }
    }
    return f;
  }
};

```

### Python

```python
class Solution:
    def getRow(self, rowIndex: int) -> List[int]: f = [1] * (rowIndex + 1) for i in range(2, rowIndex + 1): for j in range(i - 1, 0, - 1): f[j] += f[j - 1] return f

```