`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
```