# Python BFS iterative boring solution O(coins*amount) time and space with simple explanation

• ``````def coinChange(self, coins, amount):
self.operations = 0
visited = set()
queue = deque([(0,0)]) # (curr_amount, coin_count)
coins.sort(reverse=True)
while queue: # bfs / shortest path
curr_amount, coin_count = queue.popleft()
if curr_amount not in visited:
self.operations += 1
if curr_amount == amount:
return coin_count
if curr_amount > amount:
continue

for coin in coins:
queue.append((curr_amount+coin, coin_count+1))

return -1
``````

Explanation:
For the example of coins=[1,2,3], and amount=8:
The path that has been taken before will always have the minimum coin count required to get to that current amount. Eg to get to a target amount of 3:
0->1->1->1 (0+1+1+1) path = 3 coins needed
0->3 (0+3) path = 1 coin needed
and because we go down the 0->3 route first, it will be put in the queue, so add it to the visited set. When we get to 0->1->1->1 later, we won't go further down that route because it is more coins that the 0->3 (and is in the visited)

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