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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Pascal's Triangle and Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →