Skip to main content

17. Coin Change

mediumAsked at LINE

Find the fewest coins that make up an amount — LINE uses this to test DP intuition before they push you into LINE Pay reconciliation problems.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given an integer array coins representing coin denominations and an integer amount. Return the fewest number of coins needed to make up that amount. If the amount cannot be made up by any combination, return -1. You have an infinite supply of each denomination.

Constraints

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4

Examples

Example 1

Input
coins = [1,2,5], amount = 11
Output
3

Example 2

Input
coins = [2], amount = 3
Output
-1

Approaches

1. Recursion without memo

Recurse on every denomination subtraction.

Time
O(coins^amount)
Space
O(amount)
function rec(n){
  if(n===0) return 0;
  if(n<0) return Infinity;
  let best=Infinity;
  for(const c of coins) best=Math.min(best,rec(n-c)+1);
  return best;
}

Tradeoff:

2. Bottom-up DP

dp[i] = fewest coins to make i. Initialize to Infinity, dp[0] = 0. For each i from 1 to amount, dp[i] = min(dp[i - c] + 1) over coins. Final answer is dp[amount] or -1.

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 (c <= i) dp[i] = Math.min(dp[i], dp[i - c] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff:

LINE-specific tips

At LINE, mention you would reuse the same bottom-up DP shape when computing the minimum number of LINE Pay coupons to redeem a target spend — payment-integration framing wins.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Coin Change and other LINE interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →