Coin Change - Practice Coding Problems

Coin Change - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: coins = [1,3,4], amount = 6

› Output: 2

💡 Note: 6 = 3 + 3, so minimum coins needed is 2

Example 2 — Impossible Case

$ Input: coins = [2], amount = 3

› Output: -1

💡 Note: Cannot make amount 3 using only coins of denomination 2

Example 3 — Zero Amount

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

› Output: 0

💡 Note: No coins needed to make amount 0

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Available coin denominations and target amount

Process

Find optimal combination using fewest coins

Output

Return minimum number of coins needed

Key Takeaway

🎯 Key Insight: Use dynamic programming - if you know minimum coins for (amount - coin), then minimum for amount is 1 + min over all coins.

Asked in

a Amazon 45 G Google 38 M Microsoft 32 f Facebook 28

The key insight is that this is an optimization problem where we want to minimize coins used. The optimal substructure property means if we know the minimum coins for amount-coin, we can find minimum for amount. Best approach is bottom-up dynamic programming: build DP table where dp[i] = minimum coins for amount i. Time: O(amount × coins), Space: O(amount).

Common Approaches

Approach	Time	Space	Notes
✓ Memoization (Top-down DP)	O(amount × coins)	O(amount)	Cache recursive results to avoid redundant calculations
Recursive Brute Force	O(amount^coins)	O(amount)	Try all possible combinations recursively
Breadth-First Search	O(amount × coins)	O(amount)	Find shortest path to target amount using BFS
Bottom-up Dynamic Programming	O(amount × coins)	O(amount)	Build solutions for smaller amounts to solve larger amounts

Memoization (Top-down DP) — Algorithm Steps

Use recursion with a memo array
Check memo before calculating
Store result in memo before returning

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate

Solve subproblem recursively

Store

Cache the result in memo table

Reuse

Return cached result for repeated subproblems

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int memo[10001];
int memoSet[10001];

int helper(int* coins, int coinsSize, int remaining) {
    if (remaining == 0) return 0;
    if (remaining < 0) return INT_MAX;
    if (memoSet[remaining]) return memo[remaining];
    
    int minCoins = INT_MAX;
    for (int i = 0; i < coinsSize; i++) {
        int result = helper(coins, coinsSize, remaining - coins[i]);
        if (result != INT_MAX && result + 1 < minCoins) {
            minCoins = result + 1;
        }
    }
    
    memo[remaining] = minCoins;
    memoSet[remaining] = 1;
    return minCoins;
}

int solution(int* coins, int coinsSize, int amount) {
    memset(memoSet, 0, sizeof(memoSet));
    int result = helper(coins, coinsSize, amount);
    return result == INT_MAX ? -1 : result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int coins[100];
    int coinsSize = 0;
    
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        coins[coinsSize++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int amount;
    scanf("%d", &amount);
    
    int result = solution(coins, coinsSize, amount);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(amount × coins)

Each amount from 0 to target is calculated once, trying each coin

✓ Linear Growth

Space Complexity

O(amount)

Memo array of size amount plus recursion stack depth

⚡ Linearithmic Space

78.0K Views

High Frequency

~25 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoization (Top-down DP) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler