LeetCode Problem 119

Difficulty: 🟢 Easy
Topics: Array, Dynamic Programming

Solution

LeetCode 119, Pascal's Triangle II

Problem Understanding

This problem asks us to return a specific row from Pascal's Triangle. The input, rowIndex, represents the zero-based index of the row we want to generate.

Pascal's Triangle is a triangular arrangement of numbers where:

• The first and last number in every row is always 1
• Every interior number is the sum of the two numbers directly above it

For example, the first few rows are:

Row 0: [1]
Row 1: [1, 1]
Row 2: [1, 2, 1]
Row 3: [1, 3, 3, 1]
Row 4: [1, 4, 6, 4, 1]

If the input is 3, we return the fourth row, [1,3,3,1], because the indexing starts at 0.

The constraint 0 <= rowIndex <= 33 tells us the input size is relatively small. Even less efficient approaches will work within these bounds. However, the follow up specifically asks us to optimize space usage to O(rowIndex), which means we should avoid storing the entire triangle if possible.

There are several important edge cases to consider:

• rowIndex = 0, the smallest possible input, should return [1]
• rowIndex = 1, the first row with two elements, should return [1,1]
• Larger rows require careful updating because overwriting values too early can corrupt later calculations
• Since Pascal's Triangle values grow quickly, we must ensure the implementation handles larger intermediate values correctly, although the problem guarantees all results fit comfortably within standard integer ranges for the given constraints

Approaches

Brute Force Approach

The most direct solution is to build the entire Pascal's Triangle from row 0 up to rowIndex, then return the final row.

We start with the first row [1]. For each new row, we create a new array whose first and last elements are 1. Every middle element is computed as the sum of two adjacent values from the previous row.

This approach is correct because Pascal's Triangle is defined recursively. Every row depends entirely on the row before it, so constructing rows one by one guarantees correctness.

However, this method stores all rows even though we only need the final one. That leads to unnecessary memory usage.

Optimal Approach

The key observation is that each row only depends on the previous row. We do not need to store the entire triangle.

Instead, we can maintain a single array representing the current row and update it in place.

The important detail is update order. If we update from left to right, we overwrite values that are still needed for future calculations. To avoid this, we update from right to left.

For example:

Current row: [1, 3, 3, 1]
Next update:
index 3 = 3 + 1
index 2 = 3 + 3
index 1 = 1 + 3

By updating backward, we preserve the previous row values until they are no longer needed.

This achieves the follow up requirement of O(rowIndex) extra space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(rowIndex²)	O(rowIndex²)	Builds the entire triangle
Optimal	O(rowIndex²)	O(rowIndex)	Uses one array updated in place

Algorithm Walkthrough

1. Initialize the result array with the first row of Pascal's Triangle.

row = [1]

This represents row 0. 2. Iterate from row 1 up to rowIndex.

For each new row, append a 1 to the end of the array because every row in Pascal's Triangle ends with 1. 3. Update the interior elements from right to left.

For each index j from i - 1 down to 1:

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

We go backward so that values from the previous row are not overwritten before they are used. 4. Continue until the desired row is fully constructed. 5. Return the final array.

Why it works

The algorithm maintains the invariant that after iteration i, the array row exactly represents the i-th row of Pascal's Triangle.

Each interior element in Pascal's Triangle is defined as the sum of the two elements above it. By updating from right to left, we ensure that both required values still belong to the previous row at the moment of calculation. Therefore, every update produces the correct next-row value.

Python Solution

from typing import List

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

The implementation begins by initializing the first row as [1].

The outer loop generates rows one at a time until reaching the target row. During each iteration, a new 1 is appended because every Pascal's Triangle row ends with 1.

The inner loop updates interior values from right to left. This backward traversal is critical because it prevents overwriting values that are still needed for subsequent calculations.

Finally, once all rows have been processed, the function returns the resulting array.

Go Solution

func getRow(rowIndex int) []int {
    row := []int{1}

    for i := 1; i <= rowIndex; i++ {
        row = append(row, 1)

        for j := i - 1; j >= 1; j-- {
            row[j] = row[j] + row[j-1]
        }
    }

    return row
}

