Medium — Dynamic Programming | Array | Greedy
The Problem
Given an array of coin denominations and a target amount, find the minimum number of coins needed to make up that amount, or return -1 if it's impossible.
Approach
Uses dynamic programming with a bottom-up approach. We build a DP array where dp[i] represents the minimum coins needed for amount i, iterating through each coin type and updating the minimum coins required for each possible amount.
Time: O(amount × coins) · Space: O(amount)
Code
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
# Initialize the DP array with a maximum value to represent impossible cases.
dp = [float("inf")] * (amount + 1)
# Base case: It takes 0 coins to make up the amount of 0.
dp[0] = 0
# Iterate through the DP array and update the minimum number of coins needed.
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
# If dp[amount] is still float('inf'), it means it's impossible to make up the amount.
# Otherwise, dp[amount] contains the minimum number of coins needed.
return dp[amount] if dp[amount] != float("inf") else -1
Watch It Run
👁 Watch the algorithm run step by step
Open interactive visualization
Try it yourself: Open TraceLit and step through every line.
Built with TraceLit — the visual algorithm tracer for LeetCode practice.
For further actions, you may consider blocking this person and/or reporting abuse
