The Perfect Squares problem asks for the minimum number of perfect square numbers (1, 4, 9, 16, ...) that sum to a given number n. This coding problem is solved by BFS (treating each number as a node with edges to n-square² for all valid squares) or DP (coin change variant with coin denominations being perfect squares). The math, BFS, and dynamic programming interview pattern is the core.
Apple, Goldman Sachs, Microsoft, Meta, Amazon, Google, and Bloomberg ask this because it demonstrates two elegant approaches to the same problem: BFS for minimum steps and DP for minimum coins. It also connects to Lagrange's Four-Square Theorem (every positive integer is the sum of at most 4 perfect squares).
DP (coin change). dp[i] = minimum squares summing to i. For each i: try all perfect squares j² ≤ i: dp[i] = min(dp[i], dp[i-j²]+1). Initialize dp[0]=0, all others=∞. Answer = dp[n].
BFS alternative: Each level represents one more square added. Start from n, BFS toward 0. Level = number of squares used.
n=12. Precompute squares ≤ 12: {1,4,9}. dp[0]=0. dp[1]=1 (1). dp[2]=2 (1+1). dp[3]=3 (1+1+1). dp[4]=1 (4). dp[5]=2 (4+1). ... dp[9]=1 (9). dp[10]=2 (9+1). dp[11]=3 (9+1+1). dp[12]=3 (4+4+4). Answer = 3.
Perfect Squares is both a BFS and DP problem — knowing both approaches demonstrates versatility. The DP is coin change with fixed denominations (perfect squares). The BFS gives minimum distance in an implicit graph. Lagrange's theorem provides an O(1) upper bound (answer is always 1, 2, 3, or 4). Knowing this theorem helps with sanity checking and early termination.
| Title | Difficulty | Topics | LeetCode |
|---|---|---|---|
| Integer Break | Medium | Solve | |
| 2 Keys Keyboard | Medium | Solve | |
| Egg Drop With 2 Eggs and N Floors | Medium | Solve | |
| Rotated Digits | Medium | Solve | |
| 4 Keys Keyboard | Medium | Solve |
