Coin Change

Frequently Asked at Salesforce OA — Reported repeatedly in Salesforce HackerRank OAs (2024-2026).

Problem Statement

You are given an integer array coins representing coin denominations and an integer amount representing a total amount of money. Return the fewest number of coins needed to make up that amount. If it is impossible, return -1. You may assume an infinite supply of each kind of coin.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1.

Example 2:

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

Example 3:

Input: coins = [1], amount = 0
Output: 0

Constraints:

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

Difficulty: Medium LC: 322 Round: Technical R1

---

Pattern Recognition

• What is the input structure? An array of coin denominations and a target amount.
• What are we optimizing? Minimum coin count.
• What pattern does this fit? 1D DP, unbounded knapsack (coins can be reused).
• Why does this pattern fit? dp[i] depends on dp[i - coin] for each coin, a classic unbounded-knapsack recurrence.

A greedy approach (always pick the largest coin) fails for denominations like [1, 3, 4] when amount = 6: greedy gives 4 + 1 + 1 = 3 coins, but optimal is 3 + 3 = 2 coins.

---

Approach

Brute Force — Recursion

For each amount, try each coin and recurse.

minCoins(amount):
    if amount == 0: return 0
    if amount < 0: return infinity
    return 1 + min(minCoins(amount - c) for c in coins)

Time: Exponential. Space: O(amount) recursion. Why insufficient: Massive repeated subproblems.

Optimal — Bottom-Up DP

Key Insight: dp[i] = min coins for amount i. Each amount can be reached by picking one coin c and using dp[i - c] coins for the rest. Bottom-up fills dp from 0 to amount.

Step-by-step:

1. Create dp[0..amount], initialize all to Infinity.
2. dp[0] = 0.
3. For i from 1 to amount:
   • For each coin c:
     • If i - c >= 0 and dp[i - c] != Infinity: dp[i] = min(dp[i], dp[i - c] + 1).
4. Return dp[amount] if finite else -1.

Time: O(amount * coins.length). Space: O(amount).

---

Walkthrough

Trace on coins = [1, 2, 5], amount = 11:

Initial: dp = [0, Inf, Inf, ..., Inf] (size 12).

i	options	dp[i]
1	dp[0]+1=1	1
2	dp[1]+1=2, dp[0]+1=1	1
3	dp[2]+1=2, dp[1]+1=2	2
4	dp[3]+1=3, dp[2]+1=2	2
5	dp[4]+1=3, dp[3]+1=3, dp[0]+1=1	1
6	dp[5]+1=2, dp[4]+1=3, dp[1]+1=2	2
7	dp[6]+1=3, dp[5]+1=2, dp[2]+1=2	2
8	dp[7]+1=3, dp[6]+1=3, dp[3]+1=3	3
9	dp[8]+1=4, dp[7]+1=3, dp[4]+1=3	3
10	dp[9]+1=4, dp[8]+1=4, dp[5]+1=2	2
11	dp[10]+1=3, dp[9]+1=4, dp[6]+1=3	3

Answer: 3.

---

Implementation

TypeScript

function coinChange(coins: number[], amount: number): number {
    // dp[i] = min coins to make amount i. Infinity = unreachable.
    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 - c] + 1 < dp[i]) {
                dp[i] = dp[i - c] + 1;
            }
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount];
}

C++

#include <vector>
#include <algorithm>
#include <climits>

int coinChange(std::vector<int>& coins, int amount) {
    // Use amount + 1 as a sentinel (guaranteed larger than any valid count).
    std::vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;

    for (int i = 1; i <= amount; i++) {
        for (int c : coins) {
            if (i - c >= 0) {
                dp[i] = std::min(dp[i], dp[i - c] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

Watch out:

1. INT_MAX + 1 overflow in C++. Either use amount + 1 as the "unreachable" sentinel (always valid because any achievable amount uses at most amount coins of value 1), or guard with dp[i-c] != INT_MAX.
2. amount == 0 — dp[0] = 0, return 0 immediately.
3. Greedy temptation. Do not use greedy ("largest coin first"). It fails on non-canonical denominations.

---

Complexity Analysis

	Time	Space
Brute Force	Exponential	O(amount)
Optimal (DP)	O(amount * coins)	O(amount)

Bottleneck: You fill every dp[i] for i from 1 to amount, each requiring a scan over coins.

---

Edge Cases

1. amount == 0 — 0 coins.
2. No solution (coins = [2], amount = 3) — return -1.
3. Single coin = 1 — always solvable, dp[amount] = amount.
4. Coin larger than amount — that coin contributes nothing; ignore.
5. Duplicate coin denominations — fine, just wasteful. Dedupe for efficiency if you want.

---

Related Problems

• LC 518 — Coin Change II — Count the number of combinations (not min coins). 1D DP over sum, outer loop on coins.
• LC 377 — Combination Sum IV — Count ordered sequences (permutations). Outer loop on sum.
• LC 279 — Perfect Squares — Same pattern with squares as "coins".
• LC 983 — Minimum Cost for Tickets — DP variant with time-window tickets.

---

Interview Strategy Notes

Very common Salesforce Technical R1 problem. Budget 15-20 minutes. The interviewer may follow up with:

• "Can you return the actual coin list?" (Reconstruct by walking back through dp.)
• "What if coins could only be used once?" (0/1 knapsack — outer loop becomes coins, inner loop is sum decreasing.)

Practice both the canonical version and the reconstruction variant.

---

What is Expected at Each Level

Junior: Writes recursive solution, TLEs, gets to memoized solution with guidance. May skip edge cases.

Mid-level: Writes bottom-up DP directly. Explains why greedy fails with a counter-example. Handles edge cases.

Senior: Discusses the complexity precisely, walks through the DP recurrence as a shortest-path problem on a DAG (which it is), mentions BFS as an alternative O(amount * coins) solution, and handles follow-ups cleanly.