Is Coin Change easy or hard?

Coin Change is generally considered a medium difficulty problem. The challenge lies in recognizing the dynamic programming pattern and correctly defining the state transition for the minimum number of coins.

How to solve Coin Change in O(n * amount)?

Create a DP array where dp[i] represents the minimum coins needed to form amount i. Initialize dp[0] = 0 and fill the rest with a large value. For each amount i, iterate through all coins and update dp[i] = min(dp[i], dp[i - coin] + 1) if the coin fits. The final answer is dp[amount], or -1 if it remains unreachable.

What is the best approach for Coin Change?

Dynamic Programming is the most widely used solution for Coin Change. A bottom-up DP array stores the minimum coins needed for every amount from 0 to the target. This guarantees the optimal answer with O(n * amount) time and O(amount) space, where n is the number of coin denominations.

What data structure is used in Coin Change?

The most common solution uses a one-dimensional array for dynamic programming. BFS-based solutions additionally use a queue and a visited set to track explored remaining amounts during the search.

What is the time complexity of Coin Change?

The optimal dynamic programming solution runs in O(n * amount) time because each amount from 1 to the target is computed by iterating through all coin denominations. Space complexity is O(amount) for the DP array that stores intermediate results.

Coin Change Python or Java solution approach?

Both Python and Java implementations typically use the same bottom-up DP strategy. Initialize an array of size amount + 1, update values using each coin denomination, and return the computed minimum for the target amount.

Is Coin Change asked at Google, Amazon, or Meta?

Coin Change and its variations frequently appear in interviews at companies like Amazon, Google, and Meta. The problem tests understanding of dynamic programming, state transitions, and optimization over subproblems.

Description Solution Video 19:23

322. Coin Change

Medium49.3% acceptance40 companies

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
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

Constraints:

1 <= coins.length <= 12
1 <= coins[i] <= 2³¹ - 1
0 <= amount <= 10⁴

Asked at top 20 of 40 companies

Accolite Datadog Rupeek Intuit Fractal Analytics

Mastercard Meta Tiktok

Infosys Walmart Labs PayPal Pinterest

+8 more

Deutsche Bank Geico Sigmoid C3 Ai Amazon Bloomberg Oracle Adobe

Topics

19:23

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

322. Coin Change

Asked at top 20 of 40 companies

Topics

Similar problems