LeetCode 119: Pascal's Triangle II - All Solutions Explained

Problem Statement

The Pascal's Triangle II problem, LeetCode 119, is an easy-difficulty challenge where you’re given an integer rowIndex. Your task is to return the rowIndexth row (0-indexed) of Pascal's Triangle as a list. In Pascal's Triangle, each number is the sum of the two numbers directly above it, starting with a single 1 at the top. You must solve it using O(rowIndex) extra space.

Constraints

• 0≤rowIndex≤330 \leq \text{rowIndex} \leq 330≤rowIndex≤33

Example

Copy codeInput: rowIndex = 3
Output: [1,3,3,1]
Explanation:
    1
   1 1
  1 2 1
 1 3 3 1  ← Row 3

Copy codeInput: rowIndex = 0
Output: [1]
Explanation: Top row.

Copy codeInput: rowIndex = 1
Output: [1,1]
Explanation: Second row.

Understanding the Problem

We need to generate the rowIndexth row of Pascal's Triangle using only O(rowIndex) extra space, without storing the entire triangle. Key points:

• Each row can be derived from the previous row: [1], [1,1], [1,2,1], [1,3,3,1], etc.
• We can build the row iteratively or use a mathematical formula (binomial coefficients).
• Space constraint rules out storing all rows as in LeetCode 118. Let’s explore two solutions:

1. Iterative In-Place Row Update : Space-efficient and intuitive (best solution).
2. Binomial Coefficient Formula : Mathematical but less practical.

Solution 1: Iterative In-Place Row Update (Best Solution)

Intuition

Start with the first row [1] and iteratively update it in-place to generate subsequent rows up to rowIndex. For each new row, compute elements by summing adjacent elements from the previous row, reusing the same list to satisfy the O(rowIndex) space requirement.

How It Works

• If rowIndex is 0, return [1].
• Initialize the row as [1].
• For each row from 1 to rowIndex:
  • Create a new row starting with 1.
  • Compute inner elements by summing adjacent elements from the previous row.
  • End with 1.
  • Update the row to the new row.
• Return the final row.

Step-by-Step Example

For rowIndex = 3:

• Row 0: [1].
• Row 1: [1,1] (1+0, 0+1).
• Row 2: [1,2,1] (1+0, 1+1, 0+1).
• Row 3: [1,3,3,1] (1+0, 1+2, 2+1, 0+1).
• Result: [1,3,3,1].

Python Code (Best Solution)

Copy codedef getRow(rowIndex):
    row = [1]  # Start with row 0
    
    for i in range(rowIndex):
        new_row = [1]  # Start with 1
        for j in range(len(row) - 1):
            new_row.append(row[j] + row[j + 1])  # Sum adjacent elements
        new_row.append(1)  # End with 1
        row = new_row  # Update row in-place
    
    return row

# Test cases
print(getRow(3))  # Output: [1,3,3,1]
print(getRow(0))  # Output: [1]
print(getRow(1))  # Output: [1,1]

Detailed Walkthrough

• Initialization : Begins with [1].
• Iteration : Updates row using previous values.
• Result : Final row matches Pascal’s Triangle.

Complexity

• Time Complexity : O(rowIndex²), as each row i requires O(i) operations.
• Space Complexity : O(rowIndex), storing only the current row.

Why It’s the Best

• Meets O(rowIndex) space requirement.
• Simple, iterative, and intuitive.
• Interview-preferred for its practicality and clarity.

Solution 2: Binomial Coefficient Formula

Intuition

Each element in the rowIndexth row corresponds to binomial coefficients C(rowIndex,k)C(rowIndex, k)C(rowIndex,k) for k=0k = 0k=0 to rowIndexrowIndexrowIndex. Compute these directly using the formula C(n,k)=C(n,k−1)∗(n−k+1)/kC(n, k) = C(n, k-1) * (n - k + 1) / kC(n,k)=C(n,k−1)∗(n−k+1)/k, building the row in O(rowIndex) space.

How It Works

• Initialize row with [1].
• For k from 1 to rowIndex:
  • Compute next element as prev * (rowIndex - k + 1) // k.
  • Append to row.
• Return row.

Python Code

Copy codedef getRow(rowIndex):
    row = [1]
    for k in range(rowIndex):
        next_val = row[-1] * (rowIndex - k) // (k + 1)
        row.append(next_val)
    return row

# Test cases
print(getRow(3))  # Output: [1,3,3,1]
print(getRow(0))  # Output: [1]
print(getRow(1))  # Output: [1,1]

Detailed Walkthrough

• For rowIndex=3:
  • k=0: [1].
  • k=1: 1 * (3-0) // 1 = 3, [1,3].
  • k=2: 3 * (3-1) // 2 = 3, [1,3,3].
  • k=3: 3 * (3-2) // 3 = 1, [1,3,3,1].
• Result : [1,3,3,1].

Complexity

• Time Complexity : O(rowIndex), single pass to compute coefficients.
• Space Complexity : O(rowIndex), storing the row.

Pros and Cons

• Pros : Faster time complexity.
• Cons : Less intuitive, prone to integer overflow for large rowIndex without care.

Comparison of Solutions

Edge Cases to Consider

1. Zero rows : 0 → [1].
2. One row : 1 → [1,1].
3. Large rowIndex : 33, binomial may need overflow handling.
4. Small rowIndex : Both work seamlessly.

Final Thoughts

• Iterative Row Update : The best solution —meets space constraint, simple, and reliable.
• Binomial Coefficient : Faster but less intuitive and requires caution for large inputs. Master the iterative approach for its practicality in Pascal’s Triangle problems. Try generating multiple rows with a space constraint as a follow-up!