Pascal's Triangle

Pascal's Triangle

What is this problem about?

Pascal's Triangle — generating all rows up to numRows — is a foundational DP array construction problem. Each element is the sum of the two elements directly above it, forming a triangular grid that represents binomial coefficients. This appears across combinatorics, probability, and algorithm design. The array and dynamic programming interview pattern is the building block for many other problems.

Why is this asked in interviews?

Apple, Cisco, Goldman Sachs, Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe ask this because it tests 2D array construction, recurrence relations, and boundary handling — all fundamental programming skills. The problem is also a gateway to understanding combinations and binomial theorem applications.

Algorithmic pattern used

Row-by-row construction. For each row i: create a new row of length i+1. Set first and last elements to 1. For positions j=1..i-1: row[j] = prev_row[j-1] + prev_row[j]. Append each row to the result.

Example explanation

numRows=4. Build progressively:

• [1] → [[1]]
• [1,1] → [[1],[1,1]]
• [1,2,1] → append
• [1,3,3,1] → append Output: [[1],[1,1],[1,2,1],[1,3,3,1]].

Common mistakes candidates make

• Forgetting that each row has exactly row_index+1 elements.
• Modifying the previous row (always create a fresh row for each step).
• Incorrect inner loop bounds (position j from 1 to i-1, not 0 to i).
• Off-by-one: 0-indexed row 0 has 1 element, row n-1 has n elements.

Interview preparation tip

Pascal's Triangle is more than a DP warm-up — it's a gateway to binomial coefficients C(n,k). Understanding that triangle[n][k] = C(n,k) connects this to combinatorics. Practice generating it iteratively, verifying with small cases (row 4 = [1,4,6,4,1]), and recognizing its applications in probability calculations and polynomial expansion.