# The Coin Vault

> Exact change only - and you want to use as few coins as possible.

Canonical URL: <https://datadriven.io/problems/the_coin_vault>

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Given a target amount and a list of coin denominations, return the minimum coins needed using a greedy strategy: repeatedly take the largest coin that does not exceed the remaining amount. Return -1 if the greedy approach cannot make exact change.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **greedy algorithm design** and the ability to recognize when greedy works versus when dynamic programming is needed. It probes understanding of algorithmic strategy selection and edge-case handling for impossible solutions.

> **Trick to Solving**
>
> Sort denominations in descending order, then greedily take as many of the largest coin as possible before moving to the next. This greedy approach works for standard currency denominations but can fail for arbitrary denominations. The problem specifies greedy, so use it.

---

### Break down the requirements

#### Step 1: Sort coins in descending order

Processing largest denominations first minimizes the total coin count under the greedy strategy.

#### Step 2: Greedily subtract the largest possible coin

For each denomination, use as many as fit into the remaining amount via integer division.

#### Step 3: Check for exact change

After processing all denominations, if the remaining amount is not zero, return -1.

---

### The solution

**Greedy coin selection with descending denominations**

```python
def min_coins(amount: int, coins: list) -> int:
    sorted_coins = sorted(coins, reverse=True)
    total_coins = 0
    remaining = amount
    for coin in sorted_coins:
        if remaining <= 0:
            break
        count = remaining // coin
        total_coins += count
        remaining -= count * coin
    if remaining != 0:
        return -1
    return total_coins
```

> **Time and Space Complexity**
>
> **Time:** O(k log k) for sorting the k denominations, plus O(k) for the greedy pass.
> 
> **Space:** O(k) for the sorted copy.

> **Interviewers Watch For**
>
> Whether you mention that greedy does not always produce the optimal result for arbitrary coin sets. For example, coins [1, 3, 4] with amount 6: greedy picks 4+1+1=3 coins, but optimal is 3+3=2 coins.

> **Common Pitfall**
>
> Forgetting to handle the case where exact change is impossible. Always check whether `remaining == 0` after the loop.

---

## Common follow-up questions

- When does the greedy approach fail? _(Tests understanding of counterexamples and when DP is required.)_
- How would you solve this optimally with dynamic programming? _(Tests bottom-up DP with a table of size `amount + 1`.)_
- What is the time complexity of the DP approach? _(Tests O(amount * k) analysis where k is the number of denominations.)_
- What if the amount is 0? _(Tests edge case: 0 coins needed for amount 0.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_coin_vault)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.