322. Coin Change - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Given an array of coin denominations coins and an integer amount, find the fewest number of coins required to make up that amount. You may use each coin denomination as many times as needed (infinite supply). If it is not possible to make the amount with the given coins, return -1.

What does this mean? We want the minimum count of coins that sum to the target amount. For example, if we have coins [1, 2, 5] and amount = 11, one way to make 11 is 5 + 5 + 1 using 3 coins, and another way is 5 + 2 + 2 + 2 using 4 coins. The first way uses fewer coins, so the answer is 3.

Examples

Example 1:
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: The minimum coins to make 11 are [5, 5, 1] (5 + 5 + 1 = 11), which uses 3 coins. No combination can do it in fewer than 3 coins.
Example 2:
Input: coins = [2], amount = 3
Output: -1
Explanation: We cannot make 3 with coin 2 alone. Since no combination of [2] sums to 3, the result is -1.
Example 3:
Input: coins = [1], amount = 0
Output: 0
Explanation: To make amount 0, we don't need any coins, so the answer is 0.
Example 4:
Input: coins = [2, 4], amount = 7
Output: -1
Explanation: With coin denominations 2 and 4 (both even), it's impossible to form an odd amount like 7. So the output is -1.

Constraints

1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1 (coin values are positive)
0 <= amount <= 10^4

These constraints mean we have at most 12 coin types, the coins can be large in value (up to about 2 billion), and the target amount can go up to 10,000. We have an infinite supply of each coin type. The answer will always fit in an integer (if it exists, it will be at most amount coins when using all 1-value coins, and if not possible we return -1).

Hints

Brute Force Thought: Consider the simplest approach first – try using the coins in every possible combination to reach the target. What if you subtract each coin value from the amount and solve the smaller subproblem recursively? This will explore all combinations but may be very slow. Think about why it’s slow and how you might optimize it.
Use Subproblem Results: If you want to minimize coins for amount N, notice that if you knew the answer for a smaller amount (like N - coin for some coin), you could use that to build a solution for N. This hints at a recursive relation or a dynamic programming approach. Can you define dp[x] as the answer for amount x and build up to dp[amount]?
Shortest Path Analogy: You can think of the problem as a graph or tree where each amount is a state/node and you can move from one state to another by using a coin (subtracting or adding a coin value). The problem then becomes finding the shortest path from the start to the target amount. This is a hint that Breadth-First Search (BFS) might find the minimum number of steps (coins) to reach the target.

Try to formulate a solution using these hints before reading further. The brute force will give you insight, dynamic programming will optimize it using subproblem results, and BFS offers an alternative way to think about the state space.

Brute Force Solution (Exhaustive Search)

Explanation

A brute-force approach is to try every possible combination of coins to make the amount and find the one using the fewest coins. This can be done with a recursive depth-first search (DFS) that subtracts coin values from the amount until it reaches 0 (success) or goes negative (invalid path). The recursion explores all coin choices at each step:

Recursion Tree: Start with the target amount. At each step, choose any coin and subtract it from the current amount, then recursively solve the smaller remainder. Each recursive call tries all coins again.
If the remainder becomes exactly 0, we found a valid combination of coins. Count how many coins were used in this path.
If the remainder becomes negative, that path is not valid.
Track the minimum number of coins among all valid combinations.

Example (Brute Force): Suppose coins = [1, 3, 4] and amount = 6. A brute force search would explore:

Use a 1 coin, then solve for amount 5. (Then try 1 again, etc.)
Use a 3 coin, then solve for amount 3. (Could then use 3 again to hit 0.)
Use a 4 coin, then solve for amount 2. (Then try 1 or 3 on remainder 2.) It will find combinations like [1,1,1,1,1,1] (six 1s), [3,3] (two 3s), [4,1,1], etc., and determine that [3,3] uses the fewest coins (2 coins).

Why is it slow? This approach recomputes a lot of subproblems. For example, to evaluate using a 1 coin first vs a 3 coin first, there is overlap in solving sub-amounts (like solving for amount 5 or 3 multiple times). The time complexity grows exponentially with the amount, because we branch out for each coin at each step. For larger amounts (e.g. amount = 100), this becomes infeasible.

We can implement brute force recursion to illustrate the approach, but remember that this is inefficient for large inputs. It's mainly useful to understand the problem structure or for very small amounts.

Brute Force – Python Code

Python3

. . . .

Brute Force – Java Code

Java

. . . .

Note: In the Java code, we use Integer.MAX_VALUE as a sentinel for "impossible". The coinChangeBruteforce function returns Integer.MAX_VALUE when a combination is not possible. The main method then converts that to -1 for output. This approach will timeout or stack overflow for large amount values (especially if coins contains small denominations like 1), because it explores an exponential number of possibilities.

Complexity Analysis – Brute Force

Time Complexity: Exponential, roughly O(n^m) or worse, where n is the number of coin types and m is the amount (or amount divided by smallest coin value). In the worst case (like coins=[1]), the recursion depth is amount and the branching factor is 1 (just one coin), which gives O(m) for that trivial case. But with multiple coin choices, the branching factor is >1, and the recurrence roughly T(m) = T(m-c1) + T(m-c2) + ... leads to an exponential explosion. This is infeasible for amount as large as 10,000.
Space Complexity: O(m) for the recursion call stack in the worst case (depth of recursion can be amount if we use many 1-value coins). No additional data structures of significant size are used, but the stack can get deep. For amount=10^4, a naive recursion could even crash due to recursion depth limits.

Because of the exponential time, the brute force approach is not usable for large inputs, but it establishes a foundation. We notice that many subproblems repeat. For example, computing the minimum coins for amount 7 will involve computing for 6, 5, 4, etc., in different branches multiple times. This overlapping subproblem structure is a cue to use Dynamic Programming to store results and avoid recomputation.

Dynamic Programming Approach (Efficient)

Explanation

The coin change problem exhibits overlapping subproblems and optimal substructure, which makes it a perfect candidate for dynamic programming:

Optimal Substructure: An optimal solution for amount A can be constructed from optimal solutions of smaller amounts. For example, if the best way to make A uses a coin of value c, then after using that coin, the remaining amount A-c must also be made optimally to minimize total coins.
Overlapping Subproblems: The minimum coins required for a certain remainder (say amount X) will be recalculated many times in a brute force approach. We can store those results instead of recomputing.

Idea: Define dp[x] as the minimum number of coins needed to form amount x. We want dp[amount]. We can build the dp array from 0 up to the target:

Base case: dp[0] = 0 (0 coins needed to make 0 amount).
Initial values: For all other amounts, initialize dp[x] to some large number (infinity or a sentinel value) because we haven't computed them yet.
State transition: For each amount x from 1 to amount, try using each coin c that is ≤ x. If we use coin c, then we look at dp[x - c] (the best we can do for the remainder after using this coin) and add 1 coin. So one candidate for dp[x] is dp[x-c] + 1. We take the minimum of these candidates for all coin choices. In formula:
```
dp[x] = min( dp[x - c] + 1 ) for all c in coins where x - c >= 0.
```
If no coin can make x (meaning even after trying all, dp[x] stays at the initial large value), it remains effectively "infinite" which indicates impossible.

This is a bottom-up iterative approach. Alternatively, one could do a top-down recursion with memoization, which is similar in logic: recursively compute minCoins(amount) by exploring coin choices, but cache results for each sub-amount to avoid re-computation. The bottom-up method we describe here tends to be simpler to implement and understand for this problem.

Why dynamic programming is efficient: Each smaller subproblem (like amount x) is solved once and stored. We then use those results for larger amounts. The complexity will be polynomial (product of amount and number of coin types) instead of exponential.

Dealing with impossible cases: If dp[amount] remains at the initial "infinite" value by the end, it means no combination of coins can produce that amount, so we return -1.

Greedy vs DP: It's worth noting that a greedy strategy (always taking the largest coin first) does not always yield an optimal solution for arbitrary coin systems. Greedy works for some coin sets (like typical US currency coins) but fails for others. For example, with coins [1, 3, 4] and amount 6, a greedy approach would pick 4 then 1 then 1 (total 3 coins), but the optimal is 3 + 3 (2 coins). The dynamic programming approach correctly finds 2 coins, whereas a naive greedy approach might not. Therefore, DP (or BFS) is needed for a correct general solution.

Step-by-Step Example (DP)

Let’s walk through an example to see how the DP table is built:

Example: coins = [1, 2, 5], amount = 11. We initialize an array dp of size 12 (0 through 11). Let MAX be a large sentinel value (like infinity or 10001 in this case) to denote unreachable state.

Initially:
dp[0] = 0  (base case: 0 coins needed for amount 0)
dp[1..11] = MAX  (unknown yet, use a large number as placeholder)

Now compute from 1 up to 11:

For amount = 1: We try each coin:
- Using coin 1: remainder = 1-1 = 0, dp[0] = 0, so candidate = 0 + 1 = 1 coin.
- Using coin 2: remainder = -1 (not valid).
- Using coin 5: remainder = -4 (not valid). Minimum coins for 1 is 1.
  dp[1] = 1 (one 1-coin).
For amount = 2: Try coins:
- Using 1: remainder 1, dp[1] = 1, candidate = 1 + 1 = 2.
- Using 2: remainder 0, dp[0] = 0, candidate = 0 + 1 = 1.
- Using 5: remainder -3 invalid. Minimum is 1 (using coin 2 directly).
  dp[2] = 1 (one 2-coin).
For amount = 3:
- Coin 1: remainder 2, dp[2] = 1, candidate = 1 + 1 = 2.
- Coin 2: remainder 1, dp[1] = 1, candidate = 1 + 1 = 2.
- Coin 5: invalid. Minimum is 2.
  dp[3] = 2 (e.g. 1+2).
For amount = 4:
- Coin 1: remainder 3, dp[3] = 2, candidate = 2 + 1 = 3.
- Coin 2: remainder 2, dp[2] = 1, candidate = 1 + 1 = 2.
- Coin 5: invalid. Minimum is 2.
  dp[4] = 2 (e.g. 2+2).
For amount = 5:
- Coin 1: remainder 4, dp[4] = 2, candidate = 2 + 1 = 3.
- Coin 2: remainder 3, dp[3] = 2, candidate = 2 + 1 = 3.
- Coin 5: remainder 0, dp[0] = 0, candidate = 0 + 1 = 1. Minimum is 1.
  dp[5] = 1 (one 5-coin).

At this point, our dp array looks like:
dp = [0, 1, 1, 2, 2, 1, ...] (we will continue to fill up to 11).

For amount = 6:
- Coin 1: remainder 5, dp[5] = 1, candidate = 1 + 1 = 2.
- Coin 2: remainder 4, dp[4] = 2, candidate = 2 + 1 = 3.
- Coin 5: remainder 1, dp[1] = 1, candidate = 1 + 1 = 2. Minimum is 2.
  dp[6] = 2 (e.g. 5+1).
For amount = 7:
- Coin 1: remainder 6, dp[6] = 2, candidate = 2 + 1 = 3.
- Coin 2: remainder 5, dp[5] = 1, candidate = 1 + 1 = 2.
- Coin 5: remainder 2, dp[2] = 1, candidate = 1 + 1 = 2. Minimum is 2.
  dp[7] = 2 (e.g. 5+2).
For amount = 8:
- Coin 1: remainder 7, dp[7] = 2, candidate = 2 + 1 = 3.
- Coin 2: remainder 6, dp[6] = 2, candidate = 2 + 1 = 3.
- Coin 5: remainder 3, dp[3] = 2, candidate = 2 + 1 = 3. Minimum is 3.
  dp[8] = 3 (e.g. 5+2+1 or 2+2+2+2).
For amount = 9:
- Coin 1: remainder 8, dp[8] = 3, candidate = 3 + 1 = 4.
- Coin 2: remainder 7, dp[7] = 2, candidate = 2 + 1 = 3.
- Coin 5: remainder 4, dp[4] = 2, candidate = 2 + 1 = 3. Minimum is 3.
  dp[9] = 3 (e.g. 5+2+2).
For amount = 10:
- Coin 1: remainder 9, dp[9] = 3, candidate = 3 + 1 = 4.
- Coin 2: remainder 8, dp[8] = 3, candidate = 3 + 1 = 4.
- Coin 5: remainder 5, dp[5] = 1, candidate = 1 + 1 = 2. Minimum is 2.
  dp[10] = 2 (e.g. 5+5).
For amount = 11:
- Coin 1: remainder 10, dp[10] = 2, candidate = 2 + 1 = 3.
- Coin 2: remainder 9, dp[9] = 3, candidate = 3 + 1 = 4.
- Coin 5: remainder 6, dp[6] = 2, candidate = 2 + 1 = 3. Minimum is 3.
  dp[11] = 3 (e.g. 5+5+1).

