Skip to main content
Talentd

Perfect Squares - Solution & Explanation

MediumMathDynamic ProgrammingBreadth-First Search10 min readAsked at: Amazon, Microsoft, Goldman Sachs +9
Practice this problem

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:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

 

Constraints:

  • 1 <= n <= 104

Approach Overview

Problem Overview: Given an integer n, return the minimum number of perfect square numbers (like 1, 4, 9, 16...) whose sum equals n. Each square can be used multiple times. The challenge is minimizing the count while exploring combinations efficiently.

Approach 1: Brute Force Recursion (Exponential Time, O(√n) Space)

The brute force approach tries every possible perfect square ≤ n and recursively reduces the remaining value. For each square s, compute 1 + solve(n - s) and track the minimum result. This forms a large recursion tree because the same subproblems (like solve(12) or solve(7)) are recomputed many times. Time complexity grows exponentially in the worst case, roughly O(√n^n), while recursion depth leads to O(√n) auxiliary space. This approach demonstrates the structure of the problem but quickly becomes impractical for larger inputs.

Approach 2: Dynamic Programming (O(n√n) Time, O(n) Space)

The optimized solution uses dynamic programming. Create a DP array where dp[i] stores the minimum number of perfect squares needed to form value i. Initialize dp[0] = 0, then iterate from 1 to n. For each i, try every square j*j ≤ i and update dp[i] = min(dp[i], dp[i - j*j] + 1). This works because every optimal solution for i builds on previously solved smaller states. The algorithm checks about √n squares for each number up to n, resulting in O(n√n) time and O(n) space.

This problem is also commonly interpreted as a shortest-path problem using breadth-first search. Treat each remainder as a node and subtract perfect squares as edges. BFS guarantees the first time you reach 0 corresponds to the minimum number of squares. That approach has similar O(n√n) complexity but models the problem as a graph instead of a DP table.

The core insight comes from number decomposition and math properties of squares. Instead of enumerating combinations blindly, reuse results for smaller numbers. Every value builds on a previously computed optimal solution.

Recommended for interviews: The dynamic programming approach is what most interviewers expect. It clearly demonstrates state definition (dp[i]), transition (dp[i - j*j] + 1), and optimization over previous states. Brute force helps explain the problem structure, but the DP version shows you can eliminate redundant work and reason about time complexity.

Approach 1: Approach 1: Brute Force

In this approach, we solve the problem by checking all possible combinations or configurations naively. Although not efficient for large inputs, this approach is often straightforward and can provide insights into the problem structure.

This C solution iterates over all numbers from 0 to n-1, printing each number. It's a simple example of a brute force approach.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n).
Space Complexity: O(1), as no extra space is used other than loop variables.

Try this approach in the editor →

Approach 2: Approach 2: Optimized Solution using Dynamic Programming

This approach utilizes dynamic programming to optimize the solution by storing interim results and eliminating redundant calculations seen in a brute force approach. This method can significantly improve efficiency when dealing with complex recursive problems.

This C solution applies dynamic programming to calculate Fibonacci numbers, storing calculated values in the array 'dp' to avoid redundant calculations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n).
Space Complexity: O(n) due to the storage array.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Brute Force

Time Complexity: O(n).
Space Complexity: O(1), as no extra space is used other than loop variables.

Approach 2: Optimized Solution using Dynamic Programming

Time Complexity: O(n).
Space Complexity: O(n) due to the storage array.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force RecursionExponentialO(√n)Understanding the raw recursive structure of the problem
Dynamic ProgrammingO(n√n)O(n)General case and most common interview solution
Breadth-First SearchO(n√n)O(n)When modeling the problem as shortest path in a state graph

Video Solution

Perfect Squares - Dynamic Programming - Leetcode 279 - Python • NeetCode • 75,376 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Perfect Squares easy or hard?
Perfect Squares is typically classified as a medium difficulty problem. The brute force idea is straightforward, but recognizing the dynamic programming or BFS optimization requires familiarity with state-based problem solving.
Perfect Squares Python/Java solution
In Python or Java, the common implementation builds a dp array of size n+1. For each index i, iterate over square numbers j*j ≤ i and update dp[i] = min(dp[i], dp[i - j*j] + 1). This produces the minimum count in O(n√n) time.
How to solve Perfect Squares in O(n)?
Strict O(n) is generally not achievable using standard DP because each number must consider multiple square candidates. The practical optimal solution is O(n√n) using dynamic programming or BFS, both of which iterate over square numbers for each state.
What is the best approach for Perfect Squares?
Dynamic programming is the most common approach. Define dp[i] as the minimum number of perfect squares that sum to i and compute it using previously solved states. The algorithm runs in O(n√n) time and O(n) space, which works efficiently for typical constraints.
Is Perfect Squares asked at Google/Amazon/Meta?
Perfect Squares is a classic dynamic programming and BFS problem that appears in interviews at companies like Amazon, Google, and Microsoft. It tests state transitions, shortest path reasoning, and understanding of perfect square decomposition.
What data structure is used in Perfect Squares?
The dynamic programming solution uses an integer array dp[] to store minimum counts for each value up to n. The BFS variant uses a queue to explore remainders level by level, similar to shortest path traversal in graphs.
What is the time complexity of Perfect Squares?
The optimized dynamic programming solution runs in O(n√n) time because for every value from 1 to n it checks all square numbers up to √n. Space complexity is O(n) for the DP array storing the minimum counts.

Ready to solve this problem?

Practice Perfect Squares with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Primes

Next

Ugly Number II