Uploaded April 2023 | Updated November 2026, 2 hours ago
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
![Total Unique Ways To Make Change - Dynamic Programming (Coin Change 2 on LeetCode)
Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have an infinite number of each kind of coin.
Examples:
1
Input: amount = 5, coins = [1, 2, 5]
Output: 4
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
2
Input: amount = 3, coins = [2]
Output: 0
Cant make change for this amount given the coins we have.
This problem is very similar to the 0 / 1 knapsack problem.
We will use a bottom up dynamic programming approach to build to our final answer.
We will consider the total ways to make change with just the 1st coin, with just the 1st and 2nd coin, with just the 1st, 2nd, and 3rd, coin, and so on...
Complexities
A is the amount to make change for.
n is the total denominations avaliable to us.
Time: O( A * n )
For each denomination we will be solving A subproblems. So for each of the n we will be doing A work, hence multiplication.
Space: O( A * n )
Hold the answer to all subproblems.
Note: We can do this in just O( A ) space but we did it this way for simplicity
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: https://www.youtube.com/user/tusharroy2525
GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: https://www.youtube.com/user/VSympathyV
Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw Total Unique Ways To Make Change - Dynamic Programming (Coin Change 2 on LeetCode)](https://i.ytimg.com/vi/DJ4a7cmjZY0/mqdefault.jpg)

![The Dutch National Flag Problem (The Quicksort Band-Aid)
Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
The relevance of this problem is in its applications to quicksort. If we pick bad pivots for quicksort then we will have a O(n^2) runtime which is very bad.
The way of repartitioning an array as shown in O(n) time aids in this issue of repeated elements in an array being sorted.
You can read more here: https://en.wikipedia.org/wiki/Dutch_national_flag_problem
The code for this problem is pretty straightforward to do (just 2 for loops, one going forward and one going backward UNTIL we hit the region less than the pivot). If you really want to see the code, this problem can be found in the amazing book Elements of Programming Interviews by Adnan Aziz as question 6.1
++++++++++++++++++++++++++++++++++++++++++++++++++
Question: Write a program that takes an array A and an index i into A, and rearranges the elements such that
1.) All elements less than A[i] (the pivot) appear first
2.) Followed by elements equal to the pivot
3.) Followed by elements greater than the pivot
Example
A = [0, 1, 2, 0, 2, 1, 1] (same array)
Pivot Index = 2
Valid Output: [0, 1, 0, 1, 1, 2, 2]
Valid Output: [0, 0, 1, 1, 1, 2, 2] (a more perfect output)
This is called Dutch national flag partitioning because the Dutch national flag consists of three horizontal bands, each in a different color.
We will get an input and attempt to form a 3 section partitioning of the array and will always end up with these 3 sections of lesser, equal, and greater value UNLESS the value at our partition index is the smallest OR greatest value in the array.
Approach 2
Rather than create extra space, we can just do 2 passes, one forward, and then one backward.
During the forward pass for each element in the array, we will look for an element smaller than the element we are at. If it is smaller we would swap ourselves with that element.
During the backward pass move backward and look for an element larger than the element we are at. If it is larger we will swap ourselves with it.
ALSO, we stop moving backward when the element we stand at is less than the pivot because at the point we know that the partitioning is finished.
Complexities:
Time: O(n^2) + O(n^2) = O(n^2)
2 O(n^2) passes. For each element in the array, we do nearly the whole array of comparisons (triangular number) both for the forwards and backward scans.
Space: O(1)
Approach 3
But we dont need to do a new scan for a smaller or larger element FOR EACH element in the array.
We can just have a placement pointer where we swap in smaller than pivot values (for the forward iteration) and a larger than pivot placement pointer to swap in larger values.
The values equal to the pivot will end up lying in the middle by themselves.
Example
A = [0, 1, 2, 0, 2, 1, 1]
Pivot Index = 1
Value at pivot index is 1.
Forward pass: (looking to place items less than 1)
i = 0 [0, 1, 2, 0, 2, 1, 1] Swap index 0 with index 0
i = 1 [0, 1, 2, 0, 2, 1, 1] (no swap)
i = 2 [0, 1, 2, 0, 2, 1, 1] (no swap)
i = 3 [0, 0, 2, 1, 2, 1, 1] Swap index 1 with index 3
i = 4 [0, 0, 2, 1, 2, 1, 1] (no swap)
i = 5 [0, 0, 2, 1, 2, 1, 1] (no swap)
i = 6 [0, 0, 2, 1, 2, 1, 1] (no swap)
After backwards pass: (looking to place items greater than 1)
i = 6 [0, 0, 2, 1, 2, 1, 1] (no swap)
i = 5 [0, 0, 2, 1, 2, 1, 1] (no swap)
i = 4 [0, 0, 2, 1, 1, 1, 2] Swap index 4 and index 6
i = 3 [0, 0, 2, 1, 1, 1, 2] (no swap)
i = 2 [0, 0, 1, 1, 1, 2, 2] Swap index 2 and index 5
i = 1 [0, 0, 1, 1, 1, 2, 2] (stop*)
*0 is less than the pivot value of 1 so we are now in the region LESS THAN the pivot that we already created in the front of the array
Complexities:
Time: O(n) + O(n) = O(n)
Forward pass with a backwards pass, both running in linear time
Space: O(1)
No auxiliary spaces is created that scales with the input
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: https://www.youtube.com/user/tusharroy2525
GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: https://www.youtube.com/user/VSympathyV
Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
++++++++++++++++++++++++++++++++++++++++++++
This question is 6.1 in the fantastic book Elements of Programming Interviews by Adnan Aziz. The Dutch National Flag Problem (The Quicksort Band-Aid)](https://i.ytimg.com/vi/ER4ivZosqCg/mqdefault.jpg)



![Count Total Unique Binary Search Trees - The nth Catalan Number (Dynamic Programming)
Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: Given n, how many structurally unique BSTs (binary search trees) that store values 1 ... n?
Catalan Numbers: https://en.wikipedia.org/wiki/Catalan_number
Define G(n): the number of unique BST for a sequence of length n.
G(0) = 1
G(1) = 1
For each element, we can place it and recurse on the left an right not including that number we choose to root that subtree.
Define F(i,n): the number of unique BST, where the number i is served as the root of BST (1 is less than or equal to i which is less than or equal to n).
G(n) = the summation from 1 to n of F(i, n)
When we choose an element to root a subtree from the possible elements to root there, we split the possibilities into a left and a right of the original enumeration.
Example:
n = 5 aka [1, 2, 3, 4, 5]
When evaluating F(3, 5) we will have
a left subtree with [1, 2] aka G(2)
a right subtree with [4, 5] aka G(2)
G(n) evaluates the # of unique trees we can construct from a total of n possible values, regardless of what those values are.
The Realization
We notice that F(i, n) = G(i - 1) * G(n - i)
To get F(i, n) we are considering all combinations of left tree possibilities with all of the right tree possibilities.
These exhaustive pairings between two sets of items is called a cartesian product.
Now we have a new way to express F(i, n)
F(i, n) = G(i - 1) * G(n - i)
G(n) = summation from 1 to n of G(i - 1) * G(n - i)
This now can be solved with DP via top-down recursion or bottom up.
For each G(n) up to our requested n we will solve the G(n) summation equation.
At the end we return the G(n) requested which by the end we will have an answer for.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: https://www.youtube.com/user/tusharroy2525
GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: https://www.youtube.com/user/VSympathyV
Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw Count Total Unique Binary Search Trees - The nth Catalan Number (Dynamic Programming)](https://i.ytimg.com/vi/GgP75HAvrlY/mqdefault.jpg)



