Skip to main content

18. Coin Change

mediumAsked at Brex

Find the fewest coins to make a target amount — a classic unbounded knapsack DP that Brex maps to spend-limit decomposition and multi-currency rounding problems.

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

Problem

Given an array of coin denominations and an integer amount, return the fewest number of coins needed to make up that amount. Return -1 if it cannot be made.

Constraints

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

Examples

Example 1

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

Example 2

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

Approaches

1. Top-down recursion with memoization

Recursively try each coin and cache results by remaining amount.

Time
O(amount * coins.length)
Space
O(amount)
const memo = {};
function dp(rem) {
  if (rem < 0) return -1; if (rem === 0) return 0;
  if (memo[rem] !== undefined) return memo[rem];
  let best = Infinity;
  for (const c of coins) { const sub = dp(rem - c); if (sub >= 0) best = Math.min(best, sub + 1); }
  return (memo[rem] = best === Infinity ? -1 : best);
}

Tradeoff:

2. Bottom-up DP table

Build a dp array where dp[i] is the minimum coins for amount i. For each amount fill in the best answer using each coin denomination iteratively.

Time
O(amount * coins.length)
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:

Brex-specific tips

Brex asks about fintech infrastructure, multi-currency handling, and spend management algorithms. Expect LeetCode-style DSA focused on hash maps, sorting, and dynamic programming.

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 Brex interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →