Perfect Squares

Difficulty: Medium Source: NeetCode

Problem

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 (e.g., 1, 4, 9, 16, …).

Example 1: Input: n = 12 Output: 3 (4 + 4 + 4)

Example 2: Input: n = 13 Output: 2 (4 + 9)

Constraints:

• 1 <= n <= 10^4

Prerequisites

Before attempting this problem, you should be comfortable with:

• Coin Change — this is structurally identical, with perfect squares as “coins”
• BFS on Implicit Graph — treating each value as a node
• Unbounded Knapsack — using the same squares unlimited times

1. Brute Force (Recursion with Memoization)

Intuition

This is exactly Coin Change, but the “coins” are all perfect squares up to n. Try subtracting each perfect square from n and recurse. Cache results to avoid recomputation.

Algorithm

1. Precompute all perfect squares up to n.
2. dp(remaining) = minimum squares needed to sum to remaining.
3. Base case: dp(0) = 0.
4. Recursive case: 1 + min(dp(remaining - sq) for sq in squares if sq <= remaining).

Solution

import math

def numSquares_memo(n):
    squares = [i * i for i in range(1, int(math.isqrt(n)) + 1)]
    memo = {}

    def dp(remaining):
        if remaining == 0:
            return 0
        if remaining in memo:
            return memo[remaining]
        best = float('inf')
        for sq in squares:
            if sq > remaining:
                break
            best = min(best, 1 + dp(remaining - sq))
        memo[remaining] = best
        return best

    return dp(n)


print(numSquares_memo(12))  # 3
print(numSquares_memo(13))  # 2
print(numSquares_memo(1))   # 1
print(numSquares_memo(4))   # 1

Complexity

• Time: O(n * sqrt(n)) with memoization
• Space: O(n) — memo table

2. Dynamic Programming (Bottom-Up)

Intuition

Same as Coin Change bottom-up. dp[i] = minimum number of perfect squares summing to i. For each i, try all perfect squares j*j <= i: dp[i] = min(dp[i], dp[i - j*j] + 1).

Start with dp[0] = 0 and infinity everywhere else. Build up to dp[n].

Algorithm

1. Precompute squares: [1, 4, 9, 16, ...] up to n.
2. Initialize dp = [inf] * (n + 1), dp[0] = 0.
3. For each i from 1 to n:
   • For each sq in squares where sq <= i:
     • dp[i] = min(dp[i], dp[i - sq] + 1).
4. Return dp[n].

Solution

import math

def numSquares(n):
    squares = [i * i for i in range(1, int(math.isqrt(n)) + 1)]
    dp = [float('inf')] * (n + 1)
    dp[0] = 0

    for i in range(1, n + 1):
        for sq in squares:
            if sq > i:
                break
            dp[i] = min(dp[i], dp[i - sq] + 1)

    return dp[n]


print(numSquares(12))   # 3  (4+4+4)
print(numSquares(13))   # 2  (4+9)
print(numSquares(1))    # 1  (1)
print(numSquares(4))    # 1  (4)
print(numSquares(100))  # 1  (100 = 10^2)
print(numSquares(7))    # 4  (4+1+1+1)

Complexity

• Time: O(n * sqrt(n)) — n amounts × sqrt(n) squares per amount
• Space: O(n) — DP array

Common Pitfalls

Using 1 as the only starting point. It’s tempting to just repeatedly subtract 1 (greedy), but that gives the wrong answer for many inputs. n=12 would give 12 ones, not 3 fours.

Forgetting that 1 is always a perfect square. Every positive integer can be decomposed into 1s, so the answer always exists. There’s no need to return -1 unlike Coin Change with arbitrary coins.

Recomputing square roots inside the loop. Precompute the list of squares outside the DP loop to avoid repeated isqrt calls. This keeps the code clean and fast.