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 as shown:
Example 1:
Input: numRows = 5 Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
Example 2:
Input: numRows = 1 Output: [[1]]
Constraints:
1 <= numRows <= 30Problem Overview: Generate the first numRows of Pascal's Triangle. Each element is the sum of the two numbers directly above it. The first and last element of every row is always 1. The output is a 2D array containing all rows.
Approach 1: Iterative Construction (Dynamic Programming) (Time: O(n^2), Space: O(n^2))
This is the standard solution used in interviews. Build the triangle row by row using a 2D list or vector. Start with the first row [1]. For each new row, set the first and last elements to 1. For the inner elements, compute the value using the previous row: triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]. The key insight is that every value depends only on two values from the previous row, which makes this a natural dynamic programming problem. You iterate through rows and construct each one in O(row length) time, leading to O(n^2) total operations.
This approach is preferred because it directly mirrors the mathematical definition of Pascal's Triangle. Memory usage grows with the number of elements stored, which is roughly n(n+1)/2. The implementation is straightforward using an array or list of lists.
Approach 2: Recursive Pascal's Triangle Construction (Time: O(n^2), Space: O(n^2) + O(n) recursion stack)
The triangle can also be constructed recursively. The base case is the first row [1]. For row n, recursively compute the triangle up to row n-1, then generate the new row using the last row returned from the recursion. The first and last elements remain 1, while inner values are calculated as the sum of adjacent elements in the previous row.
This approach highlights the mathematical recurrence relation of Pascal's Triangle. However, recursion introduces additional stack overhead and usually results in slightly more complex code. The time complexity remains O(n^2) because every element of the triangle still needs to be generated.
Recommended for interviews: The iterative dynamic programming approach is what most interviewers expect. It demonstrates clear understanding of the triangle property and efficient state reuse. The recursive version shows mathematical insight but rarely provides practical advantages. Mentioning both approaches can strengthen your explanation: recursion reflects the formula, while the iterative method is the production-ready implementation.
This approach involves generating Pascal's Triangle row by row using an iterative method. The first row is initialized with [1], and for each subsequent row, the first and last element are always 1. The intermediate elements are calculated as sums of appropriate elements from the previous row.
In this C implementation, we allocate a 2D array to hold the triangle's content. We initialize the first and last entries of each row to 1. For each intermediate row entry, we compute its value as the sum of the two appropriate values from the preceding row, incrementally building each row from top to bottom.
C++
Java
Python
C#
JavaScript
Time Complexity: O(numRows^2) due to the nested loop structure.
Space Complexity: O(numRows^2) as we store all elements of the triangle.
This approach constructs Pascal's Triangle using recursion by calculating each value based on the combination formula. The values on the edges are always 1, and other values are calculated as combinatorial numbers derived recursively.
In this C recursive implementation, Pascal's Triangle values are computed using the combination formula. Recursive calls determine each value's placement using typical combinatorial calculations, recursively reducing the problem until base conditions are met.
C++
Java
Python
C#
JavaScript
Time Complexity: O(numRows^3) due to recursive calls, not optimal.
Space Complexity: O(numRows^2) for storing the triangle.
| Approach | Complexity |
|---|---|
| Iterative Construction Approach | Time Complexity: O(numRows^2) due to the nested loop structure. |
| Recursive Pascal's Triangle Construction | Time Complexity: O(numRows^3) due to recursive calls, not optimal. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Construction (Dynamic Programming) | O(n^2) | O(n^2) | Best general solution. Simple, efficient, and commonly expected in coding interviews. |
| Recursive Pascal's Triangle Construction | O(n^2) | O(n^2) + O(n) stack | Useful for demonstrating the mathematical recurrence relation behind Pascal's Triangle. |
Pascal Triangle | Finding nCr in minimal time • take U forward • 374,750 views views
Watch 9 more video solutions →Practice Pascal's Triangle with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor