Fast Python BFS Solution


  • 30
    E

    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
    

  • 11

    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

  • 0
    E

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


  • 1
    C

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


  • 0

    @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

  • 0
    G

    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".


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

    Adding this block can speed up the code about 50ms


  • 0

    what is the time complexity?


  • 0
    W

    @emmarong

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


  • 0
    V

    @jedihy O(len(coins)*amount)


  • 0
    P

    @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...


Log in to reply
 

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