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.

Description Solution Video 15:12

279. Perfect Squares

Medium57.0% acceptance12 companies

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 <= 10⁴

Asked at 12 companies

Revolut Accenture Yandex Bloomberg Citadel

Google Microsoft Zoho Walmart Labs Amazon Goldman Sachs Meta

Topics

15:12

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

279. Perfect Squares

Asked at 12 companies

Topics

Similar problems