LeetCode #322 Coin Change

Posted on | Post modified | In , , , , , , , , ,

Problem

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Examples

1
2
3
Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1
1
2
Input: coins = [2], amount = 3
Output: -1

Boundary Conditions

  • coins is null
  • amount < 0 => -1

Solution1

Method: Dynamic Programming

Time Complexity: O(|amount| |coins|)

Space Complexity: O(|amount|)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        MAX = float('inf')
        table = [0] + [MAX] * amount

        for idx in range(1, amount + 1):
            table[idx] = min([table[idx - coin] if idx - coin >= 0 else MAX for coin in coins]) + 1

        return table[amount] if table[amount] != MAX else -1
       #return [table[amount], -1][table[amount] == MAX]

or

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        if not coins and amount == 0:
            return 1
        elif not coins:
            return -1
        
        table = [float('inf') for _ in range(amount + 1)]
        table[0] = 0

        for idx in range(amount + 1):
            for coin in coins:
                if idx + coin <= amount:
                    table[idx + coin] = min(table[idx] + 1, table[idx + coin])

        return table[amount] if table[amount] != float('inf') else -1

Solution2

Method: Breadth-first Search

Time Complexity:

Space Complexity:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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