So the final answer dp[11] = 3, which matches what we expected (using two 5's and one 1).

This process filled out the dp array in a single pass from 1 to 11, considering all coin possibilities at each step. Each dp[x] was derived from smaller indices (subproblems), which were already solved.

Dynamic Programming – Python Code

Python3

. . . .

Dynamic Programming – Java Code

Java

. . . .

This dynamic programming solution efficiently computes the answer. In the code above, we used a one-dimensional dp array. Another possible DP approach is to use a 2D table where one dimension is the number of coin types considered and the other is the amount, similar to a classic Knapsack DP. However, that isn't necessary here; the 1D approach is simpler and works because we allow unlimited use of each coin.

Complexity Analysis – Dynamic Programming

Time Complexity: O(n * amount), where n is the number of coin types. We fill the dp array of size amount+1, and for each entry we potentially iterate over all n coins. With constraints, this is at most 12 * 10000 = 120,000 operations, which is very efficient.
Space Complexity: O(amount). We use an array of size amount+1 for DP. For amount=10000, that's 10001 integers, which is fine. The space is linear in the target amount. (If we did top-down recursion with memo, space would also be O(amount) for the memo table, and additional O(amount) for recursion stack in worst case.)

Dynamic programming is typically the recommended solution for this problem due to its clarity and efficiency. Next, we'll discuss an alternative approach using BFS, which conceptually mirrors what we did in DP but treats it as a shortest path search problem.

BFS Approach (Graph-Based Solution)

Explanation

Another way to think about the problem is as an unweighted shortest path in a graph of states. Each state is an amount of money, and you have transitions (edges) by using a coin to go from one amount to another. For example, from amount 7, using a coin of value 2 takes you to amount 5 (i.e., 7-2=5 if we think in reverse, or think forward: from 0, using coin 2 takes you to 2). If we frame it as from 0 up to amount (forward thinking), each coin usage is like taking a step in a graph from a smaller sum to a larger sum.

Imagine a graph where:

Nodes = amounts from 0 to amount.
You have an edge from node x to node x + c for each coin c (as long as x + c <= amount). This means from sum x, you can reach sum x+c by using one more coin of value c. This graph is unweighted (each edge represents using one coin, which we count as one "step").

Now the problem reduces to: starting at node 0 (amount 0, with 0 coins used), find the shortest path to node amount (the target sum). The length of the path (number of edges) will correspond to the number of coins used. Breadth-First Search (BFS) is ideal for finding the shortest path in an unweighted graph.

How BFS works here:

Start at amount 0 with distance (coin count) 0.
Enqueue the start state (0).
Perform BFS level by level. Each time we take a state curr (current amount) from the queue:
- For each coin value c, compute next = curr + c. This represents using coin c to increase the current sum.
- If next == amount, we've reached the target; return the current level + 1 as the answer.
- If next < amount and we haven't visited next before, mark it visited and enqueue it.
Continue until we either reach the target (found a solution) or exhaust all possibilities (queue empties without finding the target, meaning it's impossible to form that amount).

We use a visited set or boolean array to avoid revisiting the same amount multiple times, which prevents infinite loops and redundant work. This is analogous to how our DP avoided recomputation – once a state (amount) is visited at the shortest distance, any other way to reach that state would be longer, so we don't need to explore it again.

Example (BFS): Take coins = [1, 2, 5] and amount = 11:

Start at 0 (0 coins used).
Neighbors of 0: 1, 2, 5 (these are amounts reachable with 1 coin). Mark visited {0,1,2,5}.
Next level (1 coin): we have amounts 1, 2, 5.
Take 1: neighbors = 2 (already visited), 3, 6. New ones: 3, 6.
Take 2: neighbors = 3 (visited now), 4, 7. New ones: 4, 7.
Take 5: neighbors = 6 (visited now), 7 (visited now), 10. New one: 10.
After exploring all with 1 coin, the new states (2 coins used) discovered are {3, 6, 4, 7, 10} (order doesn’t matter).
Next level (2 coins): take 3 -> adds 4, 5, 8 (4,5 visited; 8 new), take 6 -> adds 7, 8, 11 (11 found!), etc. We found 11 at this stage, so answer = 3 coins.
BFS stops as soon as we find 11, which occurs at depth 3.

This matches our DP result. BFS is essentially doing the same exploration as DP but in a breadth-first manner.

When to consider BFS: BFS can be a good approach if the "state space" (here, amounts up to target) is not too large, and if we naturally think in terms of steps. It's especially intuitive if coin values were not uniform or if we had additional constraints that make DP formulation tricky. In this coin problem, BFS and DP are both fine. With amount <= 10000, BFS will at most visit each intermediate amount once, so performance is manageable.

One thing to note: BFS will generate states in potentially different order than DP (DP goes in increasing order of amount, BFS goes in increasing order of coin count depth). But they both ensure the first time we reach a particular amount is with the minimum coins.

BFS – Python Code

Python3

. . . .

BFS – Java Code

Java

. . . .

In the Java solution, we use a boolean[] visited for efficiency (constant-time lookups to check if we have seen an amount). The BFS increments steps each time we move to a new level of the search (meaning one more coin is used). As soon as we reach the target amount, we return the current number of steps. If BFS finishes without finding the target, we return -1.

Complexity Analysis – BFS

Time Complexity: O(n * amount) in the worst case. Each amount from 0 to amount is enqueued at most once (visited once). For each state, we try up to n coin transitions. So roughly we do O(n * amount) work. For amount=10000 and n up to 12, that's at most ~120k operations, similar to the DP approach. BFS can have overhead of queue operations and such, but it's linear in the number of states.
Space Complexity: O(amount) for the visited array/set and the queue. In worst case, the queue might hold many states at once, but it will be at most amount states. The visited structure is size amount+1. This is fine for 10^4 (and even much larger in many cases).

Both BFS and DP yield the result in about the same order of complexity. The constant factors may differ (DP might be a bit faster in practice since it's just array loops, whereas BFS involves more pointer manipulation and checks). For the given constraints, either is efficient.

Common Mistakes and Edge Cases

Here are some common pitfalls and edge cases to watch out for when solving Coin Change:

Assuming Greedy Works: A big mistake is thinking you can just take the largest coin first greedily. As discussed, a greedy strategy can fail for certain coin systems (e.g., a counterexample: coins = [1, 3, 4], amount = 6, where greedy gives 3 coins vs optimal 2 coins). Always verify if greedy is valid; in general, use DP or BFS for correctness.
Not Handling amount = 0: Make sure to return 0 when the amount is 0. It’s trivial (0 coins needed), but if not handled, your code might return -1 or some other value by default. Our solutions explicitly handle this.
No Solution Case: If no combination of coins can form the amount, return -1. Some forget to output -1 or mis-handle the condition. In DP, check if dp[amount] remained a large sentinel value. In BFS, if you exhaust the search without finding the target, return -1.
Integer Overflow (in some languages): If using a large sentinel value like Integer.MAX_VALUE or a very high number for impossible states, be careful when adding 1 to it (to avoid overflow). We avoided this by checking if res != MAX_VALUE before res + 1 in the brute force code, and by using amount+1 as the sentinel in DP (so it will never overflow when adding 1). Just be mindful in other contexts.
Inefficient Brute Force: Writing a brute force solution and testing it on large inputs can lead to timeouts or crashes (stack overflow). Always consider adding memoization or switching to DP/BFS for anything but the smallest test cases.
Large Coin Values with Small Amount: If you have coins larger than the target amount, they effectively can be ignored (they won't ever be used, except if one exactly equals the amount). The algorithms as written naturally handle this (DP will never update using a coin bigger than the current amount index; BFS will never generate a state beyond the target). Just be aware conceptually.
Unsorted Coins: The coin array need not be sorted for DP or BFS solutions. Our algorithms iterate through all coins regardless of order. Sorting is not required (and does not necessarily help). However, sometimes people sort to possibly try greedy or just out of habit – it doesn't harm correctness in DP/BFS, but it's not necessary.
Duplicate Coin Values: If the coins array has duplicates (e.g., [1,2,2,5]), it doesn't affect the result, but it could lead to redundant computation. It's usually assumed coin denominations are distinct. If not, you could deduplicate the list first to be safe.

Edge cases to test:

Smallest values: amount = 0 (expect 0), amount > 0 but no coins (though constraint guarantees at least one coin, it's a logical edge case), coins = [1] (only coin is 1, should return amount), coins = [> amount] (coin too large to use, expect -1 unless amount is 0).
Cases where one coin is exactly equal to amount (should return 1).
Prime vs composite scenarios: e.g., coins = [4,5], amount = 7 (cannot make 7, -1), amount = 9 (can make 4+5 = 2 coins).
The provided examples like [2], amount = 3 -> -1, etc.
A case with multiple coin types where the optimal uses a combination (to ensure algorithm picks combination over single-type usage): e.g., coins = [1, 7, 10], amount = 14. Greedy might pick 10 + 1*4 = 5 coins, but optimal is 7 + 7 = 2 coins. Our DP/BFS should give 2.

By covering these, you can be confident in your solution’s robustness.

Alternative Variations of the Problem

The coin change problem can have several interesting variations and related scenarios:

Counting Combinations (Coin Change II): Instead of finding the minimum number of coins, a different question (LeetCode 518) asks: "How many distinct ways can you make up the amount using the given coins?" This turns into a combinations-counting DP problem. The approach for that is different (you count ways instead of min coins, and order of coins doesn’t matter for distinct combinations).
Limited Coin Supply: In our problem, we assumed infinite supply of each coin. A variation could be if you have a limited number of each coin type. This becomes a bounded knapsack problem – you can still use DP, but you need to account for the limited quantities.
Exact Change with Constraints: Another twist could be requiring exactly k coins (not minimum, but exactly a given number), or finding if it's possible to use exactly k coins to sum to amount. This again can be solved with DP (adding a dimension for count or modifying state).
Different Objective: Sometimes the goal might be to maximize something instead of minimize (though with coins that’s less common unless coin values can be negative or you have a value associated with using a coin). One example is a game scenario where coins could give points and you want the maximum points not exceeding amount – but that diverges from the classic "make change" problem.
Making Change in Currency Systems: A practical variant is using specific currency denominations to make change for a cash amount (like making $0.87 with quarters, dimes, nickels, pennies). This is exactly the coin change problem. In most real currency systems like USD or EUR, a greedy algorithm does yield an optimal solution, but that’s because those coin systems are designed to be “canonical”. In general, the coin change DP works for any arbitrary set of denominations.
Partition Problems: If you think in terms of coins as pieces that sum to an amount, related variations include partitioning problems (e.g., can you partition a set of numbers into two equal-sum subsets, etc.) or other summation problems. Those are different in detail but share the theme of summing to a target.

Understanding the classic coin change problem sets you up to tackle these variants by adjusting the DP formulation or constraints.

Working on similar problems can strengthen your understanding. Here are a few related LeetCode problems and concepts:

Coin Change II (LeetCode 518): Count the number of ways to make up the amount with given coins (order of coins does not matter). This is a different DP problem (combinations count) but closely related to coin change.
Minimum Number of Squares (LeetCode 279 - Perfect Squares): Find the fewest number of perfect square numbers that sum to a given n. This is essentially coin change where the "coins" are perfect square values (1, 4, 9, 16, ... up to n). The approach is very similar (DP or BFS can be used).
Combination Sum (LeetCode 39) and Combination Sum II (LeetCode 40): These ask to find all combinations of candidates that sum to a target (one allows unlimited use, the other doesn’t allow reuse and avoids duplicates). They are backtracking problems related to coin change, but focus on listing combinations rather than counting or optimizing.
Jump Game II (LeetCode 45): Minimum number of jumps to reach the end of an array. This is not about coins, but it’s a minimum-step problem which can be solved with a greedy or BFS approach. It’s conceptually similar to finding a shortest path (each array index is a state, jumps are like using coins).
Unbounded Knapsack: A general problem where you have items with values (and maybe weights) that you can use infinitely and you want to maximize value for a given weight or minimize cost for a value. Coin change is a specific case of the unbounded knapsack (where we minimize the number of coins to achieve an exact sum).
Word Ladder (LeetCode 127): This is a stretch, but it’s a classic BFS shortest path problem (minimum transformations to change one word into another). It's related by the BFS approach of finding the shortest sequence of moves in a state-space (just like coin change BFS finds shortest sequence of coin additions).

322. Coin Change - Detailed Explanation

Problem Statement

Examples

Constraints

Hints

Brute Force Solution (Exhaustive Search)

Explanation

Brute Force – Python Code

Brute Force – Java Code

Complexity Analysis – Brute Force

Dynamic Programming Approach (Efficient)

Explanation

Step-by-Step Example (DP)

Dynamic Programming – Python Code

Dynamic Programming – Java Code

Complexity Analysis – Dynamic Programming

BFS Approach (Graph-Based Solution)

Explanation

BFS – Python Code

BFS – Java Code

Complexity Analysis – BFS

Common Mistakes and Edge Cases

Alternative Variations of the Problem

Related Problems for Practice