Summary

The text provides a solution to Leetcode 518, the Coin Change Problem, using two dynamic programming approaches: top-down and bottom-up.

Abstract

The Coin Change Problem involves forming a combination from a given array of coins that sum up to a given amount. The solution to this problem is typically solved using dynamic programming, which breaks down larger problems into smaller problems. The text presents a top-down approach and a bottom-up approach to solve the problem, along with code examples, diagrams, and a discussion of the time and space complexity of each approach.

Opinions

Dynamic programming is the best way to solve problems related to optimization, min, max, and most combinations.
The top-down approach is a recursion/backtrack strategy that can be better understood by drawing a tree diagram.
Duplicates can be prevented in the top-down approach by using indexes in incremented ways.
The bottom-up approach involves creating a 2D array and initializing it with zero and one values before filling it with the count of the amount formed using each coin.
Both approaches have a time and space complexity of O(N*M), where N is the length of the amount and M is the coin's size.
The code examples provided in the text are accepted by Leetcode.
The author suggests that readers should consider becoming a medium member to support the content and upskill their coding interview game by checking out a bestseller course.
The author is open to helping readers with their careers and encourages them to follow the writer and view more content on coding and system design interviews.

How to Solve Coin Change Problem — Leetcode 518

Java Solution for Leetcode 518

Originally published in https://asyncq.com

Problem

We have an infinite number of different types of coins such as coins 1, 2, 3, etc.
We have been given coins array and amount as input. We need to form a combination from the coins array that sums up to a given amount.

Institution

Whenever we need to find combination, optimization, min, max, most of the questions are solved by Dynamic Programming.

If you don’t know about Dynamic programming, is not that hard , it’s just people have made it buzz word and tag it as difficult.

Simply speaking in dynamic programming we try to break down large problems into small problems to get the value for that at first and then move to bigger and bigger subproblems.
There are two types of approaches we follow to solve any dynamic programming problem. Top Down and Bottom Up.
In this problem, we will come up with both solution.

Solution

Top Down

In Top-Down approach, we break larger problems into small problems. If we have to calculate the problem for f(5), then we first compute f(4). In order to calculate f(4), we first calculate f(3). Likewise, we reach to f(0) which becomes our base case.
It’s more of a recursion/backtrack strategy. The best way to understand recursion/backtrack approach is to draw a tree diagram to understand all the options for given problem.

In the above tree diagram, we first see all are the possibilities when the amount to be formed is 5 with a coins array. We can use coins 1, 2, and 5 and subtract them from the input amount.
Then for each new amount (Sub Problem), we have again coined 1,2,5 and we subtract them and get a new sub-problem.
Likewise, for a certain case, we reach up to 5 . In some cases, we overshoot the value, so basically, we cannot form 5 in that case.
We only select cases where we can form an amount of 5 and add an increase count to return that.

Duplicates Problem

But there is one problem since we are forming a combination, we will end up getting duplicates as well. for example [ 2,2,1] and [1,2,2] are not different combination there are same. but in our logic, we are getting duplicates.
One of the ways to avoid duplicates is to use indexes in incremented ways. What it means is that if the current index of the coin used is 1 then it will only consider the coin at index 1, 2 .. so on and it will not consider index 0.
In the below diagram, when we are using coin 1, we are considering all the coins. For index 2 we are only considering coins at index 2 and forward. we are not considering coins at index 1, thats how we can prevent using duplicates.

In the above tree diagram, we can observe that there is repeated work that we are doing. For example, when the amount is 1 and the current index is 1, we are recomputing the answer, so if we use cache to keep the previously calculated answer then we can reuse it. This approach is known as Memoization.
Below is our code for the top-down approach.

We are storing the coins index and amount to be calculated as the key for the cache. If we observe the tree, we will realize index + amount makes each iteration unique.

Submission

Top-down solution is accepted by Leetcode.

Complexity

Time Complexity: O(N*M)
Space Complexity: O(N*M)

Where N is the length of the amount and M is the coin's size.

Bottom Up

Bottom-up strategy is a bit different than top down, but once we come up with top down, the bottom is not that different.
We will create a 2D array with coins and amount size, to store the amount at each index.
Initially, we will initialize all counts with 0 when coins are zero because we cannot form an amount more than 0.
We will initialize the amount 0 when the number of coins is 0 or more to be 1.
After initialization we are storing count to form the amount, considering coins at each index.
If coins at any index are more than the amount to be formed then we just copy the count to form the previous amount.
Otherwise, we add a case when we have one coin less + a case when we consider the current coin.

Our solution is accepted by Leetcode.

Complexity

Time Complexity: O(N*M)
Space Complexity: O(N*M)

Where N is the length of the amount and M is the coin's size.

Conclusion

In this article, we solved Leetcode #518 problem. This problem involves knowledge of dynamic programming. We solved it using top-down and bottom approach and discussed about the solution in detail.

Before You Leave

Let me know if I can be of any help to your career, I would love to chat or jump on a call.
If you like this content consider becoming medium member to support.
If you want to upskill your coding interview game, you can definitely check out this bestseller course.

InterviewNoodle Community

👏 Please clap for the story and follow the writer👉
📰 View more content on Coding and System Design Interviews
🔔 Subscribe to the InterviewNoodle Newsletter