Skip to main content

15. Pascal's Triangle

easyAsked at Coursera

Pascal's Triangle asks you to materialize the first numRows rows of the triangle where every interior cell is the sum of the two cells directly above it. Coursera-reported phone screens use this easy LeetCode 118 warm-up to check three things fast: can you construct a 2-D array cleanly, can you state the row-build invariant out loud, and do you recognize that O(n^2) time is output-bound because the answer itself contains roughly n^2/2 numbers.

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

Source citations

Public interview reports confirming this problem appears in Coursera loops.

  • LeetCode (2026)— Problem #118 'Pascal's Triangle' — canonical statement, the 1 <= numRows <= 30 constraint, and easy difficulty rating.
  • Google Search Console (InterviewChamp) (2026-Q2)— Live search-demand data shows candidates searching this problem paired with Coursera interview prep.

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
  • Row i (0-indexed) always contains exactly i + 1 entries, and every row starts and ends with 1.
  • Values stay well inside 32-bit integers for numRows <= 30 — the largest entry is C(29,14) = 67,863,915.

Examples

Example 1

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

Explanation: Each interior value sums the two values above it — e.g. the 6 in the last row is 3 + 3 from the row [1,3,3,1].

Example 2

Input
numRows = 1
Output
[[1]]

Explanation: The triangle always starts from the single-element row [1]; no interior cells exist yet.

Approaches

1. Brute force (recompute each row from scratch)

For each position sum the two values in the previous row without storing the triangle incrementally.

Time
O(n^2)
Space
O(n^2)
// Readable but no different in complexity
function generate(numRows) {
  const res = [];
  for (let i = 0; i < numRows; i++) {
    const row = Array(i + 1).fill(1);
    for (let j = 1; j < i; j++) row[j] = res[i-1][j-1] + res[i-1][j];
    res.push(row);
  }
  return res;
}

Tradeoff: Same asymptotic cost as the incremental build, but with more index juggling and no payoff — interviewers expect you to move past this framing quickly and name why it cannot be beaten asymptotically.

2. Incremental row build

Build each new row directly from the last stored row, filling edges with 1s and interior cells as prev[j-1]+prev[j]. Clean O(n^2) time and space, optimal for this problem.

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

Tradeoff: Optimal for the stated problem: the output itself is Theta(n^2) values, so O(n^2) time is a hard lower bound. Saying that out loud is the senior move — it shows you reason about output-bound problems instead of hunting for a faster algorithm that cannot exist.

Coursera-specific tips

Coursera's platform work is full of list-of-lists construction — think module outlines, week-by-week syllabi, nested quiz structures — so an easy 2-D construction problem maps naturally onto a day-one screen there. Candidates report the grading weight sits on communication: state the invariant ('every row starts and ends with 1; interior cell j is prev[j-1] + prev[j]') before you type, mention the output-bound O(n^2) lower bound, and finish with the row-only space optimization unprompted. Clean loop bounds matter more than speed on an easy question.

Common mistakes

  • Off-by-one in the interior loop — j must run from 1 to i-1 inclusive; running it to i double-writes the trailing 1.
  • Mutating the previous row in place while reading from it, which corrupts the sums mid-row.
  • Returning a flat array of numbers instead of an array of row arrays — re-read the required return shape.
  • Special-casing numRows = 1 with an early return that skips pushing the seed row in the general path — the loop handles it if you seed the triangle with [[1]].

Follow-up questions

An interviewer at Coursera may pivot to one of these next:

  • Pascal's Triangle II (LC 119): return only row k using O(k) extra space — build in place from right to left.
  • Compute a single entry directly with the binomial coefficient C(n, k) using iterative multiplication — no triangle needed.
  • What breaks first if numRows grows past 30? (Entry magnitude — C(n, n/2) overflows 32-bit around row 34, so discuss BigInt or modular arithmetic.)

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Can you solve it faster than O(n^2)?

No — the requested output contains 1 + 2 + ... + numRows = numRows(numRows+1)/2 numbers, so just writing the answer is already Theta(n^2). Recognizing an output-bound lower bound is the main insight interviewers listen for.

Why does building each row from the previous one always work?

It is the definition of the triangle: row i is fully determined by row i-1, with 1s on both edges. That makes the iterative build a one-direction dynamic program with no lookback beyond one row.

What if only the last row is needed?

Keep a single row and update it right-to-left (LC 119). Updating left-to-right would consume values you still need — the right-to-left sweep is the classic space trick worth mentioning unprompted.

More Coursera coding interview questions

See all Coursera problems →

Companies that also ask Pascal's Triangle