⚡Flashcard Drill➔
NeetCode #678LC-279Medium1-D Dynamic ProgrammingNC 250
← Back to All Problems

#678 · #279 · Perfect Squares(完全平方数)

📌 Problem Statement & Constraints

Given an integer n, return the fewest number of perfect squares whose sum equals n. A perfect square is k * k for some integer k. Constraints: 1 <= n <= 10^4.

💡 Core Algorithmic Approaches

  1. Let dp[i] be the minimum number of perfect squares summing to i, with dp[0] = 0.
  2. For each i, try every square k * k <= i and relax dp[i] = min(dp[i], dp[i - k * k] + 1).
  3. This is the unbounded coin-change DP where the coin set is the perfect squares.
  4. Legendre's three-square theorem gives a constant-time formula, but the DP is the expected interview solution.

💻 Benchmark Python3 Implementation

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [0] + [float("inf")] * n
        for i in range(1, n + 1):
            k = 1
            while k * k <= i:
                dp[i] = min(dp[i], dp[i - k * k] + 1)
                k += 1
        return dp[n]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n * sqrt(n)): for each of the n values, up to sqrt(n) squares are tried.
💾 Space Complexity
O(n): the DP array.

⚠️ Interview Pitfalls & Follow-ups

  • Subtracting the largest square greedily: for n = 12 greedy gives 9 + 1 + 1 + 1 (4 squares), while 4 + 4 + 4 uses only 3.
  • Using BFS without a visited set: it re-explores the same remainders and can blow up.
  • Initialising dp[0] to infinity: the base case must be 0.
  • Ignoring the square 1: it guarantees every n is reachable, so no unreachable handling is needed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems