AlgoMonster: The Most Structured Way to Prepare for Coding Interviews

Coin Change

Medium

Given an integer array coins representing different denominations and an integer amount, return the fewest number of coins needed to make up that amount. If it is impossible, return -1.

Example:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: The minimum number of coins to make 11 is 5 + 5 + 1.

Input: coins = [2], amount = 3
Output: -1
Explanation: No combination of coins can make 3.

Input: coins = [1], amount = 0
Output: 0
Explanation: No coins are needed for amount 0.

Test Cases

Input

1 2 5
11

Expected Output

Step 1

Step 2

Step 3

Step 1: Identify the Pattern

Brute Force1

Dynamic Programming2

Greedy Algorithm3

Binary Search4

Coin Change

Medium

Given an integer array coins representing different denominations and an integer amount, return the fewest number of coins needed to make up that amount. If it is impossible, return -1.

Example:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: The minimum number of coins to make 11 is 5 + 5 + 1.

Input: coins = [2], amount = 3
Output: -1
Explanation: No combination of coins can make 3.

Input: coins = [1], amount = 0
Output: 0
Explanation: No coins are needed for amount 0.

Test Cases

Input

1 2 5
11

Expected Output

Step 1

Step 2

Step 3

Step 1: Identify the Pattern

Brute Force1

Dynamic Programming2

Greedy Algorithm3

Binary Search4

Example:

Test Cases

Example:

Test Cases

Study Notes

Start Taking Notes!