Log inSign up
mediumLeetCodeNot Started

Perfect Squares

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

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; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

### Example 1 - Input: n = 12 - Output: 3 - Explanation: 12 = 4 + 4 + 4.

### Example 2 - Input: n = 13 - Output: 2 - Explanation: 13 = 4 + 9.

Constraints:

  • 1 <= n <= 104

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Map square sum problems to Coin Change dynamic programming.
  • Tabulate transitions over square roots in O(n sqrt(n)) time.
  • Recognize mathematical bounds from Lagrange's theorem.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Minimum count of square numbers summing to target n.
  • Equivalent to Coin Change with coins = [1, 4, 9, 16, ...].

Algorithmic Decision Tree:

  • Loop i from 1 to n.
  • Loop j from 1 while j * j <= i.

Connected Patterns:

Coin ChangeInteger BreakCombination Sum IV

1. Recursive Branching

Intuition

Recursively try subtracting every perfect square j * j <= rem and take the minimum count.

Algorithm

  1. Define solve(rem).
  2. If rem == 0, return 0.
  3. Initialize minCount = inf.
  4. For j = 1 while j * j <= rem:
  5. minCount = min(minCount, 1 + solve(rem - j * j)).
  6. Return minCount.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <algorithm>
3
4using namespace std;
5
6class Solution {
7 int solve(int n) {
8 if (n == 0) return 0;
9 int minCount = 1e9;
10 for (int j = 1; j * j <= n; ++j) {
11 minCount = min(minCount, 1 + solve(n - j * j));
12 }
13 return minCount;
14 }
15public:
16 int numSquares(int n) {
17 return solve(n);
18 }
19};
20
21int main() {
22 Solution sol;
23 cout << "Num Squares: " << sol.numSquares(12) << endl;
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(sqrt(n)^n)
  • Space complexity: O(n) call stack

2. Memoized Top-Down DP

Intuition

Store minimum squares for each value in a memo array of size n + 1.

Algorithm

  1. Initialize memo array of size n + 1 with -1.
  2. In solve(rem): return memo[rem] if already computed.
  3. Iterate j * j <= rem, track minimum count.
  4. Store in memo[rem] and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int solve(int n, vector<int>& memo) {
9 if (n == 0) return 0;
10 if (memo[n] != -1) return memo[n];
11
12 int minCount = 1e9;
13 for (int j = 1; j * j <= n; ++j) {
14 minCount = min(minCount, 1 + solve(n - j * j, memo));
15 }
16
17 return memo[n] = minCount;
18 }
19public:
20 int numSquares(int n) {
21 vector<int> memo(n + 1, -1);
22 return solve(n, memo);
23 }
24};
25
26int main() {
27 Solution sol;
28 cout << "Num Squares: " << sol.numSquares(12) << endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(n * sqrt(n))
  • Space complexity: O(n)

3. 1D Bottom-Up Tabulation (O(n * sqrt(n)))

Intuition

Iteratively fill dp array of size n + 1 where dp[i] = 1 + min(dp[i - j * j]) for all j * j <= i.

Algorithm

  1. Initialize dp array of size n + 1 with \infty; dp[0] = 0.
  2. For i from 1 to n:
  3. For j = 1 while j * j <= i:
  4. dp[i] = min(dp[i], 1 + dp[i - j * j]).
  5. Return dp[n].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int numSquares(int n) {
10 vector<int> dp(n + 1, 1e9);
11 dp[0] = 0;
12
13 for (int i = 1; i <= n; ++i) {
14 for (int j = 1; j * j <= i; ++j) {
15 dp[i] = min(dp[i], 1 + dp[i - j * j]);
16 }
17 }
18
19 return dp[n];
20 }
21};
22
23int main() {
24 Solution sol;
25 cout << "Num Squares: " << sol.numSquares(12) << endl;
26 return 0;
27}

Time & Space Complexity

  • Time complexity: O(n * sqrt(n))
  • Space complexity: O(n)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive BranchingO(sqrt(n)^n)O(n)Exhaustive branching over square subtractions.Overlapping subproblems
2.Memoized DPO(n * sqrt(n))O(n)Store answer for each remaining sum in memo array.Call stack
3.1D Bottom-Up TabulationOptimalO(n * sqrt(n))O(n)Iteratively fill dp array from 1 to n.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Greedy choice (always picking the largest square <= n): Fails on 12 (greedy picks 9 + 1 + 1 + 1 = 4 squares, but 4 + 4 + 4 = 3 squares).

Pitfall 2:

Initializing dp with 0 instead of infinity.

Crucial Edge Cases to Validate:

  • n is already a perfect square: e.g. n = 1, 4, 9, 16; returns 1.
  • n = 7: 4 + 1 + 1 + 1; returns 4.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Point out why greedy fails with the counterexample n = 12 (greedy gives 4, optimal is 3). Mentioning Legendre's three-square theorem (answer is 4 iff n = 4k * (8m + 7)) also demonstrates mathematical depth.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.According to Lagrange's Four-Square Theorem, what is the maximum possible return value of numSquares(n) for ANY positive integer n?

Back to DSA Sheet