← Create New Paste

Pascal's Triangle in Coding Interviews: From Nested Lists to a Single Row in O(k) Space

3 views
Pascal's triangle shows up in two common interview forms: generate the first n rows, or return only row k. Both are easy to get working, so interviewers use them to see how cleanly you handle indexing, edge cases and space optimization, and whether you notice the link to binomial coefficients. The structure Each row starts and ends with 1, and every inner value is the sum of the two values above it: row[i][j] = row[i-1][j-1] + row[i-1][j]. Row 0 is [1], row 1 is [1, 1], row 2 is [1, 2, 1], row 3 is [1, 3, 3, 1]. Generating n rows rows = [] for i in range(n): row = [1] * (i + 1) for j in range(1, i): row[j] = rows[i-1][j-1] + rows[i-1][j] rows.append(row) return rows Filling the row with 1s first handles both edges, so the inner loop only touches positions 1 to i-1. Ask about n = 0 (return an empty list) before you start. The total work and output size are both O(n^2), which is optimal because you must produce that many numbers. Returning only row k in O(k) space Keep one list and update it in place from right to left: row = [1] * (k + 1) for i in range(2, k + 1): for j in range(i - 1, 0, -1): row[j] += row[j - 1] return row Why right to left? Each new value needs the old value at j-1. If you went left to right, you would overwrite row[j-1] before using it. This direction trick is the same one used in 0/1 knapsack space optimization, and pointing that out shows pattern recognition. The math shortcut Row k is the list of binomial coefficients C(k, 0) to C(k, k). You can compute each from the previous one: C(k, j) = C(k, j-1) * (k - j + 1) / j. This gives O(k) time. Mention integer overflow for large k: the multiplication should happen before the division, and in fixed-width languages values can exceed 32 bits for k around 34, so use 64-bit integers. Common follow-ups Interviewers may ask you to print the triangle centered, find the value at a given row and column without building rows, compute the sum of row k (it is 2^k), or count odd numbers in a row. Each one rewards connecting the triangle to combinatorics. How to present it State the recurrence, write the n-row version, then offer the in-place single-row version and explain the right-to-left order. Finish with the binomial formula as an alternative. If you want steady support while explaining solutions in a live round, Linkjob AI (https://linkjob.ai) provides real-time help during job interviews and technical interviews.
Created Nov 17, 2026 08:25 Expires Nov 17, 2027 08:25