Skip to main content

14. Pascal's Triangle

easyAsked at ServiceNow

Generate the first numRows of Pascal's triangle. ServiceNow uses this to verify candidates can build and index 2-D arrays correctly — a skill directly relevant to their report-grid and matrix-based workflow analytics features.

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

Source citations

Public interview reports confirming this problem appears in ServiceNow loops.

  • Glassdoor (2025)— Reported as a 'warm-up to check 2D array comfort' during ServiceNow intern screening.
  • Reddit r/cscareerquestions (2026)— Mentioned alongside other ServiceNow new-grad interview problems.

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 element 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 interior element is the sum of the two elements above it in the previous row.

Example 2

Input
numRows = 1
Output
[[1]]

Approaches

1. Brute force: recompute each row from scratch using combinatorics

Compute C(n, k) for each position using factorial — avoids storing previous rows but recalculates redundantly.

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

Tradeoff: Exponential recursion on comb() without memoization — completely unnecessary; the previous-row approach is simpler and faster.

2. Iterative row-by-row construction

Build each row from the previous one: start with 1, add adjacent pairs from the prior row, end with 1. No recomputation, natural loop structure. This directly mirrors how ServiceNow incremental report aggregation works.

Time
O(numRows^2)
Space
O(numRows^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: O(numRows^2) time and space, which is optimal — you must output all elements. Clean, interview-ready, no edge-case surprises.

ServiceNow-specific tips

ServiceNow interviewers appreciate candidates who verbalize the loop invariant before writing code: 'row i has i+1 elements, first and last are 1, interior elements are prev[j-1]+prev[j].' Bonus signal: mention that this incremental-row pattern is structurally identical to cumulative-sum building in ServiceNow's trend analytics engine.

Common mistakes

  • Off-by-one on the inner loop bounds — the interior loop runs from j=1 to j<i, not j<i+1.
  • Mutating the previous row in-place instead of creating a new array for each row.
  • Returning triangle.slice(0, numRows) when the loop already produces exactly numRows rows — unnecessary noise in the code.

Follow-up questions

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

  • Pascal's Triangle II: return only the k-th row using O(k) space.
  • Given a row and column, return the element without building the whole triangle.
  • Use Pascal's triangle to expand (a+b)^n.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why is the space complexity O(numRows^2)?

Because you must store all rows in the output. The total number of elements is 1+2+...+numRows = numRows*(numRows+1)/2, which is O(numRows^2). If the question only asks for the last row, O(numRows) space suffices.

Can I build each row in-place?

Yes — if you traverse the row from right to left and update in place, you can halve memory. This is the trick used in Pascal's Triangle II (LC 119).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →