Perfect Squares | Leetcode 279

Welcome to our deep dive on Perfect Squares (Leetcode 279). This problem is a brilliant application of Dynamic Programming and Breadth-First Search (BFS), asking us to find the shortest path to zero by continuously subtracting perfect square numbers.

Problem Statement

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 square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Example 1: n = 12 => Output: 3 (Explanation: 12 = 4 + 4 + 4).

Example 2: n = 13 => Output: 2 (Explanation: 13 = 4 + 9).

Approach 1: Dynamic Programming O(N * sqrt(N))

This problem can be thought of as a variation of the classic "Coin Change" problem, where our "coins" are all the perfect squares less than or equal to n.

We can build a DP array dp of size n + 1, where dp[i] represents the minimum number of perfect squares required to sum up to i. We initialize the array with a theoretical max value (e.g., n), except for dp[0] = 0 (since it takes 0 squares to sum to 0).

For every number from 1 to n, we test subtracting every possible perfect square s. The recurrence relation is: dp[i] = min(dp[i], 1 + dp[i - s])

import math

class Solution:
    def numSquares(self, n: int) -> int:
        # Initialize DP array with n (worst case is n 1s)
        dp = [n] * (n + 1)
        dp[0] = 0
        
        # Precompute all perfect squares up to n to avoid recalculating
        max_square_index = int(math.sqrt(n)) + 1
        squares = [i * i for i in range(1, max_square_index)]
        
        for i in range(1, n + 1):
            for square in squares:
                if i < square:
                    break
                dp[i] = min(dp[i], 1 + dp[i - square])
                
        return dp[n]

Complexity Analysis

Approach 2: Breadth-First Search (Shortest Path)

Instead of exhaustive DP tabulation, we can treat this as an unweighted shortest-path graph problem! The nodes are numbers [0, ..., n]. The edges are perfect squares. We want the shortest path from n to 0.

Starting from n, we subtract every valid perfect square and push the resulting "remainders" into a Queue. Every time we process a full layer of the queue, we increment our "depth" or "step count." The first time we hit 0, we have mathematically guaranteed it is the absolute shortest possible path!

from collections import deque
import math

class Solution:
    def numSquares(self, n: int) -> int:
        squares = [i * i for i in range(1, int(math.sqrt(n)) + 1)]
        
        queue = deque([n])
        visited = {n}
        level = 0
        
        while queue:
            level += 1
            # Process strictly by layer
            for _ in range(len(queue)):
                remainder = queue.popleft()
                
                for sq in squares:
                    if remainder == sq:
                        return level  # Hit 0 inherently
                    if remainder < sq:
                        break
                        
                    next_val = remainder - sq
                    if next_val not in visited:
                        visited.add(next_val)
                        queue.append(next_val)
                        
        return level

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (279)