Given n, graph will have node from n to 0. For example, if n ==4, then graph includes nodes{4,3,2,1, 0}. Each time we check current node's neighbors by looping edge_length from floort(sqrt(n)) to 1

import math

from collections import deque

class Solution(object):

def numSquares(self, n):

"""

:type n: int

:rtype: int

"""

longest_edge = int(math.floor(math.sqrt(n)))

Q = deque([(n, 0)])

visited = set()

while Q:

cur, path = Q.popleft()

for x in range(longest_edge, 0, -1):

neighbor = cur - x**2

if neighbor == 0:

return path + 1

elif neighbor > 0 and neighbor not in visited:

Q.append((neighbor, path + 1))

visited.add(neighbor)

return -1