118. Pascal's Triangle

# Question

Given an integer numRows, return the first numRows of Pascal's triangle. In Pascal's triangle, each number is the sum of the two numbers directly above it.

# Solution

# Pattern

1D Dynamic Programming (State Transition) Build the current row based purely on the values of the immediately preceding row.

# How to Identify

• The problem explicitly describes a generation process where the current state depends on the previous state.
• The structure is a grid or triangle where elements at $(r, c)$ depend on $(r-1, c-1)$ and $(r-1, c)$.

# Description

Step-by-step explanation:

1. Validate input. If numRows is 0, return an empty list.
2. Initialize the master list res to hold all the rows.
3. Iterate i from $0$ to numRows - 1. This loop represents the current row index.
4. For each row i, create a new list row.
5. Iterate j from $0$ to i. This loop builds the elements of the current row.
6. Boundary Condition: If j == 0 (first element) or j == i (last element), the value is strictly $1$. Add $1$ to the row.
7. Internal Condition: For all other elements, fetch the previous row (res.get(i - 1)). The current value is the sum of the element directly above-left (j - 1) and above-right (j). Add this sum to the row.
8. Once the inner loop finishes, add row to res.
9. Return res.

# The Intuition

Think of this as building a brick wall. You cannot place a brick in the middle of a row until the two bricks directly beneath it (or "above" it, visually, in this problem) are securely in place. Because the rules of the wall strictly dictate that a brick's value is the sum of its two supporting bricks, you don't need any complex formulas. You just need to keep the very last row of bricks you built in your memory, and use it as the foundation to build the current row. The edges of the wall are always straight lines of 1s.

# Complexity

Note: $N$ represents numRows.

# Time Complexity

The outer loop runs $N$ times. The inner loop runs $1, 2, 3, \dots, N$ times. The total number of iterations is the sum of an arithmetic progression: $\frac{N(N+1)}{2}$. This scales quadratically, making it strictly $O(N^2)$.

# Space Complexity

The returned 2D array requires $O(N^2)$ space to store the $\approx \frac{N^2}{2}$ integers. However, auxiliary space (memory used beyond what is required to construct the output) is $O(1)$, because we only create variables to hold the current row being built before appending it to the result list.

# Code

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List&lt;List&lt;Integer&gt;&gt; res = new ArrayList<>();
        if (numRows == 0) return res;
 
        for (int i = 0; i &lt; numRows; i++) {
            List&lt;Integer&gt; row = new ArrayList<&gt;();
            
            for (int j = 0; j &lt;= i; j++) {
                // The first and last elements of every row are always 1
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    // Other elements are the sum of the two elements directly above
                    List&lt;Integer&gt; prevRow = res.get(i - 1);
                    row.add(prevRow.get(j - 1) + prevRow.get(j));
                }
            }
            res.add(row);
        }
 
        return res;
    }
}

# Caveats

• Integer Overflow: For standard LeetCode constraints (numRows up to 30), standard 32-bit int is fine. However, Pascal's Triangle values grow exponentially. By row 35, the middle elements will overflow Integer.MAX_VALUE. In a real system, you must switch to long or BigInteger for N > 33.
• Formulaic Approach: Do not use the combinatorial formula $nCr = \frac{n!}{r!(n-r)!}$ to generate the entire triangle. Calculating factorials for every single cell independently takes $O(N^3)$ time and is highly prone to overflow, making it vastly inferior to the $O(N^2)$ addition method.

# Concepts to Think About

• Space Optimization: If the problem only asked you to return the last row (Pascal's Triangle II), you do not need to store the entire 2D triangle. You can compute the rows in-place using a single 1D array of size $N$, updating it from back-to-front to achieve $O(N)$ space.
• Binomial Expansion: The $k$-th row of Pascal's triangle represents the coefficients of the binomial expansion $(x+y)^k$.
• Combinatorics: The element at row $n$ and column $k$ (0-indexed) is exactly equal to $\binom{n}{k}$ (n choose k).

# Logical Follow-up

Question: Given an integer rowIndex, return only the $k$-th row of Pascal's triangle using strictly $O(k)$ extra space. (LeetCode 119: Pascal's Triangle II)

Solution: We use a single 1D array/list initialized with 1s. We iterate $k$ times. In each iteration, we traverse the array backwards from j = i - 1 down to 1, updating the array in place: row[j] = row[j] + row[j-1]. Traversing backwards ensures we don't overwrite the row[j-1] value before we need it to calculate row[j]. This achieves $O(k^2)$ time and $O(k)$ space.

Question: Can you get the $k$-th row in $O(k)$ time?

Solution: Yes, by using the mathematical property of combinations. The elements in row $n$ are $\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}$. We can calculate the next element from the previous element in $O(1)$ time using the relation: $C(n, k) = C(n, k-1) \times \frac{n - k + 1}{k}$. We start with $1$, and apply this formula to generate the row in exactly $O(k)$ time and $O(k)$ space.