You are given an array of coin denominations and a target amount. Find the minimum number of coins needed to make up that amount. If it is not possible, return -1.
For example, given coins = [1, 5, 10] and amount = 12, the answer is 3 (10 + 1 + 1).
Explain your approach to solving this problem and state the time and space complexity.
How to approach it
- Hint 1
Think about building the solution for every amount from 0 up to the target.
- Hint 2
For each amount, consider every coin denomination and take the minimum.
- Hint 3
Define dp[i] as the minimum coins needed for amount i. For each coin c, dp[i] = min(dp[i], dp[i - c] + 1).
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.