Uploaded January 2019 | Updated November 2026, 3 hours ago
Code & Problem Statement @ backtobackswe.com/platform/content/the-change-making-problem/video?utm_source=youtube&utm_medium=video
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
Question: You are given coins of different denominations and a total amount of money amount. Write a function to compute 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.
Examples:
1
Input:: coins = [1, 2, 5], amount = 11
Output 3
2
Input: coins = [2], amount = 3
Output: -1
Approach 1 (Brute Force)
We can generate all sets of coin frequencies that end up summing to the total amount given the coins that we granted and then take the sequence with the least coins in it.
This is not only harder to implement, but it entails an automatic exponential amount of work to compute all the sets of coin frequencies to only take the best answer (the set with the least coins) from.
Approach 2 (Top Down Dynamic Programming)
Example:
Input:: coins = [1, 2, 5], amount = 11
Output 3
The answer to the subproblem for amount 11 is the same thing as the MINIMUM of the answers to the sub problems with each currency deduced from the original sub problem (11) PLUS ONE since we are acting as if each coin we subtract from 11 is the last coin used to make change.
Not all paths will yield an answer, some will yield an optimal answer.
Complexities (Top Down)
A is the amount to make change for.
n is the total denominations avaliable to make change with.
Time: O( A * n )
For each amount we will approximately be doing n work in trying to deduct each denomination from the current sub problem
Our recursive tree will at maximum have a depth of S (worst case if each call deducts 1 at each call).
Space: O( A )
We answer and store a total of A subproblems in our dynamic programming table to get to our globally optimum answer.
Approach 3 (Bottom Up Dynamic Programming)
Example:
Input:: coins = [1, 2, 5], amount = 11
Output 3
We can also create a dynamic programming table going from the bottom up to the amount we want an answer for.
Complexities (Bottom Up)
A is the amount to make change for.
n is the total denominations avaliable to make change with.
Time: O( A * n )
For each amount we will potentially try each of the denominations (there are n of them).
Space: O( A )
We answer and store a total of A subproblems in our dynamic programming table to get to our globally optimum answer.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
Code & Problem Statement @ backtobackswe.com/platform/content/the-change-making-problem/video?utm_source=youtube&utm_medium=video
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
Question: You are given coins of different denominations and a total amount of money amount. Write a function to compute 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.
Examples:
1
Input:: coins = [1, 2, 5], amount = 11
Output 3
2
Input: coins = [2], amount = 3
Output: -1
Approach 1 (Brute Force)
We can generate all sets of coin frequencies that end up summing to the total amount given the coins that we granted and then take the sequence with the least coins in it.
This is not only harder to implement, but it entails an automatic exponential amount of work to compute all the sets of coin frequencies to only take the best answer (the set with the least coins) from.
Approach 2 (Top Down Dynamic Programming)
Example:
Input:: coins = [1, 2, 5], amount = 11
Output 3
The answer to the subproblem for amount 11 is the same thing as the MINIMUM of the answers to the sub problems with each currency deduced from the original sub problem (11) PLUS ONE since we are acting as if each coin we subtract from 11 is the last coin used to make change.
Not all paths will yield an answer, some will yield an optimal answer.
Complexities (Top Down)
A is the amount to make change for.
n is the total denominations avaliable to make change with.
Time: O( A * n )
For each amount we will approximately be doing n work in trying to deduct each denomination from the current sub problem
Our recursive tree will at maximum have a depth of S (worst case if each call deducts 1 at each call).
Space: O( A )
We answer and store a total of A subproblems in our dynamic programming table to get to our globally optimum answer.
Approach 3 (Bottom Up Dynamic Programming)
Example:
Input:: coins = [1, 2, 5], amount = 11
Output 3
We can also create a dynamic programming table going from the bottom up to the amount we want an answer for.
Complexities (Bottom Up)
A is the amount to make change for.
n is the total denominations avaliable to make change with.
Time: O( A * n )
For each amount we will potentially try each of the denominations (there are n of them).
Space: O( A )
We answer and store a total of A subproblems in our dynamic programming table to get to our globally optimum answer.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw

