Coin Change

Coin Change

What is this problem about?

The Coin Change interview question is one of the most famous dynamic programming problems. You are given an array of coin denominations and a target amount. You need to find the minimum number of coins required to make up that amount. If the amount cannot be made up by any combination of the coins, return -1. You have an infinite supply of each coin type.

Why is this asked in interviews?

This problem is asked by almost every major tech company, including Google, Amazon, and Apple. It is the quintessential Dynamic Programming interview pattern. It tests whether a candidate can move beyond "greedy" thinking (which doesn't work here) and instead build a solution based on subproblems. It also evaluates your ability to handle edge cases like an amount of 0 or an unreachable amount.

Algorithmic pattern used

The problem is solved using Bottom-Up Dynamic Programming. We create a dp array where dp[i] represents the minimum coins needed to make amount i.

• Base case: dp[0] = 0.
• Transition: For each amount i and each coin c, dp[i] = min(dp[i], dp[i - c] + 1). This approach ensures we find the global minimum by exploring all possible last coins used for every intermediate amount.

Example explanation

Coins: [1, 2, 5], Amount: 11

1. dp[0] = 0
2. dp[1]: Use coin 1. dp[0] + 1 = 1.
3. dp[2]: Use coin 2. dp[0] + 1 = 1. (Better than two 1s).
4. dp[5]: Use coin 5. dp[0] + 1 = 1.
5. dp[6]: Use coin 5 + dp[1]. 1 + 1 = 2.
6. dp[11]: Use coin 5 + dp[6]. 1 + 2 = 3. The 3 coins are [5, 5, 1].

Common mistakes candidates make

• Greedy approach: Trying to always take the largest coin first. (e.g., for coins [1, 3, 4] and amount 6, greedy takes 4, 1, 1 [3 coins], but the optimal is 3, 3 [2 coins]).
• Initialization: Not initializing the dp array with a value larger than the target (like amount + 1 or Infinity).
• Loop Order: While the order of loops (coins then amount vs amount then coins) doesn't matter for minimum coins, it matters for other variations like "number of ways."

Interview preparation tip

Be prepared to explain the time complexity (O(amount * coins)) and space complexity (O(amount)). Also, practice the "Top-Down with Memoization" version, as some interviewers prefer seeing the recursive thought process first.