Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Head of Career Skills Development & Coaching

*Based on past data of successful IK students

If you're preparing for a technical interview at FAANG, you must practice the coin change problem. The goal of this problem is to find the number coin combinations that can make a given amount. We will solve the coin change problem using 4 solutions and also tell you the time and space complexity for each.

Given a variety of coin denominations existing in a currency system, find the total number of ways a given amount of money can be expressed using coins in that currency system.

Assume an infinite supply of coins of every denomination.

```
{
"coins ": [1, 2, 3],
"amount": 3
}
```

Output:

```
3
```

The three ways are:

- Use the coin with denomination 1 three times.
- Use the coin with denomination 3 once.
- Use the coin with denomination 2 once and coin with denomination 1 once.

- Two ways are considered different if they use a different number of coins of any particular denomination.

Constraints:

- 1 <= total number of denominations <= 10
^{2} - 1 <= denomination of a coin <= 10
^{4} - 1 <= amount to be expressed <= 10
^{4}

We have provided the following solutions:

- Brute force solution using recursion
- Using both iterative and recursive dynamic programming to optimize the brute force solution
- Finally, we will introduce a nice trick to optimize the memory complexity of our solution with iterative dynamic programming

The most effective way to approach a dynamic programming problem is:

- Solve the problem for trivial cases, also known as the base cases.
- Figure out how the problem can be broken into smaller sub-problems. You also need to figure out which set of variables is necessary and sufficient to pinpoint the current sub-problem that we are trying to solve. This set of variables is known as the states of the problem.
- Figure out the relationship between the solution to the smaller subproblems and the solution of the whole problem. This relationship, known as the recurrence relation, can be expressed as a recursive function whose parameters are the states of the problem.

How to identify that the problem can likely be solved by the dynamic programming paradigm:

- Gain experience. If you solve various problems from different domains of algorithms, then you will start to observe a pattern in the dynamic programming problems.
- Try to break the problem into smaller subproblems and find the relationship between the solution to the smaller sub-problem and the solution to the whole problem. If you can, then most likely the problem can be solved with the dynamic programming paradigm.
- Try to convert the given problem to one of your known dynamic programming problems.

In the following solutions, we would be assuming that there are `n`

different denominations.

Let the recursive function `make_change(idx, target)`

return the number of ways to make target by using the coins from indices 0 to `idx`

, inclusive. By definition, `make_change(n - 1, amount)`

is what we need to return.

The base cases for this recursive function are:

- When we are at
`idx = -1`

, we need to check if we have`target`

== 0 or not. - We can return 0 whenever we have a negative
`target`

.

Now, let us focus on how to compute `make_change(idx, target)`

. We can make the amount target in two ways:

- By using the coin at index
`idx`

: If we use the coin at index`idx`

, our next goal would be to make`target - coins[idx]`

by using the coins from indices 0 to`idx`

. Here`coins[idx]`

is the denomination of the coin at index`idx`

. There are`make_change(idx, target - coins[idx])`

ways in total by definition. Notice that in the following call, even though we updated the parameter`target`

, we did not change the parameter`idx`

because we were allowed to use a coin as many times as we wanted. - By not using the coin at index
`idx`

: By definition, there are`make_change(idx - 1, target)`

ways in total to do so. If we combine the two cases, we get the following recurrence relation:

`make_change(idx, target) = (make_change(idx-1, target) + make_change(idx, target - coins[idx])) % 1000000007`

. The mod operation has been used as we need to output the result modulo 1000000007.

Exponential.

There are 2^{n} - 1 different subsets of the given coins which we can choose to use to make amount. In each such selection, we can choose to use any type of coin, any number of times. So our solution will try out at least 2^{n} - 1 different solutions in the worst case. Hence the complexity is exponential.

O(n + amount).

Here the auxiliary space is mostly used to maintain the call stack of the recursive calls. It is dominated by the highest possible depth of the call stack. As the smallest denomination for a coin can be equal to 1, so we can not use a coin more than amount times. Also, as we can skip at most `n - 1`

coins in total to make amount. So in the worst case, we may have a call stack of depth of O(n + amount).

O(n + amount).

Space used for input: O(n).

Auxiliary space used: O(n + amount).

Space used for output: O(1).

So, total space complexity: O(n + amount).

```
/*
Asymptotic complexity in terms of \`n\` = size of the input list and \`amount\`:
* Time: O(2^n).
* Auxiliary space: O(n + amount).
* Total space: O(n + amount).
*/
#define MOD 1000000007
int make_change(int idx, int target, vector<int> &coins) {
if (target < 0) {
return 0; // Invalid state as \`target\` can not be negative.
}
if (idx < 0) { // It means that we do not have any other coin left to consider.
if (target == 0) {
return 1; // The coins we used have summed up to \`amount\`.
} else {
return 0;
}
}
// We have two options for the coin sitting at index \`idx\`.
// 1. We can use it once now
// Notice that in the following call we did not change \`idx\` because we might
// use this coin again to make \`target\`.
int ret = make_change(idx, target - coins[idx], coins);
// 2. We ignore the coin at index \`idx\` and move to coin at index \`idx - 1\`.
ret = (ret + make_change(idx - 1, target, coins)) % MOD;
return ret;
}
int number_of_ways(vector<int> &coins, int amount) {
return make_change((int)coins.size() - 1, amount, coins);
}
```

Notice that in the above recursive solution, we may call the `make_change(idx, target)`

function multiple times with the same parameters.

For instance, consider the given example: There are three coin denominations: 1, 2 and 3 and we have to make the amount 3.

`coins[] = {1, 2, 3}`

`amount = 3`

Considering that we started from `idx = n - 1`

and `amount = 3`

state, there are two ways to reach `idx = 0`

and `target = 1`

state,

- By using the coin at
`idx = 1`

once. - By using the coin at
`idx = 0`

twice.

As the output of `make_change(idx, target)`

is constant, we do not need to compute this output more than once. We can store the result after computing the answer for `make_change(idx, target)`

once. This optimization technique is known as memoization.

The data structure that we should use for storing the data depends on the domain of the variables `idx`

and `target`

. There can be `n`

different values of `idx`

and `target`

can range from 0 to `amount`

. Both of the domains of the variables form a consecutive range. So it would be better to use a two dimensional static array than a hash table.

O(n * amount).

There are `n * amount`

different possible states which we may need to compute in the worst case. So the time complexity is equal to O(n * amount).

O(n * amount) space has been used for memoization.

O(n * amount).

Space used for input: O(n).

Auxiliary space used: O(n * amount).

Space used for output: O(1).

So, total space complexity: O(n * amount).

```
/*
Asymptotic complexity in terms of \`n\` = size of the input list and \`amount\`:
* Time: O(n * amount).
* Auxiliary space: O(n * amount).
* Total space: O(n * amount).
*/
#define MOD 1000000007
#define MAXN 100
#define MAXVAL 10000
int dp[MAXN + 3][MAXVAL + 3];
int make_change(int idx, int target, vector<int> &coins) {
if (target < 0) {
return 0; // Invalid state as \`target\` can not be negative.
}
if (idx < 0) { // It means that we do not have any other coin left to consider.
if (target == 0) {
return 1; // The coins we used have summed up to \`amount\`.
} else {
return 0;
}
}
// So that we do not calculate the solution to the same state more than once.
if (dp[idx][target] != -1) return dp[idx][target];
// We have two options for the coin sitting in index \`idx\`.
// 1. We can use it once now
// Notice that in the following call we did not change \`idx\` because we might
// use this coin again to make \`target\`.
int ret = make_change(idx, target - coins[idx], coins);
// 2. We ignore the coin at index \`idx\` and move to coin at index \`idx - 1\`.
ret = (ret + make_change(idx - 1, target, coins)) % MOD;
return dp[idx][target] = ret;
}
int number_of_ways(vector<int> &coins, int amount) {
memset(dp, -1, sizeof(dp));
return make_change((int)coins.size() - 1, amount, coins);
}
```

Let `dp[idx][target]`

be the number of ways we can make `target`

using coins from indices less than or equal to `idx`

, inclusive. By definition, `dp[n - 1][amount]`

is what we need to return. `dp[idx][0] = 1`

holds for all `idx`

between 0 to `n - 1`

as we can always make 0 in one way (by not using any coin at all). This is the base case of our solution.

Now let us focus on how to compute `dp[idx][target]`

. We can make the amount target in two ways.

- by using the coin at index
`idx`

: If we use the coin at index`idx`

, our next goal would be to make`target - coins[idx]`

by using the coins from indices between 0 to`idx`

.

Here `coins[idx]`

is the denomination of the coin at index `idx`

. There are `dp[idx][target - coins[idx]]`

ways in total by definition. Notice that we did not update the parameter `idx`

because we were allowed to use a coin as many times as we wanted.

- by not using the coin at index
`idx`

: By definition, there are`dp[idx - 1][target]`

ways in total to do so. If we combine the two cases, we get the following recurrence relation:

`dp[idx][target] = (dp[idx - 1][target] + dp[idx][target-coins[idx]]) % 1000000007`

Be careful to fill up the dp table in the right order. While computing a cell in the table, make sure that those cells who contribute to this cell have already been computed. In this problem incrementing `idx`

from 0 to `n - 1`

and incrementing the target from 0 to amount works.

O(n * amount).

There are (n * amount) different states that we may need to compute, and we compute each in constant time.

O(n * amount) space has been used for the dp table.

O(n * amount).

Space used for input: O(n).

Auxiliary space used: O(n * amount).

Space used for output: O(1).

So, total space complexity: O(n * amount).

```
/*
Asymptotic complexity in terms of \`n\` = size of the input list and \`amount\`:
* Time: O(n * amount).
* Auxiliary space: O(n * amount).
* Total space: O(n * amount).
*/
#define MOD 1000000007
#define MAXN 100
#define MAXVAL 10000
int dp[MAXN + 3][MAXVAL + 3];
// dp[idx][target] = number of ways we can make \`target\` using coins from indices less than or equal to \`idx\`.
int number_of_ways(vector<int> &coins, int amount) {
for (int idx = 0; idx < (int)coins.size(); idx++) {
for (int target = 0; target <= amount; target++) {
if (target == 0) {
dp[idx][0] = 1; // As we can make 0 in one way - by using no coin at all.
} else {
// We have two options for the coin sitting in index \`idx\`.
// 1. We can decide to not use this coin to make the sum \`target\`.
if (idx > 0) {
dp[idx][target] = dp[idx - 1][target];
}
// 2. We can use it as many times as we want.
if (target - coins[idx] >= 0) { // So that we do not access any negative index.
// For every way in which we can make the sum \`(target - coins[idx])\`,
// we can make the sum equal to \`target\` by using the coin at index \`idx\`.
dp[idx][target] = (dp[idx][target] + dp[idx][target - coins[idx]]) % MOD;
}
}
}
}
return dp[(int)coins.size() - 1][amount];
}
```

The dp table that we computed in our previous solution had a size of `n * amount`

. Let us call it the "complete dp table". The complete dp table can be thought of as a table with `n`

rows and `amount`

columns. In our solution, we will fill up the table row by row. Notice that, while computing any cell of a row, we only need the information from the immediate previous row. So we do not need to store all the rows of the complete dp table.

Only the data of the immediate previous row and current row which we are computing needs to be stored. Our optimized dp table has 2 rows and amount columns. We will be cyclically using these two rows to compute our solution.

While computing the rows, the data of the `i`

-th row from the complete dp table will be stored in `i % 2`

-th row of our optimized dp table. So whenever we are computing any row of the dp table, we will have the information of the previous row. For example, suppose we are trying to compute the dp table for the test case: `coins = [9, 1, 8, 10, 3]`

, `value = 12`

.

The complete dp table looks as follows:

```
1 0 0 0 0 0 0 0 0 1 0 0 0
1 1 1 1 1 1 1 1 1 2 2 2 2
1 1 1 1 1 1 1 1 2 3 3 3 3
1 1 1 1 1 1 1 1 2 3 4 4 4
1 1 1 2 2 2 3 3 4 6 7 8 10
```

Now, let us construct the optimized dp table. The 0th row can be computed without the help of any other row and the 1st row can be computed with the help of the 0-th row. So after computing the first two rows, our optimized dp table will look like:

```
1 0 0 0 0 0 0 0 0 1 0 0 0
1 1 1 1 1 1 1 1 1 2 2 2 2
```

At this stage, we do not need the information from the 0-th row. So we can overwrite this memory to store information about the 2nd row of the complete dp table.

```
1 1 1 1 1 1 1 1 2 3 3 3 3
1 1 1 1 1 1 1 1 1 2 2 2 2
```

Similarly, in this stage, we can replace the information of the 1st row with the new information from the 3rd row of the complete dp table.

```
1 1 1 1 1 1 1 1 2 3 3 3 3
1 1 1 1 1 1 1 1 2 3 4 4 4
```

Finally, on the last iteration, the table will look like:

```
1 1 1 2 2 2 3 3 4 6 7 8 10
1 1 1 1 1 1 1 1 2 3 4 4 4
```

But can we do better? Turns out that we can discard one of the two rows. Let us focus on the recurrence relation:

`dp[idx][target] = (dp[idx - 1][target] + dp[idx][target-coins[idx]])`

Notice that any cell contributes only its value to the next row of the same column. In other words, when moving from one row to another, we add some other value over the already existing value of that column. For this reason, we can use a one-dimensional array of size amount and add to the existing array data while moving from one row to the next row.

O(n * amount).

O(amount) space has been used for the dp table.

O(n + amount).

Space used for input: O(n).

Auxiliary space used: O(amount).

Space used for output: O(1).

So, total space complexity: O(n + amount).

```
/*
Asymptotic complexity in terms of \`n\` = size of the input list and \`amount\`:
* Time: O(n * amount).
* Auxiliary space: O(amount).
* Total space: O(n + amount).
*/
#define MOD 1000000007
#define MAXVAL 10000
int dp[2][MAXVAL + 3];
/*
Memory optimization idea:
In this problem there can be O(n * amount) different states. So the dp table that we are computing should
be of the size \`n * amount\`. Let us call this dp table of size \`n * amount\` as the "complete dp table".
The complete dp table can be thought as a table having \`n\` rows and \`amount\` columns. In our solution, we
will fill up the table row by row. Notice that, while computing any cell of a row, we only need the
information from the immediate previous row. So we do not need to store all the rows of the complete dp
table during computing the table. Only the data of the immediate previous row and current row needs to be
stored.
Our optimized dp table has 2 rows and \`amount\` columns. We will be cyclically using these two rows to
compute our solution. While computing the rows, the data of the i-th row from the complete dp table will
be stored in (i % 2)-th row of our optimized dp table.
*/
int number_of_ways(vector<int> &coins, int amount) {
for (int idx = 0; idx < (int)coins.size(); idx++) {
for (int target = 0; target <= amount; target++) {
if (target == 0) {
dp[idx % 2][0] = 1; // As we can make 0 in one way - by using no coin at all.
} else {
// We have two options for the coin sitting in index \`idx\`.
// 1. We can decide to not use this coin to make the sum \`target\`.
if (idx > 0) {
dp[idx % 2][target] = dp[(idx - 1) % 2][target];
}
// 2. We can use it as many times as we want.
if (target - coins[idx] >= 0) { // So that we do not access any negative index.
// For every way in which we can make the sum \`(target - coins[idx])\`,
// we can make the sum equal to target by using the coin at index \`idx\`.
dp[idx % 2][target] = (dp[idx % 2][target] + dp[idx % 2][target - coins[idx]]) % MOD;
}
}
}
}
return dp[((int)coins.size() - 1) % 2][amount];
}
```

We hope that these solutions to the coin change problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

- Back-end Engineering Interview Course
- Front-end Engineering Interview Course
- Full Stack Developer Interview Course

To learn more, register for the FREE webinar.

Note: Input and Output will already be taken care of.

If you're preparing for a technical interview at FAANG, you must practice the coin change problem. The goal of this problem is to find the number coin combinations that can make a given amount. We will solve the coin change problem using 4 solutions and also tell you the time and space complexity for each.

Given a variety of coin denominations existing in a currency system, find the total number of ways a given amount of money can be expressed using coins in that currency system.

Assume an infinite supply of coins of every denomination.

```
{
"coins ": [1, 2, 3],
"amount": 3
}
```

Output:

```
3
```

The three ways are:

- Use the coin with denomination 1 three times.
- Use the coin with denomination 3 once.
- Use the coin with denomination 2 once and coin with denomination 1 once.

- Two ways are considered different if they use a different number of coins of any particular denomination.

Constraints:

- 1 <= total number of denominations <= 10
^{2} - 1 <= denomination of a coin <= 10
^{4} - 1 <= amount to be expressed <= 10
^{4}

We have provided the following solutions:

- Brute force solution using recursion
- Using both iterative and recursive dynamic programming to optimize the brute force solution
- Finally, we will introduce a nice trick to optimize the memory complexity of our solution with iterative dynamic programming

The most effective way to approach a dynamic programming problem is:

- Solve the problem for trivial cases, also known as the base cases.
- Figure out how the problem can be broken into smaller sub-problems. You also need to figure out which set of variables is necessary and sufficient to pinpoint the current sub-problem that we are trying to solve. This set of variables is known as the states of the problem.
- Figure out the relationship between the solution to the smaller subproblems and the solution of the whole problem. This relationship, known as the recurrence relation, can be expressed as a recursive function whose parameters are the states of the problem.

How to identify that the problem can likely be solved by the dynamic programming paradigm:

- Gain experience. If you solve various problems from different domains of algorithms, then you will start to observe a pattern in the dynamic programming problems.
- Try to break the problem into smaller subproblems and find the relationship between the solution to the smaller sub-problem and the solution to the whole problem. If you can, then most likely the problem can be solved with the dynamic programming paradigm.
- Try to convert the given problem to one of your known dynamic programming problems.

In the following solutions, we would be assuming that there are `n`

different denominations.

Let the recursive function `make_change(idx, target)`

return the number of ways to make target by using the coins from indices 0 to `idx`

, inclusive. By definition, `make_change(n - 1, amount)`

is what we need to return.

The base cases for this recursive function are:

- When we are at
`idx = -1`

, we need to check if we have`target`

== 0 or not. - We can return 0 whenever we have a negative
`target`

.

Now, let us focus on how to compute `make_change(idx, target)`

. We can make the amount target in two ways:

- By using the coin at index
`idx`

: If we use the coin at index`idx`

, our next goal would be to make`target - coins[idx]`

by using the coins from indices 0 to`idx`

. Here`coins[idx]`

is the denomination of the coin at index`idx`

. There are`make_change(idx, target - coins[idx])`

ways in total by definition. Notice that in the following call, even though we updated the parameter`target`

, we did not change the parameter`idx`

because we were allowed to use a coin as many times as we wanted. - By not using the coin at index
`idx`

: By definition, there are`make_change(idx - 1, target)`

ways in total to do so. If we combine the two cases, we get the following recurrence relation:

`make_change(idx, target) = (make_change(idx-1, target) + make_change(idx, target - coins[idx])) % 1000000007`

. The mod operation has been used as we need to output the result modulo 1000000007.

Exponential.

There are 2^{n} - 1 different subsets of the given coins which we can choose to use to make amount. In each such selection, we can choose to use any type of coin, any number of times. So our solution will try out at least 2^{n} - 1 different solutions in the worst case. Hence the complexity is exponential.

O(n + amount).

Here the auxiliary space is mostly used to maintain the call stack of the recursive calls. It is dominated by the highest possible depth of the call stack. As the smallest denomination for a coin can be equal to 1, so we can not use a coin more than amount times. Also, as we can skip at most `n - 1`

coins in total to make amount. So in the worst case, we may have a call stack of depth of O(n + amount).

O(n + amount).

Space used for input: O(n).

Auxiliary space used: O(n + amount).

Space used for output: O(1).

So, total space complexity: O(n + amount).

```
/*
Asymptotic complexity in terms of \`n\` = size of the input list and \`amount\`:
* Time: O(2^n).
* Auxiliary space: O(n + amount).
* Total space: O(n + amount).
*/
#define MOD 1000000007
int make_change(int idx, int target, vector<int> &coins) {
if (target < 0) {
return 0; // Invalid state as \`target\` can not be negative.
}
if (idx < 0) { // It means that we do not have any other coin left to consider.
if (target == 0) {
return 1; // The coins we used have summed up to \`amount\`.
} else {
return 0;
}
}
// We have two options for the coin sitting at index \`idx\`.
// 1. We can use it once now
// Notice that in the following call we did not change \`idx\` because we might
// use this coin again to make \`target\`.
int ret = make_change(idx, target - coins[idx], coins);
// 2. We ignore the coin at index \`idx\` and move to coin at index \`idx - 1\`.
ret = (ret + make_change(idx - 1, target, coins)) % MOD;
return ret;
}
int number_of_ways(vector<int> &coins, int amount) {
return make_change((int)coins.size() - 1, amount, coins);
}
```

Notice that in the above recursive solution, we may call the `make_change(idx, target)`

function multiple times with the same parameters.

For instance, consider the given example: There are three coin denominations: 1, 2 and 3 and we have to make the amount 3.

`coins[] = {1, 2, 3}`

`amount = 3`

Considering that we started from `idx = n - 1`

and `amount = 3`

state, there are two ways to reach `idx = 0`

and `target = 1`

state,

- By using the coin at
`idx = 1`

once. - By using the coin at
`idx = 0`

twice.

As the output of `make_change(idx, target)`

is constant, we do not need to compute this output more than once. We can store the result after computing the answer for `make_change(idx, target)`

once. This optimization technique is known as memoization.

The data structure that we should use for storing the data depends on the domain of the variables `idx`

and `target`

. There can be `n`

different values of `idx`

and `target`

can range from 0 to `amount`

. Both of the domains of the variables form a consecutive range. So it would be better to use a two dimensional static array than a hash table.

O(n * amount).

There are `n * amount`

different possible states which we may need to compute in the worst case. So the time complexity is equal to O(n * amount).

O(n * amount) space has been used for memoization.

O(n * amount).

Space used for input: O(n).

Auxiliary space used: O(n * amount).

Space used for output: O(1).

So, total space complexity: O(n * amount).

```
/*
Asymptotic complexity in terms of \`n\` = size of the input list and \`amount\`:
* Time: O(n * amount).
* Auxiliary space: O(n * amount).
* Total space: O(n * amount).
*/
#define MOD 1000000007
#define MAXN 100
#define MAXVAL 10000
int dp[MAXN + 3][MAXVAL + 3];
int make_change(int idx, int target, vector<int> &coins) {
if (target < 0) {
return 0; // Invalid state as \`target\` can not be negative.
}
if (idx < 0) { // It means that we do not have any other coin left to consider.
if (target == 0) {
return 1; // The coins we used have summed up to \`amount\`.
} else {
return 0;
}
}
// So that we do not calculate the solution to the same state more than once.
if (dp[idx][target] != -1) return dp[idx][target];
// We have two options for the coin sitting in index \`idx\`.
// 1. We can use it once now
// Notice that in the following call we did not change \`idx\` because we might
// use this coin again to make \`target\`.
int ret = make_change(idx, target - coins[idx], coins);
// 2. We ignore the coin at index \`idx\` and move to coin at index \`idx - 1\`.
ret = (ret + make_change(idx - 1, target, coins)) % MOD;
return dp[idx][target] = ret;
}
int number_of_ways(vector<int> &coins, int amount) {
memset(dp, -1, sizeof(dp));
return make_change((int)coins.size() - 1, amount, coins);
}
```

Let `dp[idx][target]`

be the number of ways we can make `target`

using coins from indices less than or equal to `idx`

, inclusive. By definition, `dp[n - 1][amount]`

is what we need to return. `dp[idx][0] = 1`

holds for all `idx`

between 0 to `n - 1`

as we can always make 0 in one way (by not using any coin at all). This is the base case of our solution.

Now let us focus on how to compute `dp[idx][target]`

. We can make the amount target in two ways.

- by using the coin at index
`idx`

: If we use the coin at index`idx`

, our next goal would be to make`target - coins[idx]`

by using the coins from indices between 0 to`idx`

.

Here `coins[idx]`

is the denomination of the coin at index `idx`

. There are `dp[idx][target - coins[idx]]`

ways in total by definition. Notice that we did not update the parameter `idx`

because we were allowed to use a coin as many times as we wanted.

- by not using the coin at index
`idx`

: By definition, there are`dp[idx - 1][target]`

ways in total to do so. If we combine the two cases, we get the following recurrence relation:

`dp[idx][target] = (dp[idx - 1][target] + dp[idx][target-coins[idx]]) % 1000000007`

Be careful to fill up the dp table in the right order. While computing a cell in the table, make sure that those cells who contribute to this cell have already been computed. In this problem incrementing `idx`

from 0 to `n - 1`

and incrementing the target from 0 to amount works.

O(n * amount).

There are (n * amount) different states that we may need to compute, and we compute each in constant time.

O(n * amount) space has been used for the dp table.

O(n * amount).

Space used for input: O(n).

Auxiliary space used: O(n * amount).

Space used for output: O(1).

So, total space complexity: O(n * amount).

```
/*
Asymptotic complexity in terms of \`n\` = size of the input list and \`amount\`:
* Time: O(n * amount).
* Auxiliary space: O(n * amount).
* Total space: O(n * amount).
*/
#define MOD 1000000007
#define MAXN 100
#define MAXVAL 10000
int dp[MAXN + 3][MAXVAL + 3];
// dp[idx][target] = number of ways we can make \`target\` using coins from indices less than or equal to \`idx\`.
int number_of_ways(vector<int> &coins, int amount) {
for (int idx = 0; idx < (int)coins.size(); idx++) {
for (int target = 0; target <= amount; target++) {
if (target == 0) {
dp[idx][0] = 1; // As we can make 0 in one way - by using no coin at all.
} else {
// We have two options for the coin sitting in index \`idx\`.
// 1. We can decide to not use this coin to make the sum \`target\`.
if (idx > 0) {
dp[idx][target] = dp[idx - 1][target];
}
// 2. We can use it as many times as we want.
if (target - coins[idx] >= 0) { // So that we do not access any negative index.
// For every way in which we can make the sum \`(target - coins[idx])\`,
// we can make the sum equal to \`target\` by using the coin at index \`idx\`.
dp[idx][target] = (dp[idx][target] + dp[idx][target - coins[idx]]) % MOD;
}
}
}
}
return dp[(int)coins.size() - 1][amount];
}
```

The dp table that we computed in our previous solution had a size of `n * amount`

. Let us call it the "complete dp table". The complete dp table can be thought of as a table with `n`

rows and `amount`

columns. In our solution, we will fill up the table row by row. Notice that, while computing any cell of a row, we only need the information from the immediate previous row. So we do not need to store all the rows of the complete dp table.

Only the data of the immediate previous row and current row which we are computing needs to be stored. Our optimized dp table has 2 rows and amount columns. We will be cyclically using these two rows to compute our solution.

While computing the rows, the data of the `i`

-th row from the complete dp table will be stored in `i % 2`

-th row of our optimized dp table. So whenever we are computing any row of the dp table, we will have the information of the previous row. For example, suppose we are trying to compute the dp table for the test case: `coins = [9, 1, 8, 10, 3]`

, `value = 12`

.

The complete dp table looks as follows:

```
1 0 0 0 0 0 0 0 0 1 0 0 0
1 1 1 1 1 1 1 1 1 2 2 2 2
1 1 1 1 1 1 1 1 2 3 3 3 3
1 1 1 1 1 1 1 1 2 3 4 4 4
1 1 1 2 2 2 3 3 4 6 7 8 10
```

Now, let us construct the optimized dp table. The 0th row can be computed without the help of any other row and the 1st row can be computed with the help of the 0-th row. So after computing the first two rows, our optimized dp table will look like:

```
1 0 0 0 0 0 0 0 0 1 0 0 0
1 1 1 1 1 1 1 1 1 2 2 2 2
```

At this stage, we do not need the information from the 0-th row. So we can overwrite this memory to store information about the 2nd row of the complete dp table.

```
1 1 1 1 1 1 1 1 2 3 3 3 3
1 1 1 1 1 1 1 1 1 2 2 2 2
```

Similarly, in this stage, we can replace the information of the 1st row with the new information from the 3rd row of the complete dp table.

```
1 1 1 1 1 1 1 1 2 3 3 3 3
1 1 1 1 1 1 1 1 2 3 4 4 4
```

Finally, on the last iteration, the table will look like:

```
1 1 1 2 2 2 3 3 4 6 7 8 10
1 1 1 1 1 1 1 1 2 3 4 4 4
```

But can we do better? Turns out that we can discard one of the two rows. Let us focus on the recurrence relation:

`dp[idx][target] = (dp[idx - 1][target] + dp[idx][target-coins[idx]])`

Notice that any cell contributes only its value to the next row of the same column. In other words, when moving from one row to another, we add some other value over the already existing value of that column. For this reason, we can use a one-dimensional array of size amount and add to the existing array data while moving from one row to the next row.

O(n * amount).

O(amount) space has been used for the dp table.

O(n + amount).

Space used for input: O(n).

Auxiliary space used: O(amount).

Space used for output: O(1).

So, total space complexity: O(n + amount).

```
/*
Asymptotic complexity in terms of \`n\` = size of the input list and \`amount\`:
* Time: O(n * amount).
* Auxiliary space: O(amount).
* Total space: O(n + amount).
*/
#define MOD 1000000007
#define MAXVAL 10000
int dp[2][MAXVAL + 3];
/*
Memory optimization idea:
In this problem there can be O(n * amount) different states. So the dp table that we are computing should
be of the size \`n * amount\`. Let us call this dp table of size \`n * amount\` as the "complete dp table".
The complete dp table can be thought as a table having \`n\` rows and \`amount\` columns. In our solution, we
will fill up the table row by row. Notice that, while computing any cell of a row, we only need the
information from the immediate previous row. So we do not need to store all the rows of the complete dp
table during computing the table. Only the data of the immediate previous row and current row needs to be
stored.
Our optimized dp table has 2 rows and \`amount\` columns. We will be cyclically using these two rows to
compute our solution. While computing the rows, the data of the i-th row from the complete dp table will
be stored in (i % 2)-th row of our optimized dp table.
*/
int number_of_ways(vector<int> &coins, int amount) {
for (int idx = 0; idx < (int)coins.size(); idx++) {
for (int target = 0; target <= amount; target++) {
if (target == 0) {
dp[idx % 2][0] = 1; // As we can make 0 in one way - by using no coin at all.
} else {
// We have two options for the coin sitting in index \`idx\`.
// 1. We can decide to not use this coin to make the sum \`target\`.
if (idx > 0) {
dp[idx % 2][target] = dp[(idx - 1) % 2][target];
}
// 2. We can use it as many times as we want.
if (target - coins[idx] >= 0) { // So that we do not access any negative index.
// For every way in which we can make the sum \`(target - coins[idx])\`,
// we can make the sum equal to target by using the coin at index \`idx\`.
dp[idx % 2][target] = (dp[idx % 2][target] + dp[idx % 2][target - coins[idx]]) % MOD;
}
}
}
}
return dp[((int)coins.size() - 1) % 2][amount];
}
```

We hope that these solutions to the coin change problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

- Back-end Engineering Interview Course
- Front-end Engineering Interview Course
- Full Stack Developer Interview Course

To learn more, register for the FREE webinar.

**Attend our free webinar to amp up your career and get the salary you deserve.**

Hosted By

Ryan Valles

Founder, Interview Kickstart

- Designed by 500 FAANG+ experts
- Live training and mock interviews
- 17000+ tech professionals trained

00

Days

:

00

Hrs

:

00

Mins

:

00

Secs