LeetCode 118 - Pascal's Triangle

LeetCode Problem 118

Difficulty: 🟢 Easy
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem is asking us to generate the first numRows of Pascal's triangle, which is a triangular arrangement of numbers where each number is the sum of the two numbers directly above it. The first row is always [1], the second row [1, 1], and subsequent rows are built by summing pairs of adjacent numbers from the previous row, with 1 at both ends of every row.

The input numRows is an integer between 1 and 30 inclusive, which specifies how many rows of Pascal's triangle we must generate. The output is a two-dimensional list or slice where each inner list represents a row of the triangle.

Important edge cases include the minimum input numRows = 1 (should return [[1]]) and small rows where sums do not require complex calculations. The constraints are small enough that a straightforward iterative solution will work efficiently, but correctness in summing the middle elements is essential.

Approaches

A brute-force approach would involve computing each element of the triangle by recursively summing the elements above it. While correct, recursion would add unnecessary overhead and could be inefficient for larger numRows. Each call would recompute sums repeatedly, leading to redundant calculations.

The optimal approach relies on the observation that we can build each row iteratively from the previous row. Each row starts and ends with 1, and each interior element is the sum of the two elements above it in the previous row. This eliminates the need for recursion or recomputation and ensures an O(numRows^2) solution since each element is computed exactly once.

Approach	Time Complexity	Space Complexity	Notes
Brute Force (Recursive)	O(2^n)	O(n)	Recursively sums values for each element; inefficient for large numRows
Optimal (Iterative)	O(numRows^2)	O(numRows^2)	Builds triangle row by row using previous row; simple and efficient

Algorithm Walkthrough

1. Initialize an empty list triangle to hold all rows of Pascal's triangle.
2. Loop i from 0 to numRows - 1 to generate each row.
3. For each row, start with a list of length i + 1 filled with 1s. The first and last elements are always 1.
4. For each position j from 1 to i - 1, set row[j] = triangle[i-1][j-1] + triangle[i-1][j]. This sums the two numbers directly above.
5. Append the completed row to triangle.
6. After the loop ends, return triangle.

Why it works: Each row is constructed using only the previous row. Since the first row is [1] and the first and last elements of each row are 1, the triangle grows correctly. This preserves the Pascal triangle property for all rows.

Python Solution

from typing import List

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        triangle = []
        for i in range(numRows):
            row = [1] * (i + 1)
            for j in range(1, i):
                row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j]
            triangle.append(row)
        return triangle

This Python implementation initializes an empty list triangle to hold all rows. It iterates from 0 to numRows - 1 to build each row. The row starts with all 1s, then the inner elements are updated using the values from the previous row. Each completed row is appended to triangle, which is returned at the end.

Go Solution

func generate(numRows int) [][]int {
    triangle := make([][]int, 0, numRows)
    for i := 0; i < numRows; i++ {
        row := make([]int, i+1)
        row[0], row[i] = 1, 1
        for j := 1; j < i; j++ {
            row[j] = triangle[i-1][j-1] + triangle[i-1][j]
        }
        triangle = append(triangle, row)
    }
    return triangle
}

The Go implementation mirrors the Python solution. We preallocate the triangle slice and each row slice. The first and last elements of the row are explicitly set to 1, and interior elements are computed by summing the corresponding elements from the previous row. Go requires explicit slice creation, but the logic is otherwise identical.

Worked Examples

Example 1: numRows = 5

i	row (initial)	row (after sums)	triangle
0	[1]	[1]	[[1]]
1	[1,1]	[1,1]	[[1],[1,1]]
2	[1,1,1]	[1,2,1]	[[1],[1,1],[1,2,1]]
3	[1,1,1,1]	[1,3,3,1]	[[1],[1,1],[1,2,1],[1,3,3,1]]
4	[1,1,1,1,1]	[1,4,6,4,1]	[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2: numRows = 1

i	row	triangle
0	[1]	[[1]]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(numRows^2)	Each row i has i + 1 elements, totaling roughly n(n+1)/2 operations
Space	O(numRows^2)	The triangle stores every row, with total elements roughly n(n+1)/2

Since each element is computed exactly once, the time complexity is quadratic, and we store all elements, giving quadratic space usage.

Test Cases

# Basic cases
assert Solution().generate(1) == [[1]]  # Single row
assert Solution().generate(2) == [[1],[1,1]]  # Two rows

# Provided examples
assert Solution().generate(5) == [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
assert Solution().generate(3) == [[1],[1,1],[1,2,1]]

# Boundary cases
assert Solution().generate(30)[-1] == [1,29,406,3654, ... ,29,1]  # Last row has correct pattern

Test	Why
numRows = 1	Minimum input edge case
numRows = 2	Small triangle, checks second row correctness
numRows = 5	Standard example, correctness of sums
numRows = 30	Stress test for largest allowed input

Edge Cases

The first edge case is numRows = 1, where only a single-element row exists. The implementation handles this by initializing a row of length 1 filled with 1. No iteration over interior elements occurs, preventing index errors.

The second edge case is numRows = 2, which ensures the algorithm correctly handles small triangles. Here, the interior sum loop does not execute because i < 2, so only the first and last elements are set, which is correct.

The third edge case is the maximum size numRows = 30. This tests for both correctness and performance. The algorithm efficiently constructs the triangle without redundant calculations and does not exceed memory limits. The iterative approach ensures it scales linearly with the number of elements.