# 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)

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