Skip to main content

15. Pascal's Triangle

easyAsked at Ola

Generate the first numRows of Pascal's triangle.

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]]

Example 2

Input
numRows = 1
Output
[[1]]

Approaches

1. Compute each entry by factorial

Use the closed-form binomial coefficient.

Time
O(n^2 log n)
Space
O(n)
const fact = n => { let r=1; for (let i=2;i<=n;i++) r*=i; return r; };
return Array.from({length:numRows},(_,i)=>Array.from({length:i+1},(_,j)=>fact(i)/(fact(j)*fact(i-j))));

Tradeoff:

2. Row-by-row build

Build each row from the previous; row[j] = prev[j-1] + prev[j] with 1s at the ends.

Time
O(n^2)
Space
O(n^2)
function generate(numRows) {
  const out = [];
  for (let i = 0; i < numRows; i++) {
    const row = Array(i+1).fill(1);
    for (let j = 1; j < i; j++) row[j] = out[i-1][j-1] + out[i-1][j];
    out.push(row);
  }
  return out;
}

Tradeoff:

Ola-specific tips

Ola uses this to verify clean nested-loop indexing; mention how the iterative build mirrors aggregating per-hour ride counts into rolling totals.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

More Ola coding interview questions

See all Ola problems →

Companies that also ask Pascal's Triangle