Uploaded January 2019 | Updated November 2026, 3 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
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 let's 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 can't 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: 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
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 9.1 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.
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: 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 let's 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 can't 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: 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
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 9.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)
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)


![Partition To K Equal Sum Subsets From An Array of Integers - The Backtracking Approach
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 of integers nums and a positive integer k, find whether its possible to divide this array into k non-empty subsets whose sums are all equal.
Example:
Input:
nums = [4, 3, 2, 3, 5, 2, 1]
k = 4
Output:
true
Explanation:
Its possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.
So we will take our original array and try to form k buckets where:
Let sum be the sum of all elements in the array.
Each bucket has a sum of sum / k (aka we take the whole arrays sum and have each bucket be an equal cut of that total cumulative sum...hence K EQUAL SUM SUBSETS).
Validation
We cant do this if:
k is 0 or less.
sum % k is not 0 (meaning the total sum of the array does not allow us to have k equal sum buckets...we are only working with integers).
Code Explanation
The Driver Function:
We get the sum of the number to validate that we can have k equal sum buckets without having non-integer sums on each bucket
k also cannot be less than or equal to 0.
If all checks out we go into the recursion.
The Recursion:
Our approach here will be to fill each bucket with unique items, never placing an item in more than 1 bucket.
Each recursion frame will go through and try placing an item that has not been placed in a bucket (we keep track of placed items) and then we recurse with that item placed.
This is why we advance start by 1, we only use items past the item we just picked.
We also add the items value to our working sum.
When we have filled a bucket, we will continue on with the recursion while keeping the used items marked as seen and we set the start to 0 since the whole array is eligible again as long as an item has not been used yet and we set the working sum to 0 since we are working on a new bucket.
WHEN WE FILL K - 1 BUCKETS, WE ARE DONE. This is because if we filled k - 1 buckets, the last bucket MUST be fillable since sum % k 0.
Since we could fill all other buckets up to that point equally, we know for sure that we could finish the last bucket without things spilling over or going under value.
Complexities
Took me 3 hours of back and forth of thinking and I could still not pin the space complexity down to a point I could CLEARLY explain a given upper bound on time.
No one on Leetcode is sure and the moderators have very opaque explanations as always. I will leave this alone.
Time: O( ? )
Space: O( n )
Boolean array to mark used elements entails an automatic O(n) space.
Also, we will place nearly n items so the call stack will grow in a linear fashion with the input size but this is an after-consideration. The boolean array puts us at O(n) space at least from the beginning.
++++++++++++++++++++++++++++++++++++++++++++++++++
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 Partition To K Equal Sum Subsets From An Array of Integers - The Backtracking Approach](https://i.ytimg.com/vi/qpgqhp_9d1s/mqdefault.jpg)

![Compute The Next Permutation of A Numeric Sequence - Case Analysis (Next Permutation 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: Given a permutation of a sequence, calculate the next permutation in that sequence (if the permutation given is the last one, just return an empty array since it has no next permutation...it is the last permutation).
Approach 1 (Brute Force)
We can compute all permutations and stop on the permutation right after the permutation given.
This can have us generate n! permutations in the worst case (the permutation given is the last one).
Approach 2 (Use Intuition & Patterns)
Permutation Sequence Example:
[0, 1, 2]
1.) [0, 1, 2]
2.) [0, 2, 1]
3.) [1, 0, 2]
4.) [1, 2, 0]
5.) [2, 0, 1]
6.) [2, 1, 0]
This approach will use the idea that we notice patterns.
Notice how we plant the 0, the 1, then the 2 in the first slot as we go through the sequence.
Also, notice how the last element is the array completely reversed.
These may not matter but we are just piecing things together right now.
Lets formulate a plan.
[6, 2, 1, 5, 4, 3, 0]
We know to get to this permutation we
rooted 6
rooted 2
rooted 1
If you remember back to generating permutations it was all about planting items and then picking from a pool of remaining items.
When we plant 1 we have a pool like so [5, 4, 3, 0].
Remember how the last permutation was the original pool reversed? We will look for the longest reversed pool because we know that it is the last permutation for that particular rooting.
This is [5, 4, 3, 0] in the example given. This is a maximum suffix after the planted 1.
1 is of interest since this means we have exhausted the possibilities of permutations with 1 rooted where it is since its suffix following it is strictly decreasing.
SO TO GET THE NEXT PERMUTATION WE SWAP 1 AND THE SMALLEST NEXT ELEMENT TO MINIMIZE CHANGE IN THE PERMUTATION.
We are considering back to the rooting [6, 2] which has a possible pool of [0, 1, 2, 3, 5]
0 got its turn in index 2
1 got its turn and is finished
SO THE NEXT LARGEST ELEMENT IN 1s SUFFIX IS NEXT TO BE PLANTED THERE.
Swapping yields [6, 2, 3, 5, 4, 1, 0].
NOT DONE.
Now the prefix has been advanced in the smallest way possible. BUT the suffix of our choice to plant 3 may not be the smallest it could be to be the next permutation.
NOTICE: The first permutation was in STRICTLY INCREASING order. We need to get our suffix in strictly increasing order
We dont need to use a sorting algorithm since that is expensive.
Remember, the suffix was in strictly decreasing order before, so all we need to do is reverse it and we will have a sorted suffix.
When you really grasp how permutations are made then this will make a lot more sense and you probably could get this in an interview.
Complexities:
Time: O( n )
We are just doing linear time passes through all of this so we stay linear in time throughout.
Space: O( 1 )
We just use a few local variables, our space usage does not scale as input size gets very large.
++++++++++++++++++++++++++++++++++++++++++++++++++
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 6.10 in Elements of Programming Interviews by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash. Compute The Next Permutation of A Numeric Sequence - Case Analysis (Next Permutation on Leetcode)](https://i.ytimg.com/vi/quAS1iydq7U/mqdefault.jpg)