DP — Perfect Squares
↗ LeetCode: Perfect Squares · Medium · pattern chapter →
Asked atAmazonGoogleMeta
Min count of perfect squares summing to n.
Example 1 — n=12 → 3 (4+4+4) Example 2 — n=13 → 2 (4+9)
Constraints — 1 ≤ n ≤ 10⁴. Brute BFS over all decompositions is O(n^(√n)) — dies past n=200. DP is O(n·√n) = 10⁴·100 = 10⁶ ops = <10 ms.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — DP (min coin change with square coins)
dp[i] = 1 + min(dp[i - k²]) over k² ≤ i.
java
int numSquares(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= n; i++)
for (int k = 1; k * k <= i; k++)
if (dp[i - k*k] != Integer.MAX_VALUE)
dp[i] = Math.min(dp[i], dp[i - k*k] + 1);
return dp[n];
}Complexity — Time O(n · √n); Space O(n).
Approach 2 — Lagrange's four-square theorem
Every positive integer = sum of ≤ 4 squares. Result ∈ {1,2,3,4}.
- 1 iff n is perfect square.
- 4 iff
n = 4^k · (8m + 7). - Else check if
n = a² + b²→ 2; else 3.
O(√n). Beat the DP.
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| DP | O(n · √n) | O(n) | canonical |
| Lagrange | O(√n) | O(1) | polish |
When to use which
- Interview → DP first.
- "Fast bound" → Lagrange trick.
- Return the squares → DP with parent pointers.
AI Study CompanionBeta
Related problems
Was this page helpful?