The Go implementation follows the same logic as the Python version.

Slices in Go behave similarly to dynamic arrays, making them a natural fit for this problem. The append function is used to add the trailing 1 for each row.

Go uses explicit indexing and loop syntax, but otherwise the algorithm remains identical. Since the maximum row index is only 33, integer overflow is not a concern when using Go's standard int type.

Worked Examples

Example 1

Input: rowIndex = 3

Initial state:

Step	row
Start	[1]

Build row 1:

• Append 1
• No interior updates needed

Step	row
After row 1	[1, 1]

Build row 2:

• Append 1
• Update index 1

row[1] = 1 + 1 = 2

Step	row
After row 2	[1, 2, 1]

Build row 3:

• Append 1
• Update index 2

row[2] = 1 + 2 = 3

• Update index 1

row[1] = 2 + 1 = 3

Step	row
After row 3	[1, 3, 3, 1]

Final output:

[1, 3, 3, 1]

Example 2

Input: rowIndex = 0

Initial row already represents row 0.

Step	row
Start	[1]

Final output:

[1]

Example 3

Input: rowIndex = 1

Initial state:

Step	row
Start	[1]

Build row 1:

• Append 1

Step	row
After row 1	[1, 1]

Final output:

[1, 1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(rowIndex²)	Each row updates up to its length
Space	O(rowIndex)	Only one row is stored

The outer loop runs rowIndex times. For each row, the inner loop may process nearly all existing elements. This creates a triangular number of operations:

1 + 2 + 3 + ... + rowIndex

This sums to O(rowIndex²).

The algorithm stores only the current row, whose maximum size is rowIndex + 1, so the space complexity is O(rowIndex).

Test Cases

from typing import List

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

solution = Solution()

assert solution.getRow(0) == [1]  # smallest valid input
assert solution.getRow(1) == [1, 1]  # first non-trivial row
assert solution.getRow(2) == [1, 2, 1]  # simple interior calculation
assert solution.getRow(3) == [1, 3, 3, 1]  # provided example
assert solution.getRow(4) == [1, 4, 6, 4, 1]  # multiple interior updates
assert solution.getRow(5) == [1, 5, 10, 10, 5, 1]  # symmetric larger row
assert solution.getRow(6) == [1, 6, 15, 20, 15, 6, 1]  # deeper Pascal structure
assert solution.getRow(10) == [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1]  # larger values
assert solution.getRow(33)[0] == 1  # boundary constraint start
assert solution.getRow(33)[-1] == 1  # boundary constraint end
assert len(solution.getRow(33)) == 34  # row length property

Test	Why
rowIndex = 0	Validates smallest possible input
rowIndex = 1	Ensures basic two-element row works
rowIndex = 2	Verifies first interior computation
rowIndex = 3	Matches provided example
rowIndex = 4	Tests multiple updates in one row
rowIndex = 5	Confirms symmetry property
rowIndex = 6	Validates deeper recursive construction
rowIndex = 10	Tests larger combinational values
rowIndex = 33	Verifies upper constraint handling

Edge Cases

Edge Case 1, rowIndex = 0

This is the smallest valid input and can easily expose off-by-one errors. A naive implementation that assumes at least one iteration may fail here.

The implementation handles this correctly because the array starts as [1], which already represents row 0. Since the loop begins at 1, no updates occur, and the correct result is returned immediately.

Edge Case 2, Updating Elements in the Wrong Direction

A common bug occurs when updating the row from left to right. Doing so overwrites values before they are used.

For example:

[1, 2, 1]

If index 1 is updated first, the original 2 is lost before computing later elements.

The implementation avoids this issue by iterating backward, preserving all required previous-row values during computation.

Edge Case 3, Maximum Constraint Value

The largest allowed input is 33. Although this is still small, the row contains relatively large binomial coefficients.

The implementation handles this safely because both Python integers and Go integers comfortably support the resulting values within the problem constraints. The algorithm also remains efficient because the row length never exceeds 34.