Perfect Squares — Coin Change DP with Square Numbers as Coins

Problem Statement#

Given an integer n, return the least number of perfect square numbers that sum to n. A perfect square is an integer that is the square of an integer — for example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Constraints:

• 1 <= n <= 10^4

Example 1:

Input:  n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4. Three perfect squares.

Example 2:

Input:  n = 13
Output: 2
Explanation: 13 = 4 + 9. Two perfect squares.

Example 3:

Input:  n = 1
Output: 1
Explanation: 1 = 1. One perfect square.

Example 4:

Input:  n = 4
Output: 1
Explanation: 4 is itself a perfect square.

Why This Problem Matters#

Perfect Squares (LeetCode 279) tests pattern recognition above all else: once you see that perfect squares are simply specific "coin denominations" and the target n is the "amount," the entire Coin Change (LC 322) machinery applies. This mental leap — reducing a new problem to a known DP — is one of the most valuable skills in competitive and interview programming.

Google and Amazon include this problem specifically because it has multiple valid approaches (DP, BFS, number theory), each with different complexity and insight levels. Interviewers use it to see whether a candidate can recognize the Coin Change reduction, implement the BFS layered approach as an alternative, and even mention Lagrange's four-square theorem as a mathematical upper bound.

The O(n * sqrt(n)) DP is the standard interview solution. The BFS alternative is useful for demonstrating alternative thinking.

The Core Insight#

Perfect squares up to n are: 1, 4, 9, 16, 25, ... — i.e., j^2 for j = 1, 2, 3, ... while j^2 <= n.

These are the "coin denominations." The "amount" is n. You want the minimum number of coins (perfect squares) that sum to n. This is exactly Coin Change (LC 322).

Recurrence: dp[i] = min(dp[i - j*j] + 1) for all j where j*j <= i.

Base case: dp[0] = 0 — zero squares needed to sum to 0.

Important mathematical note: By Lagrange's four-square theorem, every positive integer can be expressed as the sum of at most four perfect squares. So the answer is always between 1 and 4. This is a useful sanity check and can be mentioned in interviews as a mathematical insight.

Optimal substructure: To achieve sum i using j^2 as the last square, you need the optimal way to achieve i - j^2, which is a strictly smaller subproblem.

Overlapping subproblems: Without memoization, the same subproblem dp[k] is recomputed many times from different larger values.

Building the DP Solution#

Step 1 — Naive Recursion (Exponential)#

# Python — naive recursion, exponential — illustrative only
def numSquares(n):
    import math
    squares = [j * j for j in range(1, int(math.sqrt(n)) + 1)]
 
    def dp(remaining):
        if remaining == 0:
            return 0
        return min(dp(remaining - s) + 1 for s in squares if s <= remaining)
 
    return dp(n)

// JavaScript — naive recursion
function numSquares(n) {
    const squares = [];
    for (let j = 1; j * j <= n; j++) squares.push(j * j);
 
    function dp(remaining) {
        if (remaining === 0) return 0;
        let best = Infinity;
        for (const s of squares) {
            if (s <= remaining) best = Math.min(best, dp(remaining - s) + 1);
        }
        return best;
    }
 
    return dp(n);
}

Step 2 — Top-Down Memoization (O(n * sqrt(n)) time, O(n) space)#

# Python — top-down memoization
from functools import lru_cache
import math
 
class Solution:
    def numSquares(self, n: int) -> int:
        squares = [j * j for j in range(1, int(math.sqrt(n)) + 1)]
 
        @lru_cache(maxsize=None)
        def dp(remaining: int) -> int:
            if remaining == 0:
                return 0
            return min(dp(remaining - s) + 1 for s in squares if s <= remaining)
 
        return dp(n)

// JavaScript — top-down memoization
var numSquares = function(n) {
    const squares = [];
    for (let j = 1; j * j <= n; j++) squares.push(j * j);
    const memo = new Map();
 
    function dp(remaining) {
        if (remaining === 0) return 0;
        if (memo.has(remaining)) return memo.get(remaining);
        let best = Infinity;
        for (const s of squares) {
            if (s <= remaining) best = Math.min(best, dp(remaining - s) + 1);
        }
        memo.set(remaining, best);
        return best;
    }
 
    return dp(n);
};

Step 3 — Bottom-Up Tabulation (O(n * sqrt(n)) time, O(n) space)#

# Python — bottom-up tabulation
import math
 
class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
 
        for i in range(1, n + 1):
            j = 1
            while j * j <= i:
                dp[i] = min(dp[i], dp[i - j * j] + 1)
                j += 1
 
        return dp[n]

// JavaScript — bottom-up tabulation
var numSquares = function(n) {
    const dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;
 
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j * j <= i; j++) {
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
        }
    }
 
    return dp[n];
};

Optimized Solution#

The standard submission-ready solution with a clean structure:

# Python — final solution, O(n * sqrt(n)) time, O(n) space
class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        for i in range(1, n + 1):
            j = 1
            while j * j <= i:
                dp[i] = min(dp[i], dp[i - j * j] + 1)
                j += 1
        return dp[n]

