# Fast Python BFS Solution

• This solution is inspired by the BFS solution for problem Perfect Square. Since it is to find the least coin solution (like a shortest path from 0 to amount), using BFS gives results much faster than DP.

``````class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
if amount == 0:
return 0
value1 = [0]
value2 = []
nc =  0
visited = [False]*(amount+1)
visited[0] = True
while value1:
nc += 1
for v in value1:
for coin in coins:
newval = v + coin
if newval == amount:
return nc
elif newval > amount:
continue
elif not visited[newval]:
visited[newval] = True
value2.append(newval)
value1, value2 = value2, []
return -1
``````

• Very nice. Though if you advertise it as fast/faster, it would really be good to say how fast it is.

I submitted it a few times and it averaged about 840 ms, which is indeed faster than the other Python solutions I've checked (fastest I knew was mine averaging about 940 ms).

And it averages about 630 ms if you replace your

``````                if newval == amount:
return nc
elif newval > amount:
continue
elif not visited[newval]:
visited[newval] = True
value2.append(newval)
``````

with this:

``````                if newval <= amount:
if not visited[newval]:
if newval == amount:
return nc
visited[newval] = True
value2.append(newval)
``````

I also tried `if newval <= amount and not visited[newval]:`, but that was consistently much slower. Always over 700 ms, whereas the two-ifs-version was always around 630 ms. Weird.

I wrote a BFS solution as well now, averages about 840 ms:

``````def coinChange(self, coins, amount):
level = seen = {0}
number = 0
while level:
if amount in level:
return number
level = {a+c for a in level for c in coins if a+c <= amount} - seen
seen |= level
number += 1
return -1``````

• Oh, thank you, I am really learning from you.

• Both the solution the answer are great. Seems to me changing the line (in Stefan's code):

``````level = {a+c for a in level for c in coins if a+c <= amount} - seen
``````

to

``````level = {a+c for a in level for c in coins if a+c <= amount and a+c not in seen}
``````

made it a little bit faster (~900-940ms vs >1000ms at this moment).

• @Chomolungma I had tried that (but chained) and for me it was slower. I just tried submitting all versions three times again:

My original => 832, 828, 844

``````level = {a+c for a in level for c in coins if a+c <= amount} - seen
``````

Yours => 928, 952, 924

``````level = {a+c for a in level for c in coins if a+c <= amount and a+c not in seen}
``````

Chained comparison I had tried => 856, 912, 844

``````level = {a+c for a in level for c in coins if amount >= a+c not in seen}
``````

Edit: Two more versions:

Swapping the order of the two tests => 868, 836, 840

``````level = {a+c for a in level for c in coins if a+c not in seen and a+c <= amount}
``````

Swapping the order of the loops => 892, 880, 876

``level = {a+c for c in coins for a in level if a+c <= amount} - seen``

• Great idea to use visited list to avoid recheck. This saves lot of time.
At first, I did not use it. It caused "Time limited Exceed".

• ``````    coins.sort()
big=coins[-1]
if not amount%big:
return amount/big
if amount%big in coins:
return amount/big+1
``````

• what is the time complexity?

• @emmarong

The line 'visited[0] = True' actually can't be disregarded. I just tried, and it makes no effects...

• @jedihy O(len(coins)*amount)

• @jedihy Yes as @victorfei said the worst-case time complexity is the same as DFS (the DP solution) but it is faster in practice to find the shortest path with BFS. I'm not sure if there is an average-case proof somewhere...

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