LeetCode: 279. Perfect Squares

O(N**2) Time Complexity, O(N) Memory

Not an effective solution at all especially in terms of time complexity.

class Solution:
    def numSquares(self, n: int) -> int:
        INT_MAX = int(1e5)
        dp = [INT_MAX] * (n+1)
        
        x = 1
        while x * x <= n:
            dp[x*x] = 1
            x += 1
        
        for i in range(1, n+1):
            if dp[i] != INT_MAX:
                continue
            for j in range(i//2, i):
                dp[i] = min(dp[i], dp[j]+dp[i-j])
        return dp[n]

 

A nice approach would be BFS.

Time Complexity is O(N) as the worst scenario here is adding up 1s. (Deepest route is 1+1+1+...+1)

Memory Complexity is O(N*sqrt(N)) as we have sqrt(N) perfect square numbers and the height of the tree will be N at worst.

class Solution:
    def numSquares(self, n: int) -> int:
        psns = []
        x = 1
        while x * x <= n:
            psns.append(x*x)
            x += 1
        
        nums, cnt = {n}, 0
        while nums:
            next_nums = set()
            cnt += 1
            for num in nums:
                for psn in psns:
                    if psn == num:
                        return cnt
                    if num < psn:
                        break
                    next_nums.add(num-psn)
            nums = next_nums

DP Solution

Time Complexity is O(N*sqrt(N))

Memory Complexity is O(N)

class Solution:
    def numSquares(self, n: int) -> int:
        INT_MAX = int(1e5)
        dp = [INT_MAX] * (n+1)
        dp[0] = 0
        for i in range(1, n+1):
            for j in range(1, int(i**0.5)+1):
                dp[i] = min(dp[i], dp[i-j*j]+1)
        return dp[n]