Skip to main content

14. Pascal's Triangle

easyAsked at PayPal

Generate the first numRows rows of Pascal's triangle where each element is the sum of the two elements above it. PayPal asks this to evaluate 2D array construction skills and pattern recognition relevant to combinatorial financial modeling.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in PayPal loops.

  • Blind (2025)— PayPal university recruiter confirmed array/matrix generation problems in online assessments
  • LeetCode Discuss (2025)— Candidate reported Pascal's triangle as a warm-up problem in PayPal SWE interview

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. The first and last elements of each row are always 1.

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 inner element is the sum of the two elements above it from the previous row

Example 2

Input
numRows = 1
Output
[[1]]

Approaches

1. Brute force (nested loops, recompute from scratch)

For each row, recompute every element by scanning the previous row independently.

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

Tradeoff: Already optimal in complexity but this version is clear enough to present first.

2. Iterative row builder

Build each row directly from the previous row, prefilling with 1s so only inner elements need summing. Clean, O(n^2) time and space with no extra passes.

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]; // first element is always 1
    for (let j = 1; j < i; j++) {
      row.push(prev[j - 1] + prev[j]);
    }
    row.push(1); // last element is always 1
    triangle.push(row);
  }
  return triangle;
}

Tradeoff: Explicitly separates edge elements (always 1) from inner sums — communicates intent clearly to interviewers.

PayPal-specific tips

PayPal interviews focus on payment processing, fraud detection logic, financial reconciliation algorithms, and distributed transaction design. Hash maps, sliding windows, and two-pointer techniques appear frequently.

Common mistakes

  • Off-by-one in the inner loop bounds — iterating j from 0 or to i instead of 1 to i-1 overwrites the edge 1s
  • Mutating the previous row while building the current row from it
  • Returning only the last row instead of the full triangle

Follow-up questions

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

  • Return only the kth row of Pascal's triangle using O(k) space (LC 119)
  • Use Pascal's triangle to compute nCr modulo a prime efficiently
  • Given a target value, find all (row, col) positions in the triangle that equal it

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Is there an O(1) space solution?

You can generate one row at a time and return only that row (LC 119), but storing the full triangle requires O(n^2) space by definition.

Why does PayPal care about Pascal's triangle?

The iterative construction pattern — building state from prior state — directly parallels ledger reconciliation and amortization schedule generation used in financial systems.

Practice these live with InterviewChamp.AI

Drill Pascal's Triangle and other PayPal interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →