Perfect Squares | LeetCode | Solution Explained

279. Perfect Squares on LeetCode is a mathematical problem, requiring us to pair math with algorithms. I explore how we can do that using Dynamic Programming (DP) and BFS. Problem Link.

Perfect Squares: Logic

We know that mathematically we can break it down as:

  • a, b, c, … represent the coefficients
  • we have to minimize the sum of the coefficients
expansion of n into perfect squares
expansion of n into perfect squares

The first thing I wanted to do was to try and restrict the range of x. How far can it go, when we have n restricting it?

We can do x = (int)sqrt(n) to find the x value in an instant. This takes O(log(n)) time & O(1) space. Time is because Python calculates square roots using Newton’s method. Here’s a math.stackexchange link.

Let’s take an example. When n = 120, we have sqrt(120) as 10.95… which is 10 in terms of int value. Thus, we can try and break down the 120 value

example of 120 for the perfect square question
example of 120 for the perfect square question

Let’s take another example. In this case we start with 3.

example of 12 having multiple paths for the perfect square question
example of 12 having multiple paths for the perfect square question

Clearly, we can have multiple paths. How do we know the best one? When we are making a decision between the first 2 or 3, we don’t know what would happen in the future. How can we see into the future? if you have been following me, you know its the cue for recursion!

Perfect Squares: Recursive DP Code

class Solution:
    def numSquares(self, n: int) -> int:
        @lru_cache(None)
        def recurse(n):
            if n == 0: return 0
            
            x = (int)(sqrt(n))
            count = inf
            for i in reversed(range(1, x+1)):
                if n - i*i >= 0:
                    temp = recurse(n - i*i)
                    count = min(count, temp + 1)
            return count
        
        return recurse(n)

Modified Recursive DP Code for Manual DP

class Solution:
    def numSquares(self, n: int) -> int:
        # @lru_cache(None) no need now
        def recurse(n):
            if dp[n] != inf: return dp[n]
            
            if n == 0: return 0
            
            x = (int)(sqrt(n))
            count = inf
            for i in reversed(range(1, x+1)):
                if n - i*i >= 0:
                    temp = recurse(n - i*i)
                    count = min(count, temp + 1)
            
            dp[n] = count
            return dp[n]
        
        dp = [inf]*(n+1)
        return recurse(n)

Perfect Squares: BFS Solution

The above solutions were using dfs. What if we used BFS instead? Think about why that is better. I have explained it in my video solution.

class Solution:
    def numSquares(self, n: int) -> int:
        sq = [i*i for i in range(1, (int)(sqrt(n))+1)]
        
        explore = {n}
        count = 0
        while explore:
            count += 1
            temp = set()
            for n in explore:              
                for x in sq:
                    if n - x == 0:
                        return count
                    if n - x > 0: 
                        temp.add(n-x)
            explore = temp

        return count

    Leave a Reply

    Your email address will not be published. Required fields are marked *