LeetCode 279 - Perfect Squares

LeetCode Problem 279

Difficulty: 🟡 Medium
Topics: Math, Dynamic Programming, Breadth-First Search

Solution

Problem Understanding

The problem asks for the minimum number of perfect square numbers whose sum equals a given integer n.

A perfect square is a number that can be written as x * x for some integer x. Examples include 1, 4, 9, 16, and 25. The task is not to list all possible combinations, but to determine the smallest count of perfect squares needed to form the target value.

For example, if n = 12, one valid representation is:

12 = 4 + 4 + 4

This uses three perfect squares. There is no way to represent 12 using only one or two perfect squares, so the answer is 3.

The input consists of a single integer n, and the output is a single integer representing the minimum number of perfect squares required.

The constraint is:

1 <= n <= 10^4

This tells us several important things. First, the input size is relatively small, which means polynomial-time dynamic programming solutions are practical. Second, exponential brute-force recursion may still become too slow because the number of combinations grows rapidly. Third, memory usage is not a major concern because arrays of size 10^4 are completely reasonable.

Several edge cases are important to recognize early:

• If n itself is a perfect square, the answer should immediately be 1.
• Small values such as 1, 2, and 3 can expose off-by-one errors in loops or array initialization.
• Numbers that require multiple repeated squares, such as 12 = 4 + 4 + 4, test whether the algorithm correctly allows reuse of the same square.
• Values that can be represented in multiple ways require the algorithm to choose the minimum count rather than the first valid combination.

Approaches

Brute-Force Approach

A brute-force solution would try every possible combination of perfect squares that sum to n.

The recursive idea is straightforward. For a target value remaining, we try subtracting every perfect square less than or equal to remaining. Each recursive call asks:

What is the minimum number of squares needed for the smaller remainder?

The final answer is:

1 + minimum(result of all recursive branches)

This approach is correct because it explores every possible decomposition of n into perfect squares. Eventually, it must encounter the optimal combination.

However, the problem is that many subproblems repeat. For example, when solving for 12, multiple recursive paths may independently compute the answer for 8, 4, or 3. This creates enormous redundancy.

The recursion tree grows exponentially, making the brute-force approach impractical even for moderate values of n.

Optimal Dynamic Programming Approach

The key observation is that the problem has optimal substructure.

Suppose we already know the minimum number of perfect squares needed for all values smaller than n. Then for any value i, we can compute:

dp[i] = 1 + min(dp[i - square])

for every perfect square square <= i.

This works because choosing a square reduces the problem to a smaller subproblem that has already been solved optimally.

Dynamic programming avoids repeated computation by storing results in an array. Each subproblem is solved exactly once, reducing the complexity dramatically.

This is essentially the same structure as the classic coin change problem, where the perfect squares act like coin denominations.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k^n) approximately	O(n) recursion depth	Explores all combinations recursively
Optimal Dynamic Programming	O(n * sqrt(n))	O(n)	Reuses previously computed subproblems

Algorithm Walkthrough

Dynamic Programming Strategy

We create a DP array where:

dp[i] = minimum number of perfect squares needed to form i

Initially, we know:

dp[0] = 0

because zero requires no numbers.

Then we compute answers incrementally from 1 to n.

Step-by-Step Process

1. Create a DP array of size n + 1.

Each index represents a target sum. We initialize every value to infinity because we want to minimize the number of squares used. 2. Set the base case.

dp[0] = 0

This means zero numbers are needed to make the value zero. 3. Iterate through every target value from 1 to n.

For each number i, we determine the best possible decomposition into perfect squares. 4. Generate every perfect square less than or equal to i.

If j * j <= i, then j * j is a valid square choice. 5. Transition from smaller subproblems.

For each square:

dp[i] = min(dp[i], dp[i - square] + 1)

The +1 represents using the current square once. 6. Continue until the entire DP table is filled.

Because smaller values are computed first, every required subproblem is already available when needed. 7. Return dp[n].

This contains the minimum number of perfect squares needed for the original target.

Why it works

The algorithm works because every valid representation of i must end with some perfect square s. Removing that square leaves a smaller value i - s. If dp[i - s] already stores the optimal solution for the smaller value, then dp[i - s] + 1 represents a valid candidate solution for i.

By checking every possible perfect square and taking the minimum, the algorithm guarantees that dp[i] becomes the optimal answer.

Python Solution

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float('inf')] * (n + 1)
        dp[0] = 0

        for current in range(1, n + 1):
            square_root = 1

            while square_root * square_root <= current:
                square = square_root * square_root

                dp[current] = min(
                    dp[current],
                    dp[current - square] + 1
                )

                square_root += 1

        return dp[n]

The implementation begins by creating the dp array. Every position initially contains infinity because we are searching for the minimum number of squares. The base case dp[0] = 0 establishes that no numbers are needed to form zero.

