Uploaded October 2019 | Updated November 2026, 3 hours ago
Try Our Full Platform: nas.io/backtobackswe
๐น Intuitive Video Explanations
โNew Unseen Questions
๐ Get All Solutions
Flow Networks: en.wikipedia.org/wiki/Flow_network
FordโFulkerson Algorithm: en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm
Max-Flow Min-Cut Theorem: en.wikipedia.org/wiki/Max-flow_min-cut_theorem
Proofs: Reference "Algorithm Design" by Jon Kleinberg and รva Tardos Chapters 7.1, 7.2 for excellent proofs on all of this.
Things I'd Improve On This Explanation (w/ More Time):
1.) I should have done a walk-through showing how the residual graph dictates how the original graph's edge flows (f(e)) are updated each iteration. (That would've made it more clear how the residual graph in the Ford-Fulkerson algorithm tells us how to update the flow on each edge (f(e)) in the original graph along the s-t path P, THEN we update the residual graph (also along P) to prepare for the next iteration.)
2.) Go into the actual augmentation once we find an s-t path P in the residual graph. We can only modulate the flow f(e) for each edge in the original graph on path P ยฑ the smallest value residual graph edge on path P. The smallest forward edge on path P in the residual graph is the "bottleneck" to how much we can increase flow along the path P in the original graph. (hard to visualize...the textbook may have to take it away with this one, but when you understand this you'll really get it after watching this video)
I also didn't talk about time complexity, but the amount of while loop iterations is bounded to the capacity coming out of start node 's'. We can't ever push more flow from 's' than the sum of capacities of those exiting edges. If each interaction increases the value of the flow v(f) by 1 (and v(f) starts at 0 in the beginning since no "water" is going through the "pipes"), we can do at most C augmentations of the flow network where C = sum(edge capacities leaving 's').
In each while loop:
- O(|V| + |E|) to find the augmenting path
- O(|E|) to update the flows in the original graph
- O(|E|) to update the residual graph
So total runtime can be bounded to O(C * (|V| + |E|)).
#backtobackswe #benyamephrem
Try Our Full Platform: nas.io/backtobackswe
๐น Intuitive Video Explanations
โNew Unseen Questions
๐ Get All Solutions
Flow Networks: en.wikipedia.org/wiki/Flow_network
FordโFulkerson Algorithm: en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm
Max-Flow Min-Cut Theorem: en.wikipedia.org/wiki/Max-flow_min-cut_theorem
Proofs: Reference "Algorithm Design" by Jon Kleinberg and รva Tardos Chapters 7.1, 7.2 for excellent proofs on all of this.
Things I'd Improve On This Explanation (w/ More Time):
1.) I should have done a walk-through showing how the residual graph dictates how the original graph's edge flows (f(e)) are updated each iteration. (That would've made it more clear how the residual graph in the Ford-Fulkerson algorithm tells us how to update the flow on each edge (f(e)) in the original graph along the s-t path P, THEN we update the residual graph (also along P) to prepare for the next iteration.)
2.) Go into the actual augmentation once we find an s-t path P in the residual graph. We can only modulate the flow f(e) for each edge in the original graph on path P ยฑ the smallest value residual graph edge on path P. The smallest forward edge on path P in the residual graph is the "bottleneck" to how much we can increase flow along the path P in the original graph. (hard to visualize...the textbook may have to take it away with this one, but when you understand this you'll really get it after watching this video)
I also didn't talk about time complexity, but the amount of while loop iterations is bounded to the capacity coming out of start node 's'. We can't ever push more flow from 's' than the sum of capacities of those exiting edges. If each interaction increases the value of the flow v(f) by 1 (and v(f) starts at 0 in the beginning since no "water" is going through the "pipes"), we can do at most C augmentations of the flow network where C = sum(edge capacities leaving 's').
In each while loop:
- O(|V| + |E|) to find the augmenting path
- O(|E|) to update the flows in the original graph
- O(|E|) to update the residual graph
So total runtime can be bounded to O(C * (|V| + |E|)).
#backtobackswe #benyamephrem

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

![Generate All Strings With n Matched Parentheses - Backtracking (Generate Parentheses 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 number n in and returns all the strings with n matched pairs of parens.
Examples:
n = 1
[ () ]
n = 2
[ (()), ()() ]
n = 3
[ ((())),(()()),(())(),()(()),()()() ]
Approach 1 (Brute Force Then Validate)
Generate all (2 ^ (2n)) possible parenthese strings and then validate each for being balanced.
If n = 2 then the string length will be 2 times that since all open parentheses are matched by closed parentheses.
This lower bounds our time complexity.
Even if we restrict the enumeration to just sets with an equal number of left and right parentheses we will have choose(2k, k) strings to consider for validation.
Approach 2 (Directed Backtracking)
The 3 Keys To Backtracking
Our Choice:
Whether we place a left or right paren at a certain decision point in our recursion.
Our Constraints:
We cant place a right paren unless we have left parens to match against.
Our Goal:
Place all k left and all k right parens.
The Key
At each point of constructing the string of length 2k we make a choice.
We can place a ( and recurse or we can place a ) and recurse.
But we cant just do that placement, we need 2 critical pieces of information.
The amount of left parens left to place.
The amount of right parens left to place.
We have 2 critical rules at each placement step.
We can place a left parentheses if we have more than 0 left to place.
We can only place a right parentheses if there are left parentheses that we can match against.
We know this is the case when we have less left parentheses to place than right parentheses to place.
Once we establish these constraints on our branching we know that when we have 0 of both parens to place that we are done, we have an answer in our base case.
++++++++++++++++++++++++++++++++++++++++++++++++++
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 16.6 in Elements of Programming Interviews by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash. Generate All Strings With n Matched Parentheses - Backtracking (Generate Parentheses on LeetCode)](https://i.ytimg.com/vi/sz1qaKt0KGQ/mqdefault.jpg)