# LeetCode 119: Pascal's Triangle II

## Problem Restatement

We are given an integer:

```python
rowIndex
```

We need to return the row at index `rowIndex` from Pascal's Triangle.

The rows are zero-indexed:

| Index | Row |
|---|---|
| `0` | `[1]` |
| `1` | `[1,1]` |
| `2` | `[1,2,1]` |
| `3` | `[1,3,3,1]` |

The official problem asks for the row at the given index. ([leetcode.com](https://leetcode.com/problems/pascals-triangle-ii/?utm_source=chatgpt.com))

For example:

```python
rowIndex = 3
```

The answer is:

```python
[1, 3, 3, 1]
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `rowIndex` |
| Output | Pascal's Triangle row at that index |
| Indexing | Zero-based |
| Edge values | Always `1` |
| Interior values | Sum of two values above |

The function shape is:

```python
class Solution:
    def getRow(self, rowIndex: int) -> list[int]:
        ...
```

## Examples

For:

```python
rowIndex = 0
```

the answer is:

```python
[1]
```

For:

```python
rowIndex = 1
```

the answer is:

```python
[1, 1]
```

For:

```python
rowIndex = 4
```

the answer is:

```python
[1, 4, 6, 4, 1]
```

because Pascal's Triangle looks like:

```text
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
```

## First Thought: Generate the Whole Triangle

One solution is:

1. Generate all rows up to `rowIndex`.
2. Return the last row.

That works.

But the problem only asks for one row.

We can reduce memory usage by updating a single array in place.

## Key Insight

Each row depends only on the previous row.

Suppose we currently have:

```python
[1, 3, 3, 1]
```

To build the next row:

```python
[1, 4, 6, 4, 1]
```

each interior value comes from:

$$
row[j] = old_row[j-1] + old_row[j]
$$

If we update from left to right, we would overwrite values too early.

So we update from right to left.

That preserves the old values needed for later calculations.

## Algorithm

Initialize:

```python
row = [1]
```

For each row number from `1` to `rowIndex`:

1. Append `1` to the row.
2. Update interior values from right to left.

For each interior index `j`:

$$
row[j] = row[j] + row[j-1]
$$

Finally, return `row`.

## Correctness

The algorithm maintains the invariant that `row` always stores the current row of Pascal's Triangle.

Initially:

```python
[1]
```

is the correct row `0`.

For each iteration, a new trailing `1` is appended, which correctly matches the last value of every Pascal row.

The interior values are then updated from right to left. At position `j`, before the update:

- `row[j]` still contains the old value from the previous row.
- `row[j-1]` also still contains the old previous-row value because right-to-left iteration has not modified it yet.

Thus:

$$
row[j] = old_row[j] + old_row[j-1]
$$

which is exactly Pascal's Triangle recurrence rule.

Since every iteration correctly transforms the current row into the next row, after processing up to `rowIndex`, the array contains exactly the desired row.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(rowIndex^2)` | Every Pascal value up to the target row is computed |
| Space | `O(rowIndex)` | Only one row array is stored |

## Implementation

```python
class Solution:
    def getRow(self, rowIndex: int) -> list[int]:
        row = [1]

        for i in range(1, rowIndex + 1):
            row.append(1)

            for j in range(i - 1, 0, -1):
                row[j] = row[j] + row[j - 1]

        return row
```

## Code Explanation

Start with the first row:

```python
row = [1]
```

Each iteration builds the next Pascal row:

```python
for i in range(1, rowIndex + 1):
```

Every row ends with `1`:

```python
row.append(1)
```

Now update interior values from right to left:

```python
for j in range(i - 1, 0, -1):
```

Compute the Pascal recurrence:

```python
row[j] = row[j] + row[j - 1]
```

Right-to-left order preserves old values correctly.

Finally:

```python
return row
```

## Testing

```python
class Solution:
    def getRow(self, rowIndex: int) -> list[int]:
        row = [1]

        for i in range(1, rowIndex + 1):
            row.append(1)

            for j in range(i - 1, 0, -1):
                row[j] = row[j] + row[j - 1]

        return row

def run_tests():
    s = Solution()

    assert s.getRow(0) == [1]

    assert s.getRow(1) == [1, 1]

    assert s.getRow(2) == [1, 2, 1]

    assert s.getRow(3) == [1, 3, 3, 1]

    assert s.getRow(4) == [1, 4, 6, 4, 1]

    assert s.getRow(5) == [1, 5, 10, 10, 5, 1]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `0` | Minimum valid row |
| `1` | Small base case |
| `2` | First interior computation |
| `3` | Standard Pascal row |
| `4` | Larger coefficients |
| `5` | Confirms repeated in-place updates |