The outer loop processes every target value from 1 through n. For each target, the inner loop generates all valid perfect squares that do not exceed the current value.

The transition step:

dp[current] = min(dp[current], dp[current - square] + 1)

is the core of the algorithm. It checks whether using the current square improves the best known solution.

Because the DP table is filled in increasing order, every smaller state has already been computed before it is needed.

Finally, the function returns dp[n], which contains the optimal answer.

Go Solution

func numSquares(n int) int {
	dp := make([]int, n+1)

	for i := 1; i <= n; i++ {
		dp[i] = n + 1
	}

	dp[0] = 0

	for current := 1; current <= n; current++ {
		for j := 1; j*j <= current; j++ {
			square := j * j

			if dp[current-square]+1 < dp[current] {
				dp[current] = dp[current-square] + 1
			}
		}
	}

	return dp[n]
}

The Go implementation follows the same dynamic programming strategy as the Python version.

One notable difference is initialization. Go does not have a built-in infinity value for integers, so the code uses n + 1 as a safe upper bound. Since the worst possible answer is n copies of 1, any value greater than n effectively behaves like infinity.

Slices in Go are dynamically sized references to arrays, making them a natural replacement for Python lists. Integer overflow is not a concern here because the constraints are small.

Worked Examples

Example 1: n = 12

Perfect squares less than or equal to 12 are:

1, 4, 9

We build the DP table progressively.

Current Value	Computation	dp Value
1	1	1
2	1 + 1	2
3	1 + 1 + 1	3
4	4	1
5	4 + 1	2
6	4 + 1 + 1	3
7	4 + 1 + 1 + 1	4
8	4 + 4	2
9	9	1
10	9 + 1	2
11	9 + 1 + 1	3
12	4 + 4 + 4	3

Final answer:

dp[12] = 3

Example 2: n = 13

Perfect squares less than or equal to 13 are:

1, 4, 9

Relevant DP transitions:

Current Value	Best Representation	dp Value
1	1	1
4	4	1
9	9	1
10	9 + 1	2
12	4 + 4 + 4	3
13	9 + 4	2

Final answer:

dp[13] = 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * sqrt(n))	For every number from 1 to n, we iterate through all perfect squares up to sqrt(n)
Space	O(n)	The DP array stores one value for each integer from 0 to n

The outer loop runs n times. For each value, the inner loop checks all perfect squares less than or equal to the current number. The number of such squares is approximately sqrt(n).

Therefore, the total runtime becomes:

O(n * sqrt(n))

The memory usage is linear because the DP array contains n + 1 entries.

Test Cases

solution = Solution()

assert solution.numSquares(1) == 1   # single perfect square
assert solution.numSquares(2) == 2   # 1 + 1
assert solution.numSquares(3) == 3   # 1 + 1 + 1
assert solution.numSquares(4) == 1   # perfect square itself
assert solution.numSquares(5) == 2   # 4 + 1
assert solution.numSquares(12) == 3  # example case
assert solution.numSquares(13) == 2  # example case
assert solution.numSquares(16) == 1  # larger perfect square
assert solution.numSquares(17) == 2  # 16 + 1
assert solution.numSquares(18) == 2  # 9 + 9
assert solution.numSquares(43) == 3  # 25 + 9 + 9
assert solution.numSquares(100) == 1 # large perfect square
assert solution.numSquares(9999) > 0 # stress test near upper bound

Test	Why
n = 1	Smallest valid input
n = 2	Requires repeated use of 1
n = 3	Verifies accumulation logic
n = 4	Perfect square edge case
n = 5	Combination of two squares
n = 12	Official example with repeated square
n = 13	Official example with different squares
n = 16	Larger perfect square
n = 17	Perfect square plus remainder
n = 18	Multiple equal squares
n = 43	More complex decomposition
n = 100	Large exact square
n = 9999	Upper-bound stress test

Edge Cases

Case 1: n is already a perfect square

Values such as 1, 4, 9, or 16 should immediately produce an answer of 1.

This can expose bugs where the algorithm unnecessarily decomposes the number into smaller pieces instead of recognizing the optimal direct solution. The implementation handles this naturally because when the current perfect square equals the target value, the transition becomes:

dp[i] = dp[0] + 1 = 1

which is automatically optimal.

Case 2: Very small inputs

Small values like 1, 2, and 3 are important because they test initialization correctness and loop boundaries.

Without properly setting dp[0] = 0, the algorithm cannot correctly build larger states. These cases also verify that the inner loop correctly includes the square 1.

Case 3: Numbers requiring repeated squares

Some values require using the same perfect square multiple times. For example:

12 = 4 + 4 + 4

A buggy implementation might accidentally restrict each square to be used once, which would produce incorrect answers. The DP transition allows unlimited reuse because each state can repeatedly transition from previously computed states using the same square again.