279. Perfect Squares
mediumFind the minimum number of perfect-square integers that sum to n. The unbounded-knapsack flavor of coin change — each square is a coin you can reuse.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
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 product of some integer with itself; for example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.
Constraints
1 <= n <= 10^4
Examples
Example 1
n = 123Explanation: 12 = 4 + 4 + 4.
Example 2
n = 132Explanation: 13 = 4 + 9.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Let dp[i] = min squares summing to i. The recurrence considers every square <= i.
Hint 2
dp[i] = 1 + min over k of dp[i - k*k]. Base case dp[0] = 0.
Hint 3
BFS over states 0..n with edges labeled by squares is the iterative-DP framing.
Solution approach
Reveal approach
Define dp[i] as the minimum number of perfect squares summing to i, with dp[0] = 0. For each i from 1 to n, try every j with j*j <= i and set dp[i] = min(dp[i], dp[i - j*j] + 1). Return dp[n]. Time is O(n * sqrt(n)) because the inner loop runs up to floor(sqrt(i)) times. Space is O(n). An equivalent BFS framing treats states 0..n as nodes with edges of label k*k, finding the shortest path length from 0 to n — useful intuition but the DP is cleaner to code.
Complexity
- Time
- O(n * sqrt(n))
- Space
- O(n)
Related patterns
- dynamic-programming
- bfs
- unbounded-knapsack
Related problems
- 322. Coin Change
- 518. Coin Change II
- 377. Combination Sum IV
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Microsoft
Practice these live with InterviewChamp.AI
Drill Perfect Squares and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →