279. Perfect Squares
Model: qwen3.5:9b
Topics: Math,Dynamic Programming,Breadth-first Search
FAANG asked: 1
Acceptance rate: 49.2%
Problem Breakdown
We are given an integer n. We need to find the minimum number of perfect square numbers (like 1, 4, 9…) whose sum equals exactly n.
Inputs: A single positive integer n ().
Outputs: An integer representing the count.
Implicit Constraints & Edge Cases:
- Perfect Squares Definition: Only integers where .
- Range: Since inputs are positive, we don’t need to handle negative numbers or zero as input (though
dp[0]is a base case). - Optimization Goal: We want the least number. This implies an optimization problem rather than just finding any combination.
Intuition
This problem maps directly to the classic “Coin Change” problem, where we have infinite supply of coins (perfect squares) and want to reach a target value with minimum count.
- Brute Force: A recursive DFS trying every possible square addition would explore an exponential search space ( or worse), leading to Time Limit Exceeded on larger inputs.
- Dynamic Programming Insight: The problem exhibits optimal substructure and overlapping subproblems. To solve for
n, we can look at smaller values: if the last perfect square used was , then the remaining sum is . Thus,dp[n] = min(dp[n], dp[n - k*k] + 1). - Mathematical Insight (Lagrange’s Four-Square Theorem): While not required for implementation given constraints (), it is worth noting that the answer will never exceed 4. This bounds our search depth if we were using BFS, but DP remains robust and easy to implement here.
Approach
We use an iterative Dynamic Programming approach (bottom-up).
- Initialize a
dparray of sizen + 1. Set all values to infinity exceptdp[0] = 0, representing that zero squares sum to zero cost. - Iterate through every number from 1 up to
n. For each indexi, we try subtracting every perfect square where . - Update the current minimum count using:
dp[i] = min(dp[i], dp[i - j*j] + 1). - Return
dp[n]after filling the table up to that index.
Alternatively, a Breadth-First Search (BFS) treats this as finding the shortest path in an unweighted graph where nodes are numbers and edges connect . However, given the constraints (), DP is sufficiently efficient and simpler to reason about without managing a queue.
Complexity Analysis
- Time Complexity: . The outer loop runs
ntimes (from 1 to n). The inner loop iterates through perfect squares up to , which averages around . With , operations are roughly proportional to , well within standard time limits. - Space Complexity: for the
dparray storing results for each number up ton.
Solution
def numSquares(n: int) -> int:
# Initialize dp array where index i stores min squares summing to i
# Use a large value (infinity) as placeholder, except base case 0
dp = [float('inf')] * (n + 1)
dp[0] = 0
# Iterate through each number from 1 up to n
for i in range(1, n + 1):
# Try subtracting every perfect square j*j <= i
j = 1
while True:
sq = j * j
if sq > i:
break
# Transition: take current best solution and add one more square (j^2)
dp[i] = min(dp[i], dp[i - sq] + 1)
j += 1
return dp[n]
Edge Cases Handled
n = 1: The loop runs once,j=1,sq=1.dp[1]becomesmin(inf, dp[0]+1)which is 1. Correctly returns 1.- Max Constraint (
n = 10^4): Array size fits in memory easily; loop iterations stay within time limits for standard interview environments (typically ~ ops/sec). - Non-Square Inputs: The logic naturally handles numbers that cannot be formed by a single square (e.g.,
n=3) by combining smaller squares found via previous DP states.