Double ended BFS 148ms in Python

  • 0

    visited and level are used to search from n to 0, where visited2 and level2 searched from 0 to n. The value in visited and visited2 is the depth or step. When they met in the middle, add up the values in both dictionary to get the final steps.

    def numSquares(self, n):
        :type n: int
        :rtype: int
        visited = {n: 0}
        level = [n]
        visited2 = {0: 0}
        level2 = [0]
        while level and level2:
            new_level = []
            # extend each number from back to front
            for cur in level:
                depth = visited[cur]
                # check if they met in the middle
                if cur in visited2:
                    return visited[cur] + visited2[cur]
                # int(math.sqrt(cur)) is the largest number to square
                for i in reversed(xrange(1, int(math.sqrt(cur))+1)):
                    # subtracted towards 0 but not smaller than 0
                    num = cur - i*i
                    if num not in visited:
                        visited[num] = depth + 1
            level = new_level
            new_level2 = []
            # extend each number from front to back
            for cur2 in level2:
                depth2 = visited2[cur2]
                # check if they met in the middle
                if cur2 in visited:
                    return visited[cur2] + visited2[cur2]
                # int(math.sqrt(n - cur2)) is the largest number to square
                for i in xrange(1, int(math.sqrt(n - cur2))+1):
                    # add towards n but not exceed n
                    num2 = cur2 + i*i
                    if num2 not in visited2:
                        visited2[num2] = depth2 + 1
            level2 = new_level2

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.