Perfect Squares: BFS Levels vs Bottom-Up DP (and the Four-Square Shortcut)

The problem

LeetCode 279: return the least number of perfect squares that sum to n. For 12 the answer is 3 (4 + 4 + 4); for 13 it is 2 (4 + 9).

Approach 1: bottom-up DP

dp[i] is the answer for i. dp[0] = 0, and dp[i] = 1 + min(dp[i - s]) over every square s <= i. That is O(n * sqrt(n)) time and O(n) space, and it is the answer most interviewers expect first.

def numSquares(n):
    squares = [k * k for k in range(1, int(n ** 0.5) + 1)]
    dp = [0] + [n] * 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]

Approach 2: BFS by levels

Treat each remainder as a node and subtracting a square as an edge. The first BFS level that reaches 0 is the answer. Keep a visited set so each remainder is expanded once. In practice it stops early because the answer is never more than 4.

The shortcut worth mentioning

Lagrange's four-square theorem says every n is a sum of at most four squares, and Legendre's three-square theorem says n needs exactly four when n has the form 4^a(8b + 7). So: strip factors of 4; if the rest is 7 mod 8 return 4; if n is a square return 1; if n = a^2 + b^2 for some a return 2; otherwise 3. That is O(sqrt(n)).

How to present it

Lead with the DP, state its complexity, then mention BFS as an early-exit alternative, and only bring up the math shortcut as a follow-up. Interviewers score the clear DP higher than a memorized theorem you cannot justify.

Practicing the explanation out loud is the hard part. Linkjob AI is an interview copilot that can help with that.

Disclosure: I work on Linkjob AI.