Skip to main content
Talentd

Inverse Coin Change - Solution & Explanation

MediumArrayDynamic Programming4 min readAsked at: Meta, Google
Practice this problem

Problem Statement

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].
Example 2:

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 <= 100
  • 0 <= 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.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Coin Set SearchO(2^n * n^2)O(n)Useful only for reasoning or very small inputs
DP Reconstruction from Ways ArrayO(n^2)O(n)General case. Efficiently reconstructs denominations by simulating coin change DP

Video Solution

Inverse Coin Change| LeetCode contest 455| leetcode 3592 | must do dynamic programming | top DP dsa • Code Thoughts • 2,449 views views

Watch 7 more video solutions →

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.

Ready to solve this problem?

Practice Inverse Coin Change with our built-in code editor and test cases.

Practice on FleetCode
Previous

Coin Change

Next

Coin Change II