Uploaded November 2022 | Updated November 2026, 3 hours ago
π Full video - youtu.be/myZKhztFhzE
π Free 5-Day Course - backtobackswe.com/five-day
First, we must ask what asymptotic means. Well, you have probably heard of the word "asymptote".
An asymptote is a "line that continually approaches a given curve but does not meet it at any finite distance".
Therefore, asymptotic analysis is the analysis of tail behaviors not reaching any finite point. It is a method of describing limiting behavior.
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
π Full video - youtu.be/myZKhztFhzE
π Free 5-Day Course - backtobackswe.com/five-day
First, we must ask what asymptotic means. Well, you have probably heard of the word "asymptote".
An asymptote is a "line that continually approaches a given curve but does not meet it at any finite distance".
Therefore, asymptotic analysis is the analysis of tail behaviors not reaching any finite point. It is a method of describing limiting behavior.
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions




![The Change Making Problem - Fewest Coins To Make Change Dynamic Programming
Code & Problem Statement @ https://backtobackswe.com/platform/content/the-change-making-problem/video?utm_source=youtube&utm_medium=video
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 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: 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 The Change Making Problem - Fewest Coins To Make Change Dynamic Programming](https://i.ytimg.com/vi/jgiZlGzXMBw/mqdefault.jpg)

![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)
