Perfect Squares (LeetCode 279): BFS, DP, and a Bit of Number Theory
5 views
Given a positive integer n, return the fewest perfect square numbers (1, 4, 9, 16, ...) that sum to n. For n = 12 the answer is 3 (4 + 4 + 4); for n = 13 it is 2 (4 + 9). It is a great interview problem because it can be solved three different ways, and discussing them shows range.
Approach 1: dynamic programming
Let dp[i] be the fewest squares summing to i. dp[0] = 0, and for each i:
dp[i] = 1 + min(dp[i - s]) over all squares s <= i
def num_squares(n):
squares = [k * k for k in range(1, int(n ** 0.5) + 1)]
dp = [0] + [float('inf')] * n
for i in range(1, n + 1):
for s in squares:
if s > i:
break
dp[i] = min(dp[i], dp[i - s] + 1)
return dp[n]
Time is O(n * sqrt(n)), space O(n). Explain it as an unbounded choice: each square can be used any number of times, similar in structure to making change with coins.
Approach 2: breadth-first search
Think of numbers 0..n as nodes, with an edge from x to x - s for each square s. The fewest squares is the shortest path from n to 0, and BFS finds shortest paths in unweighted graphs.
from collections import deque
def num_squares_bfs(n):
squares = [k * k for k in range(1, int(n ** 0.5) + 1)]
seen = {n}
queue = deque([(n, 0)])
while queue:
x, steps = queue.popleft()
for s in squares:
y = x - s
if y == 0:
return steps + 1
if y < 0:
break
if y not in seen:
seen.add(y)
queue.append((y, steps + 1))
BFS often stops early because answers are small, so it can be faster in practice. Mention the visited set; without it the queue explodes.
Approach 3: math (Lagrange and Legendre)
Lagrange's four-square theorem says every positive integer is a sum of at most four squares, so the answer is always 1, 2, 3, or 4. Legendre's three-square theorem says n needs four squares exactly when n has the form 4^a * (8b + 7). That leads to an O(sqrt(n)) check:
- If n is a perfect square, return 1.
- Remove factors of 4; if the remainder mod 8 is 7, return 4.
- If n equals a sum of two squares (try each square s and check whether n - s is a square), return 2.
- Otherwise return 3.
You don't need to prove the theorems in an interview, but knowing the answer is bounded by 4 is a nice insight, and it also explains why BFS terminates quickly.
How to present it
Start with DP since it's the most general, then mention BFS as an alternative view, and finish with the math shortcut if the interviewer seems interested. Ask which they'd prefer you code. Test with n = 1, 12, 13, and a number like 7, which needs four squares (4 + 1 + 1 + 1).
Support during the interview
Juggling multiple approaches under time pressure is hard. Linkjob AI (https://linkjob.ai) offers real-time help during live job interviews and technical interviews, suggesting hints and structure while you explain your own solution.