![Build A Min Height BST From A Sorted Array | Coding Interview Question
Back with another video π
Try Our Full Platform: https://nas.io/backtobackswe
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
β New Unseen Questions
Given a sorted array, create a binary search tree with minimal height.
Input:
[1, 2, 3, 4, 5, 6, 7]
Output:
[4, 2, 6, 1, 3, 5, 7]
Explanation:
4
/
2 6
/ /
1 3 5 7 Build A Min Height BST From A Sorted Array | Coding Interview Question](https://i.ytimg.com/vi/ky4GeXAZqb4/mqdefault.jpg)


![Implement A Max Stack - A Stack With A .max() API (Similar To Min Stack 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: Design a stack that includes a max operation, in addition to push and pop. The max method should return the maximum value stored in the stack.
A stack is an abstract data type (ADT).
An ADT is a data type is defined by its behavior from the point of view of a user of the data, we can implement it however we want as long as we give the user the interface they need to get what they expect from the ADT.
Stack is LIFO since the last item to go in, is the first one to come out.
Here we are asked to implement a stack with a max API which entails.
push()
Add an element
pop()
Get the top element
max()
Get the maximum element
The reason this is a problem is because the stack ADT restricts how data is added and retrieved from the structure so to make the .max() function run optimally we will have to think a little harder than the first approach we think of.
Approach 1 (No Optimizations & Obvious)
To answer a call to .max() we can iterate through the whole structure supporting our stack underneath and return the maximum item
whether it is implemented with an array, a lined list, etc.
This will take O(n) linear time always and O(1) constant space
Approach 2 (Use Auxiliary Data Structures)
We can use a max heap or a Binary Search Tree in tandem with a hashtable for fast lookups.
This idea is critical. Auxiliary structures with a hash table backing your ordered structures for quick lookups to get immediate reference to objects.
The structure solves the problem.
The hashtable lets you get into it fast.
This can bring us to log(n) time, but worsens space to O(n) since we will store at max all items potentially.
Approach 3 (Remember The Max At Each Element)
Write the optimal code [in EPI], but walkthrough this first.
On push it is easy to know what the max is if we have a global variable knowing the max.
We just compare the item we are adding to that max.
If the pushed item is greater then we update the global variable.
If the pushed item is less then we do nothing to the global variable.
On pop there is a problem, if we pop the element that was the maximum in the stack to that point, we have no idea what the next maximum item is unless we do an O(n) scan to restore the global variable.
So the solution is to remember the maximum in the stack at or below each item.
IF WE REMEMBER THE MAX AT EACH PUSH THEN WE SOLVE THE PROBLEM OF BEING LOST ON POP.
Complexities
Time: O( 1 )
.max() knows the maximum immediately
Space: O( n )
We need to store the max on every element upping our space usage
BIG TWEAK
We can improve the best case.
Notice that if a pushed element is less than the maximum, then it can never be the maximum.
We will use an auxiliary stack to record historical maximums and its count of occurrences (we cant just store the raw values becase of possible duplicates).
Complexities
Time stays O( 1 ), we are just optimizing space
Worst case space stays O( n )
If each pushed item is a max and needs a cached max entry
But best case for space becomes O(1) best case if the max does not change frequently.
++++++++++++++++++++++++++++++++++++++++++++++++++
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 number 9.1 in Elements of Programming Interviews by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash. Implement A Max Stack - A Stack With A .max() API (Similar To Min Stack on LeetCode)](https://i.ytimg.com/vi/nGwn8_-6e7w/mqdefault.jpg)



![Merge K Sorted Arrays - Min Heap Algorithm (Merge K Sorted Lists 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: Write a program that takes as input a set of sorted sequences and computes the union of these sequences as a sorted sequence.
This is basically the question merge 2 sorted arrays but now we have k sorted arrays.
Example:
Input
[ [3,5,7], [0,6], [0, 6, 28] ]
Output:
[0, 0, 3, 5, 6, 6, 7, 28]
Approach 1 (Brute Force)
Concatenate all arrays into one large array and sort the large array.
Sorting will always expense us O(n * log(n)) at the least when sorting non-special data that we only know a total ordering property for (then we can use merge sort or quick sort).
This does not use the fact that each array is sorted already which (should) help us on time complexity.
Approach 2
When building our final output array that is the sorted set of all the items we will be placing an item one by one from the original k arrays
What is are the items in each of those k arrays that interest us? The smallest items.
How can we keep track of the smallest item of the k smallest items respective to each array?
A min-heap is optimal.
Since we will hold at max k items in the min-heap we know what we will have at least O(k) time complexity where k is # of sorted arrays we need to maintain the smallest item across.
We will take the smallest item from the min-heap and remember the array it came from so that we can add the next item in that array to the min heap (if it exists).
Example Walkthrough:
Input
[ [3, 5, 7], [0, 6], [0, 6, 28] ]
Our output array will have size 8 [ _, _, _, _, _, _, _, _ ]
Let us step through this:
Initialize: Min Heap: [3, 0, 0]
[ 0, _, _, _, _, _, _, _ ]
Min Heap: [3, 0, 6] (0 came from array 2, we add the next item 6)
[ 0, 0, _, _, _, _, _, _ ]
Min Heap: [3, 6, 6] (0 came from array 3, we add the next item 6)
[ 0, 0, 3, _, _, _, _, _ ]
Min Heap: [5, 6, 6] (3 came from array 1, we add the next item 5)
[ 0, 0, 3, 5, _, _, _, _ ]
Min Heap: [7, 6, 6] (5 came from array 1, we add the next item 7)
[ 0, 0, 3, 5, 6, _, _, _ ]
Min Heap: [7, 6] (6 came from array 2, array 2 is finished)
[ 0, 0, 3, 5, 6, 6, _, _ ]
Min Heap: [7, 28] (6 came from array 3, we add the next item 28)
[ 0, 0, 3, 5, 6, 6, 7, _ ]
Min Heap: [28] (7 came from array 1, array 1 is finished)
[ 0, 0, 3, 5, 6, 6, 7, 28 ]
Min Heap: [] (28 came from array 3, array 3 is finished)
Output
[ 0, 0, 3, 5, 6, 6, 7, 28 ]
Complexities
Time: O( 2(n * log(k))) = O( n * log(k) )
Let n be the total elements across the k sorted arrays we are given.
Extracting and adding to the min heap will both take log(k) time.
For each of the n items, we will do an addition to the heap and removal from the heap (log(k) expense per heap operation).
Hence the times 2. It is dropped. We get O( n * log(k) ).
Space: O( k )
Our heap will need to hold k elements for most of this process and cannot worsen past this.
We are not counting the size of the output array which uses O(n) space since that isnt core to our algorithm.
++++++++++++++++++++++++++++++++++++++++++++++++++
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 number 11.1 in Elements of Programming Interviews by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash. Merge K Sorted Arrays - Min Heap Algorithm (Merge K Sorted Lists on LeetCode)](https://i.ytimg.com/vi/ptYUCjfNhJY/mqdefault.jpg)

![Reverse Polish Notation: Types of Mathematical Notations & Using A Stack To Solve RPN Expressions
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 an array with a sequence that represents a RPN expression, evaluate the Reverse Polish Notation expression.
This is one of those textbook problems. It is a classic expression of when LIFO behaviour is favorable to us when solving certain problems.
To have an RPN expression we need 2 things by definition:
A single digit or series of digits.
It is in the form [A, B, o] where A and B are integers and o is an operator (either +, -, *, or / ).
Examples:
[ 3, 4, +, 2, *, 1, + ]
is the same things as ( ( 3 + 4 ) * 2 ) + 1
which is the same things as ( 3 + 4 ) * 2 + 1 because of order of opeartions.
Example 2:
[ 1, 1, +, 2, 2, *, + ]
Approach
This is a classic stack problem, let us just do this.
The 2 key operations:
When we see a digit we push it to the stack.
When we see an operation we perform 2 pops, apply the operation between the 2 values (first popped item goes on left of the sign, 2nd popped item goes on the right of the sign), and then push the result back onto the stack so we can work with it as we continue.
If it is a valid RPN expression then we should have no problems with mismatches and null pointers, clarify that it is a valid RPN string always with your interviewer.
Complexities
n is the length of the RPN expression
Time: O( n )
We will process all n operators/operands in the expression. Each will either entail an O(1) push/pop or an O(1) arithmetic calculation.
Arithmetic operations take O(1).
Push and pop take O(1).
Space: O( d )
Let d be the total operands (numbers).
Let b be the number of operators (+, -, *, /)
If we have d digits and b operators where d + b = n, we certainly will not use O( d + b ) space (operators are not pushed to the stack).
A worst case is that we have all numbers, followed by the operators. And we will have a stack height of d digits. So we can bound to that.
++++++++++++++++++++++++++++++++++++++++++++++++++
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 number 9.2 in Elements of Programming Interviews by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash. Reverse Polish Notation: Types of Mathematical Notations & Using A Stack To Solve RPN Expressions](https://i.ytimg.com/vi/qN8LPIcY6K4/mqdefault.jpg)