LeetCode 118: Pascal's Triangle - All Solutions Explained

Problem Statement

The Pascal's Triangle problem, LeetCode 118, is an easy-difficulty challenge where you’re given an integer numRows. Your task is to generate the first numRows of Pascal's Triangle and return it as a list of lists. In Pascal's Triangle, each number is the sum of the two numbers directly above it, starting with a single 1 at the top.

Constraints

• 0≤numRows≤300 \leq \text{numRows} \leq 300≤numRows≤30

Example

Copy codeInput: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
Explanation:
    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

Copy codeInput: numRows = 1
Output: [[1]]
Explanation: Just the top row.

Copy codeInput: numRows = 0
Output: []
Explanation: Empty triangle.

Understanding the Problem

We need to generate Pascal's Triangle up to numRows, where each row is derived from the previous row by summing adjacent elements, with 1s at the ends. Key points:

• Row 0: [1].
• Row 1: [1,1].
• Row 2: [1,2,1], and so on.
• This is a pattern-based problem solvable iteratively or recursively. Let’s explore two solutions:

1. Iterative Row Generation : Simple and efficient (best solution).
2. Recursive Approach : Alternative but less practical.

Solution 1: Iterative Row Generation (Best Solution)

Intuition

Build the triangle row by row iteratively. Start with [1], then for each subsequent row, compute elements by summing pairs from the previous row, adding 1s at the start and end.

How It Works

• If numRows is 0, return an empty list.
• Initialize result with the first row: [[1]].
• For each row from 1 to numRows-1:
  • Get the previous row.
  • Create a new row starting and ending with 1.
  • For inner elements, sum adjacent elements from the previous row.
  • Append the new row to the result.
• Return the result.

Step-by-Step Example

For numRows = 5:

• Row 0: [[1]].
• Row 1: Prev=[1], New=[1,1], 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]].

Python Code (Best Solution)

Copy codedef generate(numRows):
    if numRows == 0:
        return []
    
    result = [[1]]
    
    for i in range(1, numRows):
        prev_row = result[-1]
        new_row = [1]  # Start with 1
        for j in range(len(prev_row) - 1):
            new_row.append(prev_row[j] + prev_row[j + 1])  # Sum adjacent elements
        new_row.append(1)  # End with 1
        result.append(new_row)
    
    return result

# Test cases
print(generate(5))  # Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
print(generate(1))  # Output: [[1]]
print(generate(0))  # Output: []

Detailed Walkthrough

• Base Case : Empty triangle for 0 rows.
• Iteration : Builds each row using the previous row.
• Result : Correct Pascal’s Triangle.

Complexity

• Time Complexity : O(numRows²), as each row i has i+1 elements, and we sum up to numRows-1 rows.
• Space Complexity : O(numRows²), storing the entire triangle.

Why It’s the Best

• Simple, iterative, and intuitive.
• Minimal overhead, directly builds the result.
• Interview-preferred for its clarity and efficiency.

Solution 2: Recursive Approach

Intuition

Recursively generate the triangle by computing each row based on the previous row, stopping when the desired number of rows is reached. This mirrors the iterative approach but uses function calls.

How It Works

• Base case: If numRows == 0, return [].
• If numRows == 1, return [[1]].
• Recursively get the triangle for numRows - 1.
• Compute the new row from the last row of the previous result.
• Append the new row and return.

Python Code

Copy codedef generate(numRows):
    if numRows == 0:
        return []
    if numRows == 1:
        return [[1]]
    
    prev_triangle = generate(numRows - 1)
    prev_row = prev_triangle[-1]
    new_row = [1]  # Start with 1
    for j in range(len(prev_row) - 1):
        new_row.append(prev_row[j] + prev_row[j + 1])  # Sum adjacent elements
    new_row.append(1)  # End with 1
    prev_triangle.append(new_row)
    
    return prev_triangle

# Test cases
print(generate(5))  # Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
print(generate(1))  # Output: [[1]]
print(generate(0))  # Output: []

Detailed Walkthrough

• For numRows=3:
  • numRows=1: [[1]].
  • numRows=2: [[1],[1,1]].
  • numRows=3: [[1],[1,1],[1,2,1]].
• Result : Builds bottom-up via recursion.

Complexity

• Time Complexity : O(numRows²), same work as iterative.
• Space Complexity : O(numRows²) for output, plus O(numRows) for recursion stack.

Pros and Cons

• Pros : Shows recursive thinking.
• Cons : Extra stack space, less efficient.

Comparison of Solutions

Edge Cases to Consider

1. Zero rows : 0 → [].
2. One row : 1 → [[1]].
3. Two rows : 2 → [[1],[1,1]].
4. Max rows : 30, both scale well.

Final Thoughts

• Iterative Row Generation : The best solution —simple, efficient, and space-optimal.
• Recursive Approach : Educational but overcomplicated. Master the iterative approach for its practicality in pattern problems. Try generating a specific row (LeetCode 119) as a follow-up!