# Python common BFS with fewer lines

• Inspired by this

``````def numSquares(self, n):
queue = collections.deque([(0, 0)])
visited = set()
while queue:
i, step = queue.popleft()
step += 1
for j in xrange(1, n + 1):
k = i + j * j
if k > n:
break
if k == n:
return step
if k not in visited:
queue.append((k, step))``````

• Hi tusizi, why I rewrite your code a little bit as follow, it got TLE, could you help me to figure out the bottleneck here? I think the time complexity should be the same as your code. Thanks.

``````def numSquares(self, n):
queue = collections.deque([(0, 0)])
visited = set()
while queue:
val, dis = queue.popleft()
if val == n:
return dis
for i in xrange(1, n+1):
j = val + i*i
if j > n:
break
if j not in visited:
queue.append((j, dis+1))``````

• @caikehe Your code need to clculate the whole level values ( "val +i*i") before you actually check whether get "n", more redundancy.

``````def numSquares(self, n):
queue = collections.deque([(0, 0)])
visited = set()
while queue:
val, dis = queue.popleft()
# if val == n:
#     return dis
for i in xrange(1, n+1):
j = val + i*i
if j > n:
break
if j == n:
return dis+1
if j not in visited: