Coin Change
MedPrompt
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return 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.
You may assume that you have an infinite number of each kind of coin.
Example 1:
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1Example 2:
Input: coins = [2], amount = 3
Output: -1Example 3:
Input: coins = [1], amount = 0
Output: 0
Constraints:
1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
Approaches
3 approaches with complexity analysis and trade-offs.
This approach attempts to solve the problem by exploring every possible combination of coins that could sum up to the target amount. It uses a recursive function that for a given amount, tries using each coin and recursively calls itself for the amount - coin. The function then returns the minimum number of coins found among all branches of the recursion.
Algorithm
- Define a recursive function
solve(amount). - Base Case 1: If
amount == 0, return 0. - Base Case 2: If
amount < 0, return a value indicating impossibility (e.g., infinity or a special marker like -1). - Initialize a variable
min_coinsto infinity. - Iterate through each
coinin thecoinsarray:- Make a recursive call:
result = solve(amount - coin). - If the
resultindicates a valid solution was found for the subproblem, updatemin_coins = min(min_coins, 1 + result).
- Make a recursive call:
- Return
min_coins. - In the main function, if the final result is infinity, it means no solution exists, so return -1. Otherwise, return the result.
Walkthrough
The core of this method is a recursive helper function. This function calculates the minimum coins for a given amount by breaking it down into smaller subproblems. For an amount A, it tries subtracting each available coin c and recursively finds the minimum coins for the new amount A - c. The total coins for this path would be 1 + min_coins(A - c). The function explores all such paths and returns the minimum among them.
Base Cases:
- If the
amountbecomes 0, it means we've successfully made the change, so we need 0 more coins. - If the
amountbecomes negative, it means the last coin used was too large, so this path is invalid.
The primary drawback is its performance. The same subproblem (e.g., finding the minimum coins for an amount of 5) is calculated multiple times through different recursive paths, leading to an exponential number of function calls.
class Solution { public int coinChange(int[] coins, int amount) { if (amount < 0) return -1; if (amount == 0) return 0; int minCoins = Integer.MAX_VALUE; for (int coin : coins) { int res = coinChange(coins, amount - coin); // If the subproblem has a solution (res >= 0) and it's better than what we have if (res >= 0 && res < minCoins) { minCoins = 1 + res; } } return (minCoins == Integer.MAX_VALUE) ? -1 : minCoins; }}Complexity
Time
O(S^N) Where `S` is the number of coins and `N` is the amount. For each amount, the function branches out `S` times. This creates a recursion tree of depth up to `N`, leading to an exponential number of calls.
Space
O(amount) The space complexity is determined by the maximum depth of the recursion stack. In the worst case, the recursion can go as deep as the `amount` (e.g., if there is a coin of value 1).
Trade-offs
Pros
Conceptually simple and follows a natural, divide-and-conquer logic.
Cons
Extremely inefficient due to redundant computations.
Will lead to a 'Time Limit Exceeded' (TLE) error on most platforms for non-trivial inputs.
This approach enhances the brute-force recursion by using memoization, a dynamic programming technique. It stores the results of expensive function calls (subproblems) and returns the cached result when the same inputs occur again. This avoids re-computation and drastically improves performance.
Algorithm
- Create a memoization array,
memo, of sizeamount + 1to store the results of subproblems. Initialize it with a sentinel value (e.g., -2) to indicate an uncomputed state. - Define a recursive helper function
solve(amount, memo). - Base Case 1: If
amount == 0, return 0. - Base Case 2: If
amount < 0, return -1 (impossibility). - Memoization Check: If
memo[amount]is not the sentinel value, return the stored result. - Initialize
min_coins = infinity. - For each
coinincoins:- Recursively call
res = solve(amount - coin, memo). - If
resis not -1, updatemin_coins = min(min_coins, 1 + res).
- Recursively call
- Store the computed result in the memoization table:
memo[amount] = (min_coins == infinity) ? -1 : min_coins. - Return
memo[amount].
Walkthrough
We introduce a memoization table (an array, memo) to store the minimum coins required for each amount from 0 to amount. Before computing the solution for an amount, we first check if the result is already in our memo table. If it is, we return it directly. If not, we compute it recursively as in the brute-force approach. Once the result is computed, we store it in the memo table before returning.
This way, each subproblem solve(i) for i from 0 to amount is computed only once. The results are then reused, pruning the recursion tree of all redundant branches.
import java.util.Arrays; class Solution { public int coinChange(int[] coins, int amount) { // Use an array to store results for subproblems. // -2 indicates not computed, -1 indicates impossible. int[] memo = new int[amount + 1]; Arrays.fill(memo, -2); return solve(coins, amount, memo); } private int solve(int[] coins, int amount, int[] memo) { // Base cases if (amount == 0) { return 0; } if (amount < 0) { return -1; } // Check memoization table if (memo[amount] != -2) { return memo[amount]; } int minCoins = Integer.MAX_VALUE; for (int coin : coins) { int result = solve(coins, amount - coin, memo); // If a solution exists for the subproblem if (result != -1) { minCoins = Math.min(minCoins, result + 1); } } // Store result in memo table before returning memo[amount] = (minCoins == Integer.MAX_VALUE) ? -1 : minCoins; return memo[amount]; }}Complexity
Time
O(S * N) Where `S` is the number of coins and `N` is the amount. Each subproblem `solve(i)` for `i` from 1 to `N` is computed exactly once. To compute each subproblem, we iterate through all `S` coins.
Space
O(N) Where `N` is the amount. This space is used for the memoization array of size `N+1` and for the recursion stack, which can go up to depth `N`.
Trade-offs
Pros
Significantly more efficient than brute-force.
Guarantees an optimal solution by exploring each subproblem only once.
The recursive structure can be more intuitive to write than the iterative bottom-up version.
Cons
May cause a
StackOverflowErrorfor very largeamountdue to deep recursion, though the problem constraints make this unlikely.Has slightly more overhead than the bottom-up approach due to recursive function calls.
This is the iterative or 'tabulation' version of the dynamic programming solution. It builds the solution from the ground up, starting from amount 0 and iteratively computing the minimum coins for each amount up to the target. This approach avoids recursion entirely, making it very efficient and free from stack depth limitations.
Algorithm
- Create a DP array,
dp, of sizeamount + 1. - Initialize
dp[0] = 0and all other elementsdp[i]to a value representing infinity (e.g.,amount + 1). - Loop for
ifrom 1 toamount(representing the target amounts):- Inside, loop through each
coinin thecoinsarray:- If
coin <= i, it's possible to use this coin. - Update the minimum coins for amount
i:dp[i] = min(dp[i], 1 + dp[i - coin]).
- If
- Inside, loop through each
- After the loops, if
dp[amount]is still the infinity value, it means the amount is unreachable, so return -1. - Otherwise, return
dp[amount].
Walkthrough
We use an array dp of size amount + 1, where dp[i] will store the minimum number of coins needed to make change for amount i. We initialize dp[0] to 0 (0 coins for amount 0) and all other dp[i] to a sentinel value representing infinity (a good choice is amount + 1, as it's an impossible number of coins).
We then iterate from i = 1 to amount. For each i, we try to form the amount using each available coin. For every coin, if coin <= i, we can potentially form amount i by taking one coin and adding it to the optimal solution for amount i - coin. The number of coins for this combination would be 1 + dp[i - coin]. We take the minimum over all possible coins.
The final answer is stored in dp[amount]. If its value is still the initial infinity value, it means the amount cannot be formed.
import java.util.Arrays; class Solution { public int coinChange(int[] coins, int amount) { // dp[i] will store the minimum number of coins for amount i. int[] dp = new int[amount + 1]; // A value of amount + 1 represents infinity, since we can't use more coins than the amount itself. int max = amount + 1; Arrays.fill(dp, max); // Base case: 0 coins are needed for amount 0. dp[0] = 0; // Build up the dp table from amount 1 to the target amount. for (int i = 1; i <= amount; i++) { for (int coin : coins) { if (coin <= i) { // dp[i - coin] would be the min coins for the remaining amount. dp[i] = Math.min(dp[i], dp[i - coin] + 1); } } } // If dp[amount] is still 'max', it was never updated, meaning it's impossible. return dp[amount] > amount ? -1 : dp[amount]; }}Complexity
Time
O(S * N) Where `S` is the number of coins and `N` is the amount. This is due to the two nested loops: one iterating from 1 to `N` and the inner one iterating through all `S` coins.
Space
O(N) Where `N` is the amount. We need an array of size `N+1` to store the DP table.
Trade-offs
Pros
Highly efficient and robust, generally considered the standard solution.
Avoids recursion overhead and potential stack overflow errors.
Iterative logic can be easier to analyze for performance.
Cons
Can be slightly less intuitive to formulate for those more accustomed to recursive thinking.
Solutions
Solution
class Solution {public int coinChange(int[] coins, int amount) { final int inf = 1 << 30; int n = amount; int[] f = new int[n + 1]; Arrays.fill(f, inf); f[0] = 0; for (int x : coins) { for (int j = x; j <= n; ++j) { f[j] = Math.min(f[j], f[j - x] + 1); } } return f[n] >= inf ? -1 : f[n]; }}/** * @param {number[]} coins * @param {number} amount * @return {number} */ var coinChange = function (coins, amount) { const n = amount; const f = Array(n + 1).fill(1 << 30); f[0] = 0; for (const x of coins) { for (let j = x; j <= n; ++j) { f[j] = Math.min(f[j], f[j - x] + 1); } } return f[n] > n ? -1 : f[n]; };''' >>> float("inf") inf >>> float("inf") + 1 inf ''' class Solution ( object ): def coinChange ( self , coins , amount ): """ :type coins: List[int] :type amount: int :rtype: int """ dp = [ float ( "inf" )] * ( amount + 1 ) dp [ 0 ] = 0 for i in range ( 1 , amount + 1 ): for coin in coins : if i - coin >= 0 : dp [ i ] = min ( dp [ i ], dp [ i - coin ] + 1 ) return dp [ - 1 ] if dp [ - 1 ] != float ( "inf" ) else - 1 ############ class Solution : def coinChange ( self , coins : List [ int ], amount : int ) -> int : dp = [ amount + 1 ] * ( amount + 1 ) dp [ 0 ] = 0 for coin in coins : for j in range ( coin , amount + 1 ): dp [ j ] = min ( dp [ j ], dp [ j - coin ] + 1 ) return - 1 if dp [ - 1 ] > amount else dp [ - 1 ]class Solution {public: int coinChange(vector<int> &coins, int amount) { int n = amount; int f[n + 1]; memset(f, 0x3f, sizeof(f)); f[0] = 0; for (int x : coins) { for (int j = x; j <= n; ++j) { f[j] = min(f[j], f[j - x] + 1); } } return f[n] > n ? -1 : f[n]; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.