Fast Python BFS Solution


  • 24
    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
    

  • 9

    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.


  • 0
    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)


Log in to reply
 

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