What is the time complexity of Coin Change?

The optimal solution has a time complexity of O(n * amount).

What is the space complexity of Coin Change?

The space complexity is O(amount).

What data structures are used to solve Coin Change?

This problem uses Dynamic Programming. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Coin Change?

Insight 1: The problem exhibits optimal substructure; the solution to a larger problem can be constructed from solutions to smaller subproblems. This makes Dynamic Programming a suitable approach. Insight 2: We can build a table (dp array) where `dp[i]` represents the minimum number of coins needed to make up the amount `i`.

Which companies ask LeetCode 322. Coin Change in interviews?

This problem is frequently asked at Accenture, Affirm, Agoda, Airbnb, Atlassian and 24 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Coin Change - LeetCode 322 Solution

Coin Change - Complete Solution Guide

Coin Change is LeetCode problem 322, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1 . You may assume that you have an infinite number of each kind of coin. Example 1: Input: coins = [1,2,5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1 Example 2: Input: coins = [2], amount = 3 O

Detailed Explanation

The Coin Change problem asks us to find the minimum number of coins needed to make up a given target amount, given a set of coin denominations. We are allowed to use an unlimited number of each coin denomination. If it's impossible to make up the amount with the given coins, we should return -1. If the amount is 0, we return 0.

Solution Approach

The solution utilizes dynamic programming with a bottom-up approach. We create a `dp` array of size `amount + 1`. `dp[i]` stores the minimum number of coins needed to reach amount `i`. The base case is `dp[0] = 0`. We iterate through each coin denomination and, for each coin, iterate through all amounts from the coin value up to the target amount. For each amount `a`, we check if using the current coin would result in a smaller number of coins than the current value of `dp[a]`. If it does, we update `dp[a]` with the new minimum value. Finally, we return `dp[amount]` if it's less than or equal to `amount`; otherwise, we return -1, indicating that the amount cannot be made up from the given coins.

Step-by-Step Algorithm

Step 1: Initialize a `dp` array of size `amount + 1` with a large value (e.g., `amount + 1`) to represent infinity. This indicates that initially, we don't know how many coins are needed for each amount.
Step 2: Set `dp[0] = 0`, as it requires 0 coins to make up an amount of 0.
Step 3: Iterate through each coin denomination in the `coins` array.
Step 4: For each coin, iterate through the amounts from `coin` to `amount` (inclusive).
Step 5: For each amount `a`, check if using the current coin can reduce the number of coins needed. This is done by comparing `dp[a]` with `dp[a - coin] + 1`. `dp[a - coin]` represents the minimum coins to reach `a - coin`, and adding 1 represents using the current coin.
Step 6: If `dp[a - coin] + 1 < dp[a]`, update `dp[a]` with `dp[a - coin] + 1`. This means we've found a better way to make up the amount `a`.
Step 7: After iterating through all coins and amounts, check the value of `dp[amount]`. If it's still the initial large value (indicating that we never found a way to make up the amount), return -1. Otherwise, return `dp[amount]`.

Key Insights

Insight 1: The problem exhibits optimal substructure; the solution to a larger problem can be constructed from solutions to smaller subproblems. This makes Dynamic Programming a suitable approach.
Insight 2: We can build a table (dp array) where `dp[i]` represents the minimum number of coins needed to make up the amount `i`.
Insight 3: Initialize the dp array with a large value (amount + 1) representing infinity to handle cases where an amount cannot be made up from the available coins. `dp[0]` is initialized to 0 because no coins are needed to make up an amount of 0.

Complexity Analysis

Time Complexity: O(n * amount)

Space Complexity: O(amount)

Topics

This problem involves: Dynamic Programming.

Companies

Asked at: Accenture, Affirm, Agoda, Airbnb, Atlassian, BlackRock, Capgemini, Capital One, ConsultAdd, Datadog, Deloitte, EPAM Systems, Geico, Infosys, Intuit, J.P. Morgan, Juniper Networks, Mastercard, Netflix, Nvidia, PayPal, Pinterest, SAP, Salesforce, Samsung, ServiceNow, Walmart Labs, Zoho, tcs.

Coin Change | LeetCode 322

Medium

Dynamic Programming

Time: O(n * amount)Space: O(amount)

Solution Code

Available in:

class Solution {
    public int coinChange(int[] coins, int amount) {
        int INF = amount + 1;
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++) dp[i] = INF;
        dp[0] = 0;
        for (int coin : coins) {
            for (int a = coin; a <= amount; a++) {
                if (dp[a - coin] + 1 < dp[a]) {
                    dp[a] = dp[a - coin] + 1;
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 322: Coin Change - Detailed explanation and solution approaches.

Topics

Dynamic Programming

Companies

AccentureAffirmAgodaAirbnbAtlassianBlackRockCapgeminiCapital One

Stats

Difficulty:Medium

Languages:4

Companies:29

Problem #:322

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

7 steps

1
Step 1: Initialize a `dp` array of size `amount + 1` with a large value (e.g., `amount + 1`) to represent infinity. This indicates that initially, we don't know how many coins are needed for each amount.
2
Step 2: Set `dp[0] = 0`, as it requires 0 coins to make up an amount of 0.
3
Step 3: Iterate through each coin denomination in the `coins` array.
4
Step 4: For each coin, iterate through the amounts from `coin` to `amount` (inclusive).
5
Step 5: For each amount `a`, check if using the current coin can reduce the number of coins needed. This is done by comparing `dp[a]` with `dp[a - coin] + 1`. `dp[a - coin]` represents the minimum coins to reach `a - coin`, and adding 1 represents using the current coin.
6
Step 6: If `dp[a - coin] + 1 < dp[a]`, update `dp[a]` with `dp[a - coin] + 1`. This means we've found a better way to make up the amount `a`.
7
Step 7: After iterating through all coins and amounts, check the value of `dp[amount]`. If it's still the initial large value (indicating that we never found a way to make up the amount), return -1. Otherwise, return `dp[amount]`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n * amount)

💾

Space Complexity

O(amount)

📝

Why?

The time complexity is determined by the nested loops, where the outer loop runs 'n' times (number of coins) and the inner loop runs at most 'amount' times. The space complexity comes from the `dp` array of size `amount + 1`.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Recursion with Memoization

A recursive approach can also be used with memoization to avoid redundant calculations. This approach directly translates the problem's recurrence relation into code.

Time: O(n * amount)Space: O(amount), due to the memoization table (dp array) and recursion call stack in the worst case.

Trade-offs: The recursive approach with memoization is conceptually similar to the dynamic programming approach, but it can be slightly less efficient due to the overhead of recursive calls. However, it might be more intuitive for some to understand.

Greedy Approach

A greedy approach might seem tempting at first, where we always choose the largest coin denomination that is less than or equal to the remaining amount. However, this approach does not always guarantee an optimal solution.

Time: Variable, can be much faster if greedy works, but potentially very slow if not.Space: O(1)

Trade-offs: Greedy approach is simpler to implement, but it's not guaranteed to find the optimal solution for all coin denominations. It might be suitable if you know that the coin denominations have certain properties that make the greedy approach optimal (e.g., US currency).

✨

Key Insights

1Insight 1: The problem exhibits optimal substructure; the solution to a larger problem can be constructed from solutions to smaller subproblems. This makes Dynamic Programming a suitable approach.
2Insight 2: We can build a table (dp array) where `dp[i]` represents the minimum number of coins needed to make up the amount `i`.
3Insight 3: Initialize the dp array with a large value (amount + 1) representing infinity to handle cases where an amount cannot be made up from the available coins. `dp[0]` is initialized to 0 because no coins are needed to make up an amount of 0.

📚

Key Terms Explained

For Students

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Edge Cases

Edge case 1: `amount = 0`. The solution correctly handles this case by initializing `dp[0] = 0` and returning it if the main loop completes without changing this value.
Edge case 2: No combination of coins can make up the amount. The solution handles this by initializing the `dp` array with a large value (`amount + 1`). If `dp[amount]` remains greater than `amount` after the iterations, it means that no valid combination was found, and the solution returns -1.
Edge case 3: `coins` array is empty. While the prompt states `1 <= coins.length <= 12`, it's good practice to consider this. The algorithm will correctly initialize `dp` array and return -1, since the nested loops will not be executed.
Edge case 4: A coin denomination is larger than the amount. The inner loop `for (int a = coin; a <= amount; a++)` will simply not execute for amounts smaller than that coin.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not initializing the `dp` array correctly. Failing to initialize `dp[0] = 0` or not setting the other elements to a large value to represent infinity can lead to incorrect results.

✗Common mistake 2: Incorrectly updating the `dp` array. The condition `dp[a - coin] + 1 < dp[a]` must be checked to ensure that we're only updating `dp[a]` with a smaller number of coins.

✗Common mistake 3: Failing to handle the case where the amount cannot be made up. Returning -1 when `dp[amount]` is still the initial large value is crucial.

✗Common mistake 4: Not considering all possible combinations of coins. It is vital to loop through all coins and consider each for every possible amount.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Point-of-sale systems. Determining the minimum number of bills and coins to give as change to a customer.

🏦Real-world scenario 2: Inventory management. Optimizing the number of items to stock to meet demand, where each item has a different cost and value.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Start with recursion, then memoize. The hardest part is identifying the state. Ask yourself: "What information do I need to make the current decision?"

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Forgetting base cases or initializing the DP array incorrectly. Start by solving the smallest subproblems.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 21, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 14

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 7

❓

Frequently Asked Questions

How do I identify if a problem needs dynamic programming?

DP problems typically have: 1) Overlapping subproblems (same calculation repeated), 2) Optimal substructure (optimal solution uses optimal solutions to subproblems). Look for keywords like "minimum/maximum," "count ways," "is it possible," or "longest/shortest."

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Coin Change"?

For this medium-level Dynamic Programming problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether standard techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?