LeetCode 119: Pascal's Triangle II

Problem Restatement

We are given an integer:

rowIndex

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

The rows are zero-indexed:

The official problem asks for the row at the given index. (leetcode.com)

For example:

rowIndex = 3

The answer is:

[1, 3, 3, 1]

Input and Output

The function shape is:

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

Examples

For:

rowIndex = 0

the answer is:

[1]

For:

rowIndex = 1

the answer is:

[1, 1]

For:

rowIndex = 4

the answer is:

[1, 4, 6, 4, 1]

because Pascal’s Triangle looks like:

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

[1, 3, 3, 1]

To build the next row:

[1, 4, 6, 4, 1]

each interior value comes from:

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:

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:

Finally, return row.

Correctness

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

Initially:

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

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

Implementation

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:

row = [1]

Each iteration builds the next Pascal row:

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

Every row ends with 1:

row.append(1)

Now update interior values from right to left:

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

Compute the Pascal recurrence:

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

Right-to-left order preserves old values correctly.

Finally:

return row

Testing

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: