Updated Coin Change Problem (LeetCode 322)

The coin change problem is one of those questions that keeps showing up in coding interviews at top tech companies, and for good reason. It’s a clean, well-defined problem that forces you to think beyond brute force and reason about optimal substructure. If you’re serious about landing a role at a FAANG or Tier-1 company, this is a problem you simply cannot afford to skip.

What makes it particularly valuable is how naturally it demonstrates dynamic programming concepts. It teaches you to break a larger problem into smaller, overlapping subproblems and build the solution bottom-up, a skill that directly applies to many other dynamic programming interview questions.

In this article, we will walk you through the problem statement, work through examples, explore solution approaches step by step, and break down the time and space complexity so you know exactly what to expect in an interview setting.

Problem Statement

A coin change problem and its solution are given in this section.

Problem: With a list of coin denominations and a target amount, find the minimum number of coins needed to make up that amount. If it’s not possible, return -1.

Coins available: [1, 5, 10]

Target Amount: 11

Min coins needed: 2

The following DP table presents coin change details of input, output, selections available.

Explanation: A row indicates one coin denomination. Each column is the amount from 0 to the target. Value in a cell (coin, i) shows the number of coins needed if you use that coin to reach amount i — specifically, dp[i – coin] + 1. The final dp[i] row at the bottom shows the minimum across all coin rows at each column.

The blue cells at the bottom are the optimal decision path backwards from the target, and the green cell gives the final value. Cells with opacity show suboptimal choices at that amount. Toggle coins on/off or drag the target slider to change the DP table.

Constraints

The coin change problem constraints are about the minimum coins or combinations to make a target amount using given denominations. Common constraints include positive integer denominations, a non-negative target amount, and a time complexity.

The figure illustrates constraints in coin change problems.

The coin change constraints are:

• Number of coins (n): Coin size set or denomination decides the number of iterations for the inner DP loop. For 12 coins, brute-force methods can be used. When the coin set is more than 100, then the coin array must be deduplicated.
• Coin value range (v): This is an important constraint and must be v ≥ 1. With a zero-value coin, infinite loops are formed in greedy and unbounded DP. The top bound of coin value is relative to T, and if all coins are more than the target, the answer is −1.
• Target amount (T): Drives time O(n × T) and space O(T). LeetCode version caps T at 10⁴. At T = 10⁶, a 1 M-entry array is formed with millions of slow inner-loops passes.

Example Walkthrough

An example of the coin change problem is given as follows:

Target amount: 8

Coin denominations: 1,3,5

Step-by-step explanation:

Diagram of target amount, available coins, combination results.

Also Read: Possible To Achieve Target Sum Problem

Understanding the Problem

In the coin change problem, the goal is to meet the target amount by using the fewest coins possible. In the above example, the coins given are of denominations [1,3,5] and the target is 8.

Possible combinations to meet the target are:

8 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 → 8 coins

8 = 3 + 3 + 1 + 1 → 4 coins

8 = 5 + 1 + 1 + 1 → 4 coins

8 = 3 + 5 → 2 coins Best combination

Minimizing coins means increased efficiency since fewer coins allow for simpler and faster solutions. This is important in practical applications when payment is made with minimum coins. Multiple combinations are possible, but the solution with the fewest coins is preferred.

Key observations:

• In ATMs, it may not be possible to handle odd and fractional amounts such as 103. In such cases, the ATM flashes a message on the screen that specific denominations only are available.
• In cash registers, it may not be possible to pay fractional amounts such as 103.53. The store then rounds off the amount to the nearest dollar.
• Coins can be used multiple times, and the order of coins does not matter.

Also Read: How to Crack FAANG Coding Interviews: Practice Strategy & Questions

Approaches to Solve the Coin Change Problem

Several approaches are available to solve the coin change problem. These include brute force recursion, recursion with memorization, and dynamic programming.

The following figure illustrates the workflow of the three main coin change problem approaches.

Approach 1: Brute Force Recursion

Also called the greedy algorithm, it presents the locally optimal choice or the largest coin for every step, leading to the optimum combination.

Code snippet in Java for brute force recursion.

int coinChange(int[] coins, int amount) {
    if (amount == 0) return 0;
    if (amount < 0)  return Integer.MAX_VALUE;
    int min = Integer.MAX_VALUE;
    for (int coin : coins) {
        int res = coinChange(coins, amount - coin);
        if (res != Integer.MAX_VALUE) {
            min = Math.min(min, res + 1);
        }
    }
    return min;
}

Complexity table and explanation is:

Approach 2: Memoization

The memoization approach in the coin change problem removes the need for recomputing the same subproblems. The approach increases the efficiency of recursion by storing computed results in a cache and reusing them when needed.

The memoization in Java is given below. In the code, results are stored in “return m[a] = (min == Integer.MAX_VALUE) ? -1 : min;” and reused when needed.

int f(int[] c, int a, int[] m) {
    if (a == 0)  return 0;
    if (a < 0)   return -1;
    if (m[a] != 0) return m[a];
    int min = Integer.MAX_VALUE;
    for (int x : c) {
        int r = f(c, a - x, m);
        if (r >= 0) min = Math.min(min, r + 1);
    }
    return m[a] = (min == Integer.MAX_VALUE) ? -1 : min;
}

Approach 3: Dynamic Programming

