The coin change problem is a classic leet coding challenge often encountered in technical interviews. The problem asks:
Given an array of coin denominations and a target amount, find the fewest number of coins needed to make up that amount. If it's not possible, return -1. You can use each coin denomination infinitely many times.
Here are multiple ways to solve the Coin Change problem in Kotlin, with detailed explanations and code examples. I'll present two distinct approaches:
- Dynamic Programming (Bottom-Up approach)
- Recursive Approach with Memoization (Top-Down)
Approach 1: Dynamic Programming (Bottom-Up)
Idea:
- Build an array
dpwhere eachdp[i]indicates the minimum number of coins required for the amounti. - Initialize the array with a large number (representing infinity).
- The base case is
dp[0] = 0.
Steps:
- For each amount from
1toamount, try every coin denomination. - Update
dp[i]if using the current coin leads to fewer coins than the current value.
Kotlin Solution:
fun coinChange(coins: IntArray, amount: Int): Int {
val max = amount + 1
val dp = IntArray(amount + 1) { max }
dp[0] = 0
for (i in 1..amount) {
for (coin in coins) {
if (coin <= i) {
dp[i] = minOf(dp[i], dp[i - coin] + 1)
}
}
}
return if (dp[amount] > amount) -1 else dp[amount]
}
// Usage:
fun main() {
println(coinChange(intArrayOf(1, 2, 5), 11)) // Output: 3
println(coinChange(intArrayOf(2), 3)) // Output: -1
println(coinChange(intArrayOf(1), 0)) // Output: 0
}
Time Complexity: O(amount * coins.length)
Space Complexity: O(amount)
Approach 2: Recursive Approach with Memoization (Top-Down)
Idea:
- Define a recursive function
solve(remainingAmount)that returns the minimum coins required. - Use memoization to store previously computed results, avoiding redundant calculations.
Steps:
- For each call, explore all coin denominations and recursively find solutions.
- Cache results to avoid recomputation.
Kotlin Solution:
fun coinChangeMemo(coins: IntArray, amount: Int): Int {
val memo = mutableMapOf<Int, Int>()
fun solve(rem: Int): Int {
if (rem < 0) return -1
if (rem == 0) return 0
if (memo.containsKey(rem)) return memo[rem]!!
var minCoins = Int.MAX_VALUE
for (coin in coins) {
val res = solve(rem - coin)
if (res >= 0 && res < minCoins) {
minCoins = res + 1
}
}
memo[rem] = if (minCoins == Int.MAX_VALUE) -1 else minCoins
return memo[rem]!!
}
return solve(amount)
}
// Usage:
fun main() {
println(coinChangeMemo(intArrayOf(1, 2, 5), 11)) // Output: 3
println(coinChangeMemo(intArrayOf(2), 3)) // Output: -1
println(coinChangeMemo(intArrayOf(1), 0)) // Output: 0
}
Time Complexity: O(amount * coins.length)
Space Complexity: O(amount) (stack space + memoization map)
Quick Comparison:
| Approach | Time Complexity | Space Complexity | When to Use? |
|---|---|---|---|
| Dynamic Programming (Bottom-Up) | O(amount * coins.length) |
O(amount) |
Optimal, preferred for efficiency |
| Recursive with Memoization | O(amount * coins.length) |
O(amount) |
Easy to understand recursion |
Edge Cases Handled:
- If
amountis0, both solutions immediately return0. - If the amount cannot be composed by given coins, they return
-1.
Summary:
- Dynamic Programming is the optimal, most widely used solution for this problem.
- Recursive Approach with memoization demonstrates understanding of recursion and memoization principles.
You can select either based on clarity, readability, or efficiency needs. The DP solution is highly recommended in competitive programming or technical interviews for optimal performance.
Thanks for reading! 🎉 I'd love to know what you think about the article. Did it resonate with you? 💭 Any suggestions for improvement? I’m always open to hearing your feedback to improve my posts! 👇🚀. Happy coding! 💻✨
Posts
