Perfect Squares - LeetCode Daily Challenge

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.

Try here before watching the video.

Video Explanation

Java Code

class Solution {

    private int solve(int n, int[] dp) {
        if(n <= 1) {
            return n;
        }
        
        if(dp[n] != -1) {
            return dp[n];
        }

        int count = Integer.MAX_VALUE;
        for(int i = 1; i <= Math.sqrt(n); i++) {
            int temp = 1 + solve(n - (i * i), dp);
            count = Math.min(temp, count);
        }
        return dp[n] = count;
    }

    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, -1);
        return solve(n, dp);    
    }
}

C++ Code

class Solution {
private:
    int solve(int n, vector<int>& dp) {
        if (n <= 1) {
            return n;
        }

        if (dp[n] != -1) {
            return dp[n];
        }

        int count = INT_MAX;
        for (int i = 1; i <= sqrt(n); i++) {
            int temp = 1 + solve(n - (i * i), dp);
            count = min(temp, count);
        }
        return dp[n] = count;
    }

public:
    int numSquares(int n) {
        vector<int> dp(n + 1, -1);
        return solve(n, dp);
    }
};

Python Code

class Solution:
    def solve(self, n: int, dp: List[int]) -> int:
        if n <= 1:
            return n
        
        if dp[n] != -1:
            return dp[n]
        
        count = float('inf')
        for i in range(1, int(n ** 0.5) + 1):
            temp = 1 + self.solve(n - (i * i), dp)
            count = min(temp, count)
        
        dp[n] = count
        return count

    def numSquares(self, n: int) -> int:
        dp = [-1] * (n + 1)
        return self.solve(n, dp)

Javascript Code

var numSquares = function(n) {
    const solve = (n, dp) => {
        if (n <= 1) {
            return n;
        }

        if (dp[n] !== -1) {
            return dp[n];
        }

        let count = Number.MAX_SAFE_INTEGER;
        for (let i = 1; i <= Math.sqrt(n); i++) {
            const temp = 1 + solve(n - (i * i), dp);
            count = Math.min(temp, count);
        }
        dp[n] = count;
        return count;
    };

    const dp = new Array(n + 1).fill(-1);
    return solve(n, dp);
};

Go Code

func solve(n int, dp []int) int {
	if n <= 1 {
		return n
	}

	if dp[n] != -1 {
		return dp[n]
	}

	count := math.MaxInt32
	for i := 1; i <= int(math.Sqrt(float64(n))); i++ {
		temp := 1 + solve(n - (i * i), dp)
		count = int(math.Min(float64(temp), float64(count)))
	}
	dp[n] = count
	return count
}

func numSquares(n int) int {
	dp := make([]int, n + 1)
	for i := range dp {
		dp[i] = -1
	}
	return solve(n, dp)
}

Complexity Analysis

Time Complexity: O(N * sqrt(N)), The time complexity of this solution can be analyzed in terms of the number of subproblems being solved. In the worst case, each recursive call can result in exploring all integers up to the square root of the given number N. Therefore, the time complexity can be expressed as O(N * sqrt(N)), where N is the input number.
Space Complexity: O(N), The space complexity is determined by the size of the memoization array dp, which has a length of N + 1. Hence, the space complexity is O(N) since it grows linearly with the input size.