LeetCode 119: Pascal's Triangle II Solution in Python – A Step-by-Step Guide

What Is LeetCode 119: Pascal's Triangle II?

In LeetCode 119: Pascal's Triangle II, you’re given an integer rowIndex (0-based), and your task is to return the rowIndex-th row of Pascal’s Triangle as a list. Each row starts and ends with 1, and middle elements are sums of pairs from the row above. For example, rowIndex = 3 gives [1, 3, 3, 1]. The twist? You need to do it with O(k) extra space, where k is the row index, avoiding the O(n²) space of building the full triangle like in LeetCode 118.

Problem Statement

• Input: An integer rowIndex (0-based).
• Output: A list of integers—the rowIndex-th row of Pascal’s Triangle.
• Rules:
• Row 0 is [1].
• Use O(k) extra space.

Constraints

• 0 <= rowIndex <= 33

Examples

• Input: rowIndex = 3
• Output: [1, 3, 3, 1]
• Why: 4th row (0-based) of Pascal’s Triangle.
• Input: rowIndex = 0
• Output: [1]
• Why: First row.
• Input: rowIndex = 1
• Output: [1, 1]
• Why: Second row.

Understanding the Problem: Fetching One Row

To solve LeetCode 119: Pascal's Triangle II in Python, we need to generate the k-th row of Pascal’s Triangle using only O(k) extra space. A naive approach might build the entire triangle (O(n²) space) and pick the last row, but that’s overkill. Since each row depends on the previous one, we can optimize by focusing on just the row we need. We’ll explore:

• Best Solution (Iterative Single-Row): O(k) time, O(k) space—builds the row iteratively.
• Alternative Solution (Binomial Coefficients): O(k) time, O(k) space—uses math to compute elements.

Let’s start with the Best Solution—iterative construction—and break it down step-by-step.

Best Solution: Iterative Single-Row Construction

Why This Is the Best Solution

The iterative single-row approach is the star here because it’s efficient—O(k) time and O(k) space—and intuitive. It builds the target row by iteratively updating a single list, reusing space as it goes. It’s like sketching the row on a whiteboard, erasing and updating as you refine it—simple, fast, and space-smart!

How It Works

Here’s the strategy:

• Step 1: Start with Row 0:
• Initialize a list with [1].
• Step 2: Build Up to Row k:
• For each row from 1 to rowIndex:
• Create a new row starting with 1.
• Compute middle elements by summing pairs from the previous row.
• End with 1.
• Update the list to the new row.
• Step 3: Return the Row:
• The final list is the rowIndex-th row.

Step-by-Step Example

Example: rowIndex = 3

• Row 0: row = [1].
• Row 1:
• Prev = [1].
• New = [1, 1] (1s at ends).
• row = [1, 1].
• Row 2:
• Prev = [1, 1].
• New = [1, 1+1, 1] = [1, 2, 1].
• row = [1, 2, 1].
• Row 3:
• Prev = [1, 2, 1].
• New = [1, 1+2, 2+1, 1] = [1, 3, 3, 1].
• row = [1, 3, 3, 1].
• Result: [1, 3, 3, 1].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        # Step 1: Start with row 0
        row = [1]

        # Step 2: Build up to rowIndex
        for i in range(rowIndex):
            # Create new row starting with 1
            new_row = [1]
            # Compute middle elements
            for j in range(i):
                new_row.append(row[j] + row[j + 1])
            # End with 1
            new_row.append(1)
            # Update row
            row = new_row

        return row

• Line 4: Initialize with [1] (row 0).
• Line 7-14: Loop from 0 to rowIndex-1:
• Line 9: Start new row with 1.
• Line 11-12: Sum adjacent pairs from previous row.
• Line 14: End with 1.
• Line 16: Update row to new row.
• Line 18: Return final row.
• Time Complexity: O(k²)—each row i takes O(i) time, total ~k²/2.
• Space Complexity: O(k)—size of the row.

This crafts the row with finesse!

Alternative Solution: Binomial Coefficient Approach

Why an Alternative Approach?

The binomial coefficient method uses math to compute each element directly—O(k) time, O(k) space. Each element in row k is a binomial coefficient C(k, j), offering a formula-based solution. It’s like punching numbers into a calculator to get the row—elegant and precise, though less visual than iteration.

How It Works

Here’s the plan:

• Step 1: Row k has k+1 elements: [C(k,0), C(k,1), ..., C(k,k)].
• Step 2: Compute coefficients iteratively:
• Start with C(k,0) = 1.
• C(k,j) = C(k,j-1) * (k - j + 1) / j.
• Step 3: Build and return the row.

Step-by-Step Example

Example: rowIndex = 3

• Row 3: [C(3,0), C(3,1), C(3,2), C(3,3)].
• Compute:
• C(3,0) = 1.
• C(3,1) = 1 * 3 / 1 = 3.
• C(3,2) = 3 * 2 / 2 = 3.
• C(3,3) = 3 * 1 / 3 = 1.
• Result: [1, 3, 3, 1].

Code for Binomial Approach

Copy codeclass Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        # Initialize row with first element
        row = [1]

        # Compute binomial coefficients
        for j in range(rowIndex):
            # Next element = prev * (k - j) / (j + 1)
            next_val = row[-1] * (rowIndex - j) // (j + 1)
            row.append(next_val)

        return row

• Line 4: Start with [1].
• Line 7-9: Compute each next coefficient:
• Line 8: Use formula for C(k,j+1).
• Line 9: Append to row.
• Time Complexity: O(k)—linear pass to build row.
• Space Complexity: O(k)—size of the row.

It’s a math-driven row generator!

Comparing the Two Solutions

• Iterative (Best):
• Pros: O(k²) time, O(k) space, intuitive summing.
• Cons: Slower for large k.
• Binomial (Alternative):
• Pros: O(k) time, O(k) space, faster, mathematically cool.
• Cons: Less visual, potential overflow (rare within constraints).

Binomial edges out for speed, but iterative is more beginner-friendly.

Additional Examples and Edge Cases

• 0: [1].
• 2: [1, 2, 1].
• 4: [1, 4, 6, 4, 1].

Both handle these seamlessly.

Complexity Breakdown

• Iterative: Time O(k²), Space O(k).
• Binomial: Time O(k), Space O(k).

Binomial’s linear time is a perk.

Key Takeaways

• Iterative: Build step-by-step!
• Binomial: Math to the rescue!
• Space: O(k) is the goal.
• Python Tip: Lists make it easy—see [Python Basics](/python/basics).

Final Thoughts: Grab That Row

LeetCode 119: Pascal's Triangle II in Python is a neat challenge to snag a single row. The iterative approach offers a hands-on build, while binomial coefficients bring math magic. Want more Pascal fun? Check LeetCode 118: Pascal's Triangle or LeetCode 66: Plus One. Ready to fetch your row? Head to Solve LeetCode 119 on LeetCode and nail it today!