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

What Is LeetCode 118: Pascal's Triangle?

In LeetCode 118: Pascal's Triangle, you’re given an integer numRows, and your goal is to generate Pascal’s Triangle up to that many rows. Pascal’s Triangle is a triangular array where:

• The first and last element of each row is 1.
• Every other element is the sum of the two elements directly above it from the previous row.

The output is a list of lists, where each sublist represents a row. For example, numRows = 5 produces [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]].

Problem Statement

• Input: An integer numRows.
• Output: A list of lists representing Pascal’s Triangle up to numRows.
• Rules:
• Row 1 is [1].
• Each subsequent row builds from the previous one.

Constraints

• 0 <= numRows <= 30

Examples

• Input: numRows = 5
• Output: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
• Why: Builds row-by-row: [1], [1, 1], [1, 2, 1], etc.
• Input: numRows = 1
• Output: [[1]]
• Why: Just the top row.
• Input: numRows = 0
• Output: []
• Why: No rows requested.

Understanding the Problem: Building the Triangle

To solve LeetCode 118: Pascal's Triangle in Python, we need to generate a triangular structure where each row depends on the one above it. A naive approach might involve complex indexing or recursion, but the pattern is simple enough for efficient solutions. We’ll explore:

• Best Solution (Iterative Row-by-Row): O(n²) time, O(1) extra space (excluding output)—intuitive and fast.
• Alternative Solution (Binomial Coefficients): O(n²) time, O(1) extra space—math-based and elegant.

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

Best Solution: Iterative Row-by-Row Construction

Why This Is the Best Solution

The iterative row-by-row approach is the go-to because it’s straightforward, efficient—O(n²) time—and uses minimal extra space beyond the output. It builds each row using the previous one, mimicking how you’d draw Pascal’s Triangle by hand. It’s like stacking blocks, one level at a time, with a clear rule—perfect for beginners and pros alike!

How It Works

Here’s the strategy:

• Step 1: Handle Base Cases:
• If numRows = 0, return an empty list.
• Step 2: Start with Row 1:
• Initialize result with [[1]].
• Step 3: Build Each Row:
• For row i (0-based index):
• New row starts and ends with 1.
• Middle elements = sum of two elements from the previous row.
• Append each new row to the result.
• Step 4: Return the Triangle:
• The result is the full triangle.

Step-by-Step Example

Example: numRows = 5

• Step 1: result = [], but since numRows > 0, proceed.
• Row 0: result = [[1]].
• Row 1:
• Prev = [1].
• New = [1, 1] (1s at ends).
• result = [[1], [1, 1]].
• Row 2:
• Prev = [1, 1].
• New = [1, 1+1, 1] = [1, 2, 1].
• result = [[1], [1, 1], [1, 2, 1]].
• Row 3:
• Prev = [1, 2, 1].
• New = [1, 1+2, 2+1, 1] = [1, 3, 3, 1].
• result = [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]].
• Row 4:
• Prev = [1, 3, 3, 1].
• New = [1, 1+3, 3+3, 3+1, 1] = [1, 4, 6, 4, 1].
• result = [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]].
• Result: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        # Step 1: Handle empty case
        if numRows == 0:
            return []

        # Step 2: Initialize with first row
        result = [[1]]

        # Step 3: Build subsequent rows
        for i in range(1, numRows):
            prev_row = result[-1]
            new_row = [1]  # Start with 1
            # Calculate middle elements
            for j in range(len(prev_row) - 1):
                new_row.append(prev_row[j] + prev_row[j + 1])
            new_row.append(1)  # End with 1
            result.append(new_row)

        return result

• Line 4-5: Return empty list if numRows = 0.
• Line 8: Start result with [1].
• Line 11-17: Loop for rows 1 to numRows-1:
• Line 12: Get previous row.
• Line 13: Start new row with 1.
• Line 15-16: Sum adjacent pairs from previous row.
• Line 17: End with 1, append row.
• Line 19: Return triangle.
• Time Complexity: O(n²)—each row takes O(i) time, total ~n²/2.
• Space Complexity: O(1) extra space (output excluded).

This builds the triangle like a pro!

Alternative Solution: Binomial Coefficient Approach

Why an Alternative Approach?

The binomial coefficient method uses math to generate each element—still O(n²) time, O(1) extra space (excluding output). It’s based on the fact that Pascal’s Triangle entries are binomial coefficients (C(n, k)), offering a formulaic twist. It’s like using a calculator to fill in the blanks—elegant but less intuitive for some.

How It Works

Here’s the strategy:

• Step 1: Each element in row i, position k (0-based) is C(i, k).
• Step 2: Compute C(i, k) iteratively:
• C(i, k) = C(i, k-1) * (i - k + 1) / k.
• Step 3: Build rows using this formula.

Step-by-Step Example

Example: numRows = 5

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

Code for Binomial Approach

Copy codeclass Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        if numRows == 0:
            return []

        result = []
        for i in range(numRows):
            row = []
            val = 1  # C(i, 0)
            row.append(val)
            for k in range(i):
                val = val * (i - k) // (k + 1)  # C(i, k+1)
                row.append(val)
            result.append(row)

        return result

• Line 4-5: Empty case.
• Line 8-14: Build rows:
• Line 10-11: Start with 1.
• Line 12-13: Compute next coefficient.
• Time Complexity: O(n²)—each row takes O(i) time.
• Space Complexity: O(1) extra space.

It’s a math-powered builder!

Comparing the Two Solutions

• Iterative (Best):
• Pros: O(n²) time, O(1) space, intuitive summing.
• Cons: Slightly more manual.
• Binomial (Alternative):
• Pros: O(n²) time, O(1) space, mathematically cool.
• Cons: Less visual, potential integer overflow (rare here).

Iterative wins for simplicity.

Additional Examples and Edge Cases

• 2: [[1], [1, 1]].
• 3: [[1], [1, 1], [1, 2, 1]].
• 0: [].

Both handle these perfectly.

Complexity Breakdown

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

Iterative’s practical edge shines.

Key Takeaways

• Iterative: Sum and stack!
• Binomial: Math makes it happen!
• Pattern: Each row builds on the last.
• Python Tip: Lists are your friend—see [Python Basics](/python/basics).

Final Thoughts: Raise the Triangle

LeetCode 118: Pascal's Triangle in Python is a numeric pyramid party. The iterative approach stacks rows with ease, while the binomial method brings math magic. Want more array fun? Try LeetCode 119: Pascal's Triangle II or LeetCode 66: Plus One. Ready to build? Head to Solve LeetCode 118 on LeetCode and construct that triangle today!