Last updated on January 13th, 2025 at 03:12 am

Here, we see a Perfect Squares LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Breadth First Search, Dynamic Programming, Math

Companies

Google

Level of Question

Medium

Perfect Squares LeetCode Solution

1. 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.

2. Coding Pattern Used in Solution

The coding pattern used in this code is Dynamic Programming. Specifically, it is solving a “0/1 Knapsack-like problem” where the goal is to minimize the number of perfect squares that sum up to n. This problem is similar to the knapsack problem because we are iterating over possible “items” (perfect squares) and determining the minimum number of items needed to achieve a target sum (n).

3. Code Implementation in Different Languages

3.1 Perfect Squares C++

class Solution {
public:
    int numSquares(int n) {
        if (n <= 0)
        {
            return 0;
        }
        vector<int> cntPerfectSquares(n + 1, INT_MAX);
        cntPerfectSquares[0] = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j*j <= i; j++)
            {
                cntPerfectSquares[i] = 
                    min(cntPerfectSquares[i], cntPerfectSquares[i - j*j] + 1);
            }
        }
        return cntPerfectSquares.back();
    }
};

3.2 Perfect Squares Java

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        int count = 1;
        while (count * count <= n) {
            int sq = count * count;
            for (int i = sq; i <= n; i++) {
                dp[i] = Math.min(dp[i - sq] + 1, dp[i]);
            }
            count++;
        }
        return dp[n];
    }
}

3.3 Perfect Squares JavaScript

var numSquares = function(n) {
    let dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;
    for (let i = 1; i <= n; ++i) {
        let min_val = Infinity;
        for (let j = 1; j * j <= i; ++j) {
            min_val = Math.min(min_val, dp[i - j * j] + 1);
        }
        dp[i] = min_val;
    }
    return dp[n];
};

3.4 Perfect Squares Python

class Solution(object):
    def numSquares(self, n):
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        count = 1
        while count * count <= n:
            sq = count * count
            for i in range(sq, n + 1):
                dp[i] = min(dp[i - sq] + 1, dp[i])
            count += 1
        return dp[n]

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n3/2)	O(n)
Java	O(n3/2)	O(n)
JavaScript	O(n3/2)	O(n)
Python	O(n3/2)	O(n)

• The problem is solved using Dynamic Programming.
• The dp array stores the minimum number of perfect squares required to sum up to each number from 0 to n.
• The time complexity is O(n3/2) due to the nested loops, and the space complexity is O(n) because of the dp array.