The dynamic programming approach in the coin change problem uses optimal substructure and overlapping subproblems. Smaller amounts are solved in combination to reach the target amount. The method iteratively solves the problem for each amount from 0 until the target amount is reached, and the results are stored in a table to avoid redundant calculations.

The code snippet with dynamic programming for the coin change problem is given below.

int f(int[] c, int a, int[] m) {
    if (a == 0)  return 0;
    if (a < 0)   return -1;
    if (m[a] != 0) return m[a];
    int min = Integer.MAX_VALUE;
    for (int x : c) {
        int r = f(c, a - x, m);
        if (r >= 0) min = Math.min(min, r + 1);
    }
    return m[a] = (min == Integer.MAX_VALUE) ? -1 : min;
}

Step explanation. Each cell uses previously computed values. The minimum coins for all amounts from 0 to target is given to reach the final answer step by step.

The following figure illustrated the DP coin change problem with coin value [1,2,5] and target 8.

Complexity Analysis

The following table breaks down the key technical differences between the three strategies of coin change, dynamic programming, memoization, and brute force recursion.

Dynamic programming is the most efficient solution for the coin change problem as it breaks the problem into optimal subproblems. Results are stored in overlapping subproblems to avoid redundant calculations.

Edge Cases

Some edge cases for impossible-to-achieve values through any combination are important. Some edge cases of the coin change problem are:

Coin Change Problem Target amount equals zero: The minimum number of coins is 0. Coins are not needed to make the amount 9. It is the base case in dynamic programming and the recursive approaches for the coin change problem.

All coins greater than the amount: Then the problem does not have a solution. Smaller amounts with larger coins cannot be formed.

No possible combination: Then, the combinations to form the target amount are not possible. The problem is different when all coins are smaller in value than the target amount.

Very large target values: When the target amount is very large, such as 106, then the coin change problem computation is very slow. Performance and memory are insufficient.

Common Mistakes

Some common mistakes in coin change problem, are present in the following table.:

Interview Tips

Software engineer interviews see questions on theory and practical code implementation. Interviewers want to evaluate how you interpret a problem and write efficient code. Brevity, simplicity, and security are important in answering coding interview problems. The following strategies are recommended.

• Coding practice is critical, and you must access question banks, practice questions, and write the code in an IDE.
• Understand what interviewers are evaluating.
• If the intent is not clear, clarify your doubts and ask clarifying questions.
• Break down large problems into smaller steps.
• Declare any assumptions when data or conditions are not mentioned, and explain performance conditions.
• Explain execution plans since interviewers are interested in knowing how you implement them.
• You will be asked about data structures for massive databases, so read about them.
• Edge cases are important, so prepare for them.
• Scenario-based questions are often asked after the initial questions, so prepare for different scenarios.
• Prepare with the STAR method, and attend mock interviews.

Conclusion

The blog examined the coin change problem and three main approaches: brute force recursion, recursion with memorization, and dynamic programming to solve the problem. The coin change problem is to find the minimum number of coins for a target value, with an infinite supply of specific coin denominations.

The coin change problem is critical in real-world applications such as ATMs, banking and financial transactions, and in resource allocation. Complexity analysis of the three approaches was examined, and the dynamic programming method is the most efficient solution for the coin change problem, as it breaks the problem into optimal subproblems.

The memoization approach in the coin change problem removes the need for recomputing the same subproblems. The brute force approach presents the locally optimal choice or the largest coin for every step, leading to the optimum combination.

Technical coding interviews invariably have questions on the coin change problems. You are evaluated on your logic, reasoning, and coding expertise. Read about edge cases, variations in the coin change problem, and practice coding in an IDE.

Want to crack tech interviews and land a job with top tech firms? Come to Interview Kickstart

You’ve worked through the ‘Coin Change Problem (LeetCode 322): DP Solution and Explanation’ guide. Now it’s time to prepare like a serious coding engineer aiming to land a job with leading tech firms.

The Tech Mock Interview prep program by Interview Kickstart is designed by FAANG+ engineering leaders who know exactly what top companies expect. The program covers Airbnb interview questions, and answers and other interview-relevant topics that matter in real hiring loops.

You get personalized 1:1 technical coaching, homework guidance, and detailed solution discussions. You’ll also go through mock interviews with Silicon Valley engineers in real-world simulated environments, followed by structured, actionable feedback to sharpen your performance.

Beyond technical prep, Interview Kickstart supports your career growth with resume building, LinkedIn optimization, personal branding guidance, and live behavioral workshops.

FAQs: Coin Change Problem

Q1. What is the coin change problem?

The coin change problem is about finding the minimum number of coins for a target value, with an infinite supply of specific coin denominations.

Q2. Why is dynamic programming used?

Dynamic programming is used to solve coin change problems with overlapping subproblems and optimal substructure by storing and reusing previously computed results.

Q3. What happens if no solution exists?

If no solution to the coin change problem is computed, then the target cannot be achieved with the given inputs.

Q4. What is the time complexity?

Every subproblem is solved once, making it efficient compared to recursion.

References

• GitHub FAANG-Coding-Interview-Questions
• Daily Dev Fun Coding Problems: From Easy to Hard

Recommended Reads:

• Best Companies to Work For Software Engineer (And Top Cities)
• 20 Essential Interview Puzzles for Software Engineers in 2026 (With Solutions)
• Software Engineer Job Levels at Google
• Number Of Ways To Make Change Problem
• Possible To Achieve Target Sum Problem