# LeetCode 118: Pascal's Triangle

## Problem Restatement

We are given an integer:

```python
numRows
```

We need to generate the first `numRows` rows of Pascal's Triangle.

In Pascal's Triangle:

- The first and last number of every row are `1`.
- Every interior value equals the sum of the two numbers directly above it.

The official problem asks us to return the first `numRows` rows. ([leetcode.com](https://leetcode.com/problems/pascals-triangle/?utm_source=chatgpt.com))

For example:

```python
numRows = 5
```

The output is:

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

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `numRows` |
| Output | First `numRows` rows of Pascal's Triangle |
| Edge values | Always `1` |
| Interior values | Sum of two values above |

The function shape is:

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

## Examples

For:

```python
numRows = 1
```

the triangle is:

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

For:

```python
numRows = 5
```

the rows are built step by step.

Row `0`:

```python
[1]
```

Row `1`:

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

Row `2`:

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

because:

```python
2 = 1 + 1
```

Row `3`:

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

because:

```python
3 = 1 + 2
3 = 2 + 1
```

## First Thought: Build Rows One by One

Each row depends only on the previous row.

So instead of computing combinations directly, we can generate rows incrementally.

For every new row:

- Start with `1`.
- Compute interior values using the previous row.
- End with `1`.

This naturally forms a dynamic programming process.

## Key Insight

Suppose the previous row is:

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

The next row starts and ends with `1`:

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

Each interior value comes from the two values above:

```python
1 + 3 = 4
3 + 3 = 6
3 + 1 = 4
```

So the next row becomes:

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

The rule is:

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

for interior positions.

## Algorithm

Initialize:

```python
ans = []
```

For each row index `i`:

1. Create a row filled with `1`s of length `i + 1`.
2. For every interior position:
   1. Compute the sum of the two values above.
3. Append the row to the answer.

Return the completed triangle.

## Correctness

The algorithm builds the triangle row by row.

Each row begins and ends with `1`, which matches the definition of Pascal's Triangle.

For every interior position `j`, the algorithm computes:

$$
ans[i-1][j-1] + ans[i-1][j]
$$

These are exactly the two numbers directly above the current position in Pascal's Triangle.

Therefore, every interior value is correct.

Since each row is built from the previous row using the Pascal recurrence rule, every generated row matches Pascal's Triangle exactly.

Thus, after `numRows` iterations, the algorithm correctly returns the first `numRows` rows.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(numRows^2)` | Every triangle value is computed once |
| Space | `O(numRows^2)` | The output stores all rows |

The output itself contains:

$$
1 + 2 + 3 + ... + numRows
$$

values.

## Implementation

```python
class Solution:
    def generate(self, numRows: int) -> list[list[int]]:
        ans = []

        for i in range(numRows):
            row = [1] * (i + 1)

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

            ans.append(row)

        return ans
```

## Code Explanation

The answer list stores all rows:

```python
ans = []
```

Each row has length:

```python
i + 1
```

Create the row initially filled with `1`s:

```python
row = [1] * (i + 1)
```

The first and last values remain `1`.

Now compute interior values:

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

Use the previous row:

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

Append the completed row:

```python
ans.append(row)
```

Finally:

```python
return ans
```

## Testing

```python
class Solution:
    def generate(self, numRows: int) -> list[list[int]]:
        ans = []

        for i in range(numRows):
            row = [1] * (i + 1)

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

            ans.append(row)

        return ans

def run_tests():
    s = Solution()

    assert s.generate(1) == [
        [1]
    ]

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

    assert s.generate(5) == [
        [1],
        [1, 1],
        [1, 2, 1],
        [1, 3, 3, 1],
        [1, 4, 6, 4, 1],
    ]

    assert s.generate(6) == [
        [1],
        [1, 1],
        [1, 2, 1],
        [1, 3, 3, 1],
        [1, 4, 6, 4, 1],
        [1, 5, 10, 10, 5, 1],
    ]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `numRows = 1` | Minimum valid triangle |
| `numRows = 2` | Small base structure |
| `numRows = 5` | Standard example |
| `numRows = 6` | Confirms larger row generation |