21. Coin Change
mediumAsked at RevolutFind the minimum number of coins to make a target amount with unlimited supply, a Revolut staple that mirrors choosing the minimum number of pre-funded liquidity buckets to satisfy a payout.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
Given an integer array coins of denominations and an integer amount, return the fewest number of coins needed to make up that amount. If it cannot be made, return -1.
Constraints
1 <= coins.length <= 121 <= coins[i] <= 2^31 - 10 <= amount <= 10^4
Examples
Example 1
coins=[1,2,5], amount=113Example 2
coins=[2], amount=3-1Approaches
1. Plain recursion
Try every coin at every step; return min coin count.
- Time
- O(coins^amount)
- Space
- O(amount)
function f(rem){ if (rem===0) return 0; let best = Infinity; for (const c of coins) if (rem-c>=0) best = Math.min(best, 1 + f(rem-c)); return best; }Tradeoff:
2. Bottom-up DP
dp[i] = fewest coins to reach amount i; dp[i] = min(dp[i-c]+1) for each coin c. Returns -1 if dp[amount] stayed at Infinity.
- Time
- O(amount * coins)
- Space
- O(amount)
function coinChange(coins, amount){
const dp = new Array(amount+1).fill(Infinity);
dp[0] = 0;
for (let i = 1; i <= amount; i++)
for (const c of coins)
if (i - c >= 0) dp[i] = Math.min(dp[i], dp[i-c]+1);
return dp[amount] === Infinity ? -1 : dp[amount];
}Tradeoff:
Revolut-specific tips
Revolut frames this as a payout-bucket selection problem — they want you to mention that real liquidity systems use integer minor units to avoid the floating-point comparison bugs that wreck DP solutions.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.