// JavaScript — final solution
var numSquares = function(n) {
    const dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j * j <= i; j++) {
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
        }
    }
    return dp[n];
};

Alternative: BFS approach (treats the problem as a shortest-path graph):

# Python — BFS approach, O(n * sqrt(n)) time, O(n) space
from collections import deque
 
class Solution:
    def numSquares(self, n: int) -> int:
        squares = [j * j for j in range(1, int(n ** 0.5) + 1)]
        queue = deque([n])
        visited = {n}
        level = 0
 
        while queue:
            level += 1
            for _ in range(len(queue)):
                remaining = queue.popleft()
                for s in squares:
                    nxt = remaining - s
                    if nxt == 0:
                        return level
                    if nxt > 0 and nxt not in visited:
                        visited.add(nxt)
                        queue.append(nxt)
 
        return level

BFS treats each value as a graph node with edges to value - s for each square s. The minimum path to 0 from n is the answer. BFS guarantees the shortest path in an unweighted graph.

Visual Dry Run#

Input: n = 12

Answer: 3. Decomposition: 4 + 4 + 4 = 12.

Complexity Analysis#

For n = 10^4: 10^4 * 100 = 10^6 operations. Very fast.

Common Mistakes#

1. Not recognizing the Coin Change isomorphism. Candidates who miss the reduction often try greedy (always use the largest square that fits), which fails for cases like n = 12 where greedily picking 9 leads to 9 + 1 + 1 + 1 = 4 squares, while 4 + 4 + 4 = 3 is optimal.

2. Greedy always picking the largest square. For n = 12: greedy picks 9 (remaining 3), then 1+1+1 = 4 total. DP finds 4+4+4 = 3. Greedy fails.

3. Initializing dp[i] = 0 instead of infinity. Zero means "0 squares needed," which is only true for dp[0]. All other positions need infinity as a sentinel.

4. Off-by-one in the square root computation. Use while j * j <= i rather than while j * j < i. Missing perfect squares (e.g., j=2 for i=4) causes incorrect answers.

5. Forgetting dp[0] = 0. Without this base case, no amounts can be built from 0, and the entire dp array stays at infinity.

6. Missing the connection to Coin Change. Always mention it: "This is Coin Change where the denominations are all perfect squares up to n."

Interview Tips#

Lead with the reduction. "I recognize that perfect squares are coin denominations and n is the target amount. This is identical to Coin Change (LC 322) — I'll use the same dp[i] = min(dp[i - j^2] + 1) recurrence."

Mention Lagrange's four-square theorem. "By Lagrange's theorem, every positive integer is the sum of at most four perfect squares. So the answer is always 1, 2, 3, or 4 — this is a useful sanity check." Mentioning this theorem signals mathematical depth.

Offer the BFS alternative. "I can also model this as a shortest-path problem on a graph where each node has edges to values obtained by subtracting a perfect square. BFS gives the same O(n * sqrt(n)) complexity."

State the complexity clearly. "For each of the n values in the dp array, I try at most sqrt(n) perfect squares. Total: O(n * sqrt(n)) time, O(n) space."

Follow-up Questions#

Q: What is the mathematical upper bound on the answer? By Legendre's three-square theorem and Lagrange's four-square theorem, the answer is at most 4. If n is a perfect square, the answer is 1. If n = 4^a * (8b + 7) for non-negative integers a, b, the answer is 4. Otherwise, check if it is achievable in 1, 2, or 3 squares.

Q: Can you solve this in O(sqrt(n)) using number theory? Yes, using Legendre's three-square theorem and direct checks. For interview purposes, the DP solution is universally accepted.

Q: What if you had to count the number of ways to decompose n, not just the minimum? That is the Perfect Squares counting variant — use Coin Change II logic: dp[i] += dp[i - j*j] with dp[0] = 1.

Q: What if square numbers could be used at most once? This becomes a 0/1 knapsack. Iterate amounts in reverse (right to left) when updating dp to prevent reuse.

Q: How does BFS compare to DP for this problem? Both are O(n * sqrt(n)) time and O(n) space. BFS is intuitive when thinking of the problem as shortest-path. DP is more natural when thinking of it as knapsack. Both are valid interview answers.

Key Takeaways#

• Perfect Squares is Coin Change where the denominations are all perfect squares 1, 4, 9, 16, ... up to n.
• Recurrence: dp[i] = min(dp[i - j*j] + 1) for all j with j*j <= i. Base case: dp[0] = 0.
• Initialize dp[i] = infinity for all i > 0. The answer is dp[n].
• Lagrange's four-square theorem guarantees the answer is at most 4 — a useful mathematical fact to mention in interviews.
• Time O(n * sqrt(n)), Space O(n). For n = 10^4, this is about 10^6 operations.
• BFS is a valid alternative: model values as graph nodes, edges to value - s, and find the shortest path from n to 0.
• Always reduce new problems to known patterns — this problem is a textbook example of reduction to Coin Change.