Loading problem…
Given an integer array coins and an integer amount, return the fewest number of coins needed to make up that amount. Return -1 if impossible.
Example 1
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1 uses 3 coins. No combination of 2 coins reaches 11 (the largest is 5 + 5 = 10), so 3 is the fewest.
Example 2
Input: coins = [2], amount = 3
Output: -1
Explanation: Any number of 2-coins adds up to an even amount, so the odd amount 3 can never be made. The answer is -1.
Example 3
Input: coins = [1], amount = 0
Output: 0
Explanation: An amount of 0 needs no coins at all.
Model the problem as a graph: each amount `0..amount` is a node, and there's an edge from `a` to `a + c` for each coin `c`. Then "minimum coins" becomes "shortest path from `0` to `amount`" — exactly what BFS computes.
Run checks all cases above. Submit evaluates all test cases.