Given an integer numRows, generate the first numRows of Pascal's Triangle. Each row starts and ends with 1, and every inner value is the sum of the two values directly above it. If the interviewer asks only for one row, mention the nCr based variant too.
Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
Explanation: Every inner cell comes from previousRow[j - 1] + previousRow[j].
Input: numRows = 1
Output: [[1]]
Explanation: With one row, only the top of the triangle is returned.
- Boundary elements are always 1.
- Full triangle generation is naturally O(n^2).
- For a single row, nCr recurrence is the sharper answer.
- Memory hook: row by row, two parents build one child.
- Do not overuse factorials because they introduce overflow and repeated work.
Algorithm: Compute each value separately using combinations nCr.
Pseudo:
- For every row i from 0 to numRows - 1:
- For every column j from 0 to i, compute iCj.
- Push the computed value into the current row.
Time: O(n^3) in a naive factorial or repeated multiplication style
Space: O(1) extra apart from answer
Why mention it: Good for showing mathematical understanding, but not the best construction approach.
Algorithm: Build the triangle row by row using the previous row.
Pseudo:
- Start with an empty answer.
- For each row i, create an array of size i + 1 filled with 1.
- For every inner index j from 1 to i - 1, set row[j] = ans[i - 1][j - 1] + ans[i - 1][j].
- Push the row into the answer.
Time: O(n^2)
Space: O(n^2)
Interview line: This is the standard and most expected answer when the full triangle is required.
Algorithm: For the full triangle, the row-by-row DP build is already optimal. For one specific row, use nCr recurrence.
Pseudo:
- Full triangle case: use previous row to fill current row.
- Single row case: start with 1 and iteratively derive the next combination value.
- Push each derived value into the row answer.
Time: O(n^2) for full triangle, O(n) for one row
Space: O(n^2) for full triangle, O(1) extra for one row
Key insight: The problem has two common variants, and interviewers like when you mention both.
answer = empty list
FOR row from 0 to numRows - 1
current = empty list
FOR col from 0 to row
value = nCr(row, col)
append value to current
append current to answer
RETURN answer
answer = empty list
FOR row from 0 to numRows - 1
current = array of size row + 1 filled with 1
FOR col from 1 to row - 1
current[col] = answer[row - 1][col - 1] + answer[row - 1][col]
append current to answer
RETURN answer
IF full triangle is required
use row-by-row construction and return all rows
rowAnswer = [1]
current = 1
FOR col from 0 to rowIndex - 1
current = current * (rowIndex - col) / (col + 1)
append current to rowAnswer
RETURN rowAnswer