Skip to main content

118. Pascal's Triangle

easy

Generate the first numRows of Pascal's triangle, where each number is the sum of the two directly above it. A classic introduction to DP table construction.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

  • 1 <= numRows <= 30

Examples

Example 1

Input
numRows = 5
Output
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Explanation: Each row starts and ends with 1; interior cells sum the two cells above.

Example 2

Input
numRows = 1
Output
[[1]]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Row i has i+1 entries; first and last are 1.

Hint 2

For interior position j in row i: row[i][j] = row[i-1][j-1] + row[i-1][j].

Hint 3

Build row-by-row using only the previous row — no big table needed if you stream output.

Solution approach

Reveal approach

Define the subproblem as 'the i-th row of the triangle'. The recurrence relation is row[i][j] = row[i-1][j-1] + row[i-1][j] for interior positions, with row[i][0] = row[i][i] = 1 as base cases. Iterate i from 0 to numRows-1, allocate a new row of length i+1 with both endpoints set to 1, then fill the interior by reading from the previously appended row. Append each completed row to the result list. Time is O(numRows^2) because total cells equal 1+2+...+numRows; space is O(numRows^2) for the output (no extra DP table needed since the last row in the result list is the 'previous row').

Complexity

Time
O(numRows^2)
Space
O(numRows^2)

Related patterns

  • dynamic-programming
  • memoization-recursion

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Adobe
  • Microsoft

More Dynamic Programming practice problems

See all Dynamic Programming problems →