Inverse Coin Change solution and explanation
Google
7 more videos on this problem
Inverse Coin Change| LeetCode contest 455| leetcode 3592 | must do dynamic programming | top DP dsaCode Thoughts · 13:17 · 2K views
3592. Inverse Coin Change (Leetcode Medium)Programming Live with Larry · 17:20 · 1K views
Leetcode 3592 - Inverse Coin Change | DP Explained in JavacodingX krishna · 49:27 · 916 views
LeetCode 3592. Inverse Coin Change | DP | Medium | O(N^3)Leet's Code · 28:07 · 601 views
3592. Inverse Coin Change | LeetCode Contest 455| C++| DPBEASTCODES · 19:18 · 593 views
【每日一题】LeetCode 3592. Inverse Coin ChangeHuifeng Guan · 17:31 · 312 views
Inverse Coin Change | Leetcode 3592 | DP, Memoization, Dry Run in C++BEASTCODES · 16:38 · 212 views
Leetcode 3592. Inverse Coin Change | Q2 | Java| Recursion + DP Explained | Weekly Contest 455ExpertFunda · 29:47 · 193 views
The problem
You are given a 1-indexed integer array numWays, where numWays[i] represents the number of ways to select a total amount i using an infinite supply of some fixed coin denominations. Each denomination is a positive integer with value at most numWays.length.
However, the exact coin denominations have been lost. Your task is to recover the set of denominations that could have resulted in the given numWays array.
Return a sorted array containing unique integers which represents this set of denominations.
If no such set exists, return an empty array.
Example 1:
Input: numWays = [0,1,0,2,0,3,0,4,0,5]
Output: [2,4,6]
Explanation:
| Amount | Number of ways | Explanation |
|---|---|---|
| 1 | 0 | There is no way to select coins with total value 1. |
| 2 | 1 | The only way is [2]. |
| 3 | 0 | There is no way to select coins with total value 3. |
| 4 | 2 | The ways are [2, 2] and [4]. |
| 5 | 0 | There is no way to select coins with total value 5. |
| 6 | 3 | The ways are [2, 2, 2], [2, 4], and [6]. |
| 7 | 0 | There is no way to select coins with total value 7. |
| 8 | 4 | The ways are [2, 2, 2, 2], [2, 2, 4], [2, 6], and [4, 4]. |
| 9 | 0 | There is no way to select coins with total value 9. |
| 10 | 5 | The ways are [2, 2, 2, 2, 2], [2, 2, 2, 4], [2, 4, 4], [2, 2, 6], and [4, 6]. |
Input: numWays = [1,2,2,3,4]
Output: [1,2,5]
Explanation:
| Amount | Number of ways | Explanation |
|---|---|---|
| 1 | 1 | The only way is [1]. |
| 2 | 2 | The ways are [1, 1] and [2]. |
| 3 | 2 | The ways are [1, 1, 1] and [1, 2]. |
| 4 | 3 | The ways are [1, 1, 1, 1], [1, 1, 2], and [2, 2]. |
| 5 | 4 | The ways are [1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2], and [5]. |
Example 3:
Input: numWays = [1,2,3,4,15]
Output: []
Explanation:
No set of denomination satisfies this array.
Constraints:
1 <= numWays.length <= 1000 <= numWays[i] <= 2 * 108
Approach overview
Problem Overview: You are given an array where ways[i] represents the number of ways to form amount i using unlimited coins. The task is to recover the set of coin denominations that would produce exactly this dynamic programming table.
Approach 1: Brute Force Coin Set Search (Exponential Time)
Try every possible subset of coin denominations from 1..n. For each candidate set, recompute the classic coin change DP where dp[i] += dp[i - coin]. If the generated table matches the provided ways array, that set is valid. This method uses a full recomputation for each subset, resulting in O(2^n * n^2) time and O(n) space. It proves the problem is solvable but becomes infeasible even for moderate n.
Approach 2: DP Reconstruction from Ways Array (O(n^2))
The key observation: the standard coin change DP builds values incrementally by processing coins in increasing order. If a denomination c exists, it increases the number of ways for all amounts i ≥ c using dp[i] += dp[i - c]. Start with a fresh DP array where dp[0] = 1 and everything else is 0. Iterate amounts from 1 to n. If the computed dp[i] is smaller than ways[i], that gap must come from introducing a coin of value i. Add i to the coin set and update the DP for all future indices using the classic transition. Continue until the reconstructed DP matches the given array. This simulation runs in O(n^2) time with O(n) space.
The technique relies on the monotonic nature of coin processing: smaller denominations affect more states, so detecting discrepancies early reveals which coin must exist. Each discovered coin triggers a standard unbounded knapsack update across the array.
Implementation closely mirrors the classic dynamic programming formulation of coin change. The only difference is that instead of counting combinations for a target, you reconstruct the coin set that would generate the provided DP table. The input structure behaves like a prefix of the usual DP state array.
This problem combines ideas from array processing and incremental dynamic programming transitions. Careful state comparison between the generated DP and the provided array is the core step.
Recommended for interviews: The DP reconstruction approach. Interviewers expect you to recognize the classic coin change transition and reverse the process. Mentioning the brute force search demonstrates understanding of the search space, but reconstructing coins in O(n^2) time shows strong DP intuition.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Coin Set Search | O(2^n * n^2) | O(n) | Useful only for reasoning or very small inputs |
| DP Reconstruction from Ways Array | O(n^2) | O(n) | General case. Efficiently reconstructs denominations by simulating coin change DP |
Frequently asked questions
Is Inverse Coin Change easy or hard?
Inverse Coin Change is typically rated Medium. The forward coin change DP is standard, but recognizing how to reconstruct the coin set from the DP table requires deeper understanding of dynamic programming transitions.
Inverse Coin Change Python/Java solution
Most implementations follow the same structure: initialize a DP array with dp[0] = 1, iterate through the ways array, detect missing contributions, add the corresponding coin, and update dp using the classic coin change transition. The logic translates directly across Python, Java, C++, and Go.
How to solve Inverse Coin Change in O(n^2)?
Initialize dp[0] = 1 and iterate amounts from 1 to n. If the current dp[i] does not match the provided ways[i], add coin i to the set and update all states j ≥ i using dp[j] += dp[j - i]. Continue until the generated DP array matches the given array.
What is the best approach for Inverse Coin Change?
Dynamic programming reconstruction is the most efficient approach. Build a DP array the same way the classic coin change algorithm works and compare it with the provided ways array. Whenever the computed value is smaller than the expected value at index i, introduce a coin of value i and update the DP table. This runs in O(n^2) time and O(n) space.
Is Inverse Coin Change asked at Google/Amazon/Meta?
Variants of reverse dynamic programming and coin change reconstruction appear in interviews at companies like Google, Amazon, and Meta. Interviewers often test whether candidates understand how DP states are formed and whether they can reason about reversing the transition process.
What data structure is used in Inverse Coin Change?
The core data structure is a one‑dimensional dynamic programming array that stores the number of ways to form each amount. The algorithm also maintains a list or array of discovered coin denominations during reconstruction.
What is the time complexity of Inverse Coin Change?
The optimal reconstruction approach runs in O(n^2) time because every discovered coin may update the DP array from its value up to n. The algorithm uses O(n) additional space for the DP table used during reconstruction.