# Double ended BFS 148ms in Python

• `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
new_level.append(num)
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
new_level2.append(num2)
level2 = new_level2``````

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