279. Perfect Squares

Problem

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Thought Process

  • since 1 is a perfect square, so for any n, there must be a solution, the worst case is n
  • I tried the brute force solution but failed, i.e. find the biggest perfect score the number can hold e.g. 9 for 12:
    • e.g. 12 = 9 + 3, and 3 can only be 1 + 1 + 1, giving an result of 4
    • however, 12 = 4 + 4 + 4, which is 3
  • One solution is to model the problem as an unweighted graph:
    • for numbers from 0 to n, each number is a point
    • connect two points x, y if the distance (y-x) is a perfect square number, connect these two points
    • Then the problem is essentially a finding the shortest path problem, which can be solved with Broad First Search

Code

from collections import deque

class Solution:

    def numSquares(self, n):
        # create a queue
        q = deque()
        # store the point and number of steps to get to this point
        # initially, store n, and 0 steps to get to n first
        pair = (n, 0)

        # append pair to queue
        q.append(pair)

        # loop as long as q is not empty
        while q:
            # check the current pair at the head of queue
            curr = q.popleft()
            num = curr[0]
            step = curr[1]

            if num == 0:
                # for 0 return 0
                return step

            i = 1
            for i in range(num - i**2 + 1):
                # as long as num can hold another perfect square
                pair = (num - i**2, step + 1)
                q.append(pair)

This solution is correct logically however, it will have TLE issue. Because there were too many repetitive calculations.

Complexity

  • Time complexity is O(n**2), a nested while and for loop is used
  • Space complexity is O(n), a deque is used to store node and its level info

Optimization

Due to TLE, one way to optimize the solution is to record whether a num is visited, if it’s already visited, no need to push it into the q to avoid repetition and waste on resources.

from collections import deque

class Solution:
    def numSquares(self, n: int) -> int:
        # create a queue
        q = deque()
        # store the point and number of steps to get to this point
        # initially, store n, and 0 steps to get to n first
        pair = (n, 0)

        # append pair to queue
        q.append(pair)

        # create a visited list, initialized with all False
        visited = [False] * (n+1)
        # since (n,0) is append in queue already, so n is already visited
        visited[n] = True

        # loop as long as q is not empty
        while q:
            # check the current pair at the head of queue
            curr = q.popleft()
            num = curr[0]
            step = curr[1]

            if num == 0:
                # for 0 return 0
                return step

            i = 1

            while True:
                a = num - i**2
                # as long as num can take another perfect square
                # a is the next perfect square
                if a < 0:
                    break
                if not visited[a]:
                    pair = (a, step + 1)
                    q.append(pair)
                    visited[a] = True

                i += 1

def test():
    sol = Solution()
    print(sol.numSquares(12))
    print(sol.numSquares(13))
    print(sol.numSquares(1))

test()
3
2
1

White Board

Below is the white board: