118. Pascal’s Triangle

Pascal’s Triangle is a classic problem frequently asked in interviews at top tech companies like Google, Amazon, and Microsoft because it tests your understanding of dynamic programming patterns and your ability to reuse previous computations to build solutions incrementally. The core challenge lies in understanding the triangle’s recursive structure and implementing it efficiently.

Problem statement

Given a positive integer numRows, your task is to generate the first numRows of Pascal’s Triangle and return them as a list of lists.

In Pascal’s Triangle, each number is calculated by summing the two numbers directly above it in the previous row. The triangle always begins with a single 1 at the top, and each subsequent row extends this pattern. The first and last elements of every row are always 1, while interior elements follow the summation rule.

Constraints:

• 1 ≤ numRows ≤ 30

Examples

Optimized approach using dynamic programming

The core intuition behind the solution is to build Pascal’s triangle row by row using dynamic programming. Pascal’s Triangle exhibits an optimal substructure: Each element in a row can be computed directly from two adjacent elements in the row above it. Using this substructure, we can build the triangle row by row, where each new row uses only the immediately preceding row’s values.

This works because of a recurrence relation: the value at position j in row i equals the sum of values at positions j-1 and j in row i-1. We don’t need to know anything about earlier rows, only the most recent one. This bottom-up construction is the essence of tabulation in dynamic programming.

Step-by-step algorithm

1. Initialize an empty list triangle to store all rows of Pascal’s Triangle.
2. Loop through each row index from 0 to numRows.
   1. For each iteration, create a new list row with a length of row_num + 1 (since row 0 has 1 element, row 1 has 2 elements, etc.).
   2. Set the first element row[0] and last element row[-1] to 1.
   3. For each interior position j (from 1 to len(row) - 1),
      1. Compute row[j] by summing the two elements from the previous row: triangle[row_num - 1][j - 1] and triangle[row_num - 1][j].
   4. Append the completed row to the triangle list.
3. After all rows are built, return the triangle as the final result.

1 / 9

Code implementation

Let’s look at the following illustration to better understand the solution.

def generate(numRows):
    # List to store all rows of Pascal's Triangle
    triangle = []
    
    # Build each row from 0 to numRows - 1
    for row_num in range(numRows):
        # Create a new row with length row_num + 1
        row = [None for _ in range(row_num + 1)]
        
        # First and last elements are always 1
        row[0], row[-1] = 1, 1
        
        # Compute interior elements using DP relation
        for j in range(1, len(row) - 1):
            row[j] = triangle[row_num - 1][j - 1] + triangle[row_num - 1][j]
        
        # Add the completed row to triangle
        triangle.append(row)
    
    return triangle

# Driver code
def main():
    test_cases = [
        {"numRows": 1},
        {"numRows": 3},
        {"numRows": 5},
        {"numRows": 7},
        {"numRows": 10}
    ]
    
    for i, case in enumerate(test_cases, 1):
        print(f"{i}.\tnumRows: {case['numRows']}")
        result = generate(case['numRows'])
        print(f"\n\tGenerated Pascal's Triangle:")
        for row in result:
            print(f"\t{row}")
        print("-" * 75)

if __name__ == "__main__":
    main()

Time complexity

The time complexity of this algorithm is O(numRows²) because we generate numRows number of rows, and for each row i, we perform i operations to fill in its elements. The first row takes 1 operation, the second takes 2, the third takes 3, and so on. The total number of operations is 1 + 2 + 3 + … + numRows, which is the sum of the first n natural numbers. This sum equals n × (n + 1) / 2, which simplifies to O(n²) where n is numRows.

Space complexity

The space complexity of this algorithm is O(1) auxiliary space. While we do use a triangle list to store the output, in complexity analysis, we typically don’t count the space required for the output itself. We only consider extra space used beyond the input and output.

Common pitfalls and interview tips

1. Off-by-one errors in indexing: A common mistake is incorrectly accessing triangle[row_num][j] instead of triangle[row_num - 1][j] when computing interior values. Remember, you’re always looking at the previous row (hence row_num - 1), not the current row being built. Carefully trace through the indices with a small example to avoid this.
2. Handling the first row edge case: Some candidates forget that when row_num = 0, there are no interior elements to compute, and the inner loop for j in range(1, len(row) - 1) naturally handles this by not executing. Don’t add unnecessary special case checks, the algorithm already handles it elegantly.
3. Misunderstanding space complexity: Many candidates claim the space complexity is O(numRows²) without qualifying whether they’re counting output space. In an interview, always clarify: “Are we counting the output storage in space complexity, or just auxiliary space?” The correct answer depends on this clarification, but typically we report O(1) auxiliary space for this problem.