Pascal's Triangle - Solution & Explanation

Problem Overview: Generate the first numRows of Pascal's Triangle. Each number in the triangle equals the sum of the two numbers directly above it. The first and last value of every row is always 1. The output is a 2D array where each inner array represents a row.

Approach 1: Iterative Construction (O(n²) time, O(n²) space)

This method builds the triangle row by row using a dynamic programming idea. Start with the first row [1]. For every new row i, create an array of size i + 1. Set the first and last elements to 1. For the inner elements, compute values using the previous row: row[j] = prevRow[j-1] + prevRow[j]. Continue this process until numRows rows are generated. The algorithm touches each element once, so the total time complexity is O(n²). The triangle itself stores n(n+1)/2 numbers, giving O(n²) space complexity. This approach is straightforward, avoids recursion overhead, and is the most common solution used in production code. It relies heavily on array indexing and sequential iteration, making it a good example of problems involving the Array pattern combined with simple Dynamic Programming.

Approach 2: Recursive Pascal's Triangle Construction (O(n²) time, O(n²) space)

The recursive strategy mirrors the mathematical definition of Pascal's Triangle. Define a function that generates the triangle up to row n. The base case returns [[1]]. For each recursive call, first compute the triangle up to n-1, then construct the new row using the last row of the previously generated triangle. The first and last elements remain 1, while middle elements are computed using adjacent pairs from the previous row. Although recursion makes the logic elegant, the triangle still requires visiting every element, resulting in O(n²) time complexity. The space complexity is also O(n²) for storing the triangle, plus O(n) recursion stack depth. Recursive implementations are useful when practicing recursion patterns or understanding the mathematical structure of Pascal's Triangle, but iterative construction is usually preferred in interviews.

Recommended for interviews: Interviewers typically expect the iterative construction approach. It demonstrates that you understand the relationship between rows and can translate that rule into array operations. Writing the brute recursive version shows conceptual understanding of the triangle's definition, but the iterative Dynamic Programming build is cleaner, avoids stack overhead, and is the solution most candidates present during coding interviews.