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


  • 1
    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))
    
                visited.add(curr_amount)
    
        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)


Log in to reply
 

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