Domain 2MediumCORE

Perfect Squares

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.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Math#Dynamic Programming#Breadth-first Search

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 (1≤n≤1041 \le n \le 10^4).
Outputs: An integer representing the count.

Implicit Constraints & Edge Cases:

  • Perfect Squares Definition: Only integers kk where x=k∗kx = k*k.
  • 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.

  1. Brute Force: A recursive DFS trying every possible square addition would explore an exponential search space (O(2n)O(2^n) or worse), leading to Time Limit Exceeded on larger inputs.
  2. 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 k2k^2, then the remaining sum is n−k2n - k^2. Thus, dp[n] = min(dp[n], dp[n - k*k] + 1).
  3. Mathematical Insight (Lagrange’s Four-Square Theorem): While not required for implementation given constraints (N≤104N \le 10^4), 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).

  1. Initialize a dp array of size n + 1. Set all values to infinity except dp[0] = 0, representing that zero squares sum to zero cost.
  2. Iterate through every number from 1 up to n. For each index i, we try subtracting every perfect square j∗jj*j where j2≤ij^2 \le i.
  3. Update the current minimum count using: dp[i] = min(dp[i], dp[i - j*j] + 1).
  4. 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 0..n0..n and edges connect x→x+k2x \to x + k^2. However, given the constraints (10410^4), DP is sufficiently efficient and simpler to reason about without managing a queue.

Complexity Analysis

  • Time Complexity: O(nn)O(n\sqrt{n}). The outer loop runs n times (from 1 to n). The inner loop iterates through perfect squares up to i\sqrt{i}, which averages around n\sqrt{n}. With N=104N=10^4, operations are roughly proportional to 3×1063 \times 10^6, well within standard time limits.
  • Space Complexity: O(n)O(n) for the dp array storing results for each number up to n.

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] becomes min(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 ~10810^8 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.