Category: foundational_interview
-
LeetCode 2696: Minimum String Length After Removing Substrings
link Stack Here “AB” is like “()” and “CD” is like “{}”. Deleting a pair enables further deletes if they are nested with matching open and close like: (()), {()}, {{}}, ({}). For example: “ACDB”. So, we use a stack to simulate deletes. Time: , space: same. Two pointers If we could modify the string,…
-
LeetCode 394: Decode String
link Our problem is a concatenation of the below pattern: Since there are nested sub-problems, we use stack to solve it. As we process the string from left-to-right, we have two decision points: In the end, the stack has the repeated string. Time: , space: same.
-
LeetCode 739: Daily Temperatures
link Brute force For each day we can scan into the future and pick the first day with a higher temperature. Time: . Stack If the temperatures are sorted in non-increasing order, no days will have a warmer day in the future. So, if any day has a future warmer day, there must be two…
-
LeetCode 232: Implement Queue using Stacks
link Queue preserves the write order. Stack reverses the write order. If we reverse write order twice, we get back the original order. So, we can pass the push()‘s through the two stacks (left and right) in sequence: . Here would be the push()and would be peek() or pop(). Amortized, each push(), peek(), pop() and…
-
LeetCode 341: Flatten Nested List Iterator
link We want to flatten the list lazily, so we use a stack with the top as the next element to return. If hasNext() returns true, the next() must return an integer. So, hasNext() must guarantee that there is an integer to return. We could not simply use len() as the signal for hasNext() because,…
-
LeetCode 636: Exclusive Time of Functions
link From pairs of consecutive logs we find exclusive time piecemeal and attribute to the correct function. Exclusive cpu time A log represents two timestamps: (1) end timestamp of the previous function and (2) start timestamp of the next function. If log timestamp is , then: From a pair of consecutive logs: and , we…
-
LeetCode 1249: Minimum Remove to Make Valid Parentheses
link Brute force Try all possibilities. For every opening parenthesis we can take it or remove it. For every closing parenthesis, we can remove it or if close count is less than open count, we can take it. Time: , space: . Greedy With a stack we try to match (or pop) an open as…
-
LeetCode 1047: Remove All Adjacent Duplicates In String
link Stack We can consider an adjacent duplicate pair like “aa” or “cc” as “()”. Removal of such a pair may produce more duplicate pairs only if there is nesting like: “(())”. For example: “zaaz” or “poop”. So, we use a stack to remove the nested duplicate pairs. Time: , space: same. Two pointers If…
-
LeetCode 224: Basic Calculator
link We want to process the string as a sequence of tokens where each token is an operator or an opening (or closing) parenthesis or a multi-digit number. So, we use a stack to store tokens as we process the string from left-to-right. All binary operators, no parentheses If we only had binary operators and…
-
LeetCode 59: Spiral Matrix II
link We simulate continuous spiral motion defined by directions and their boundaries. To get the matrix filled up, we piggyback on this motion by hopping in and hopping out at the right times. We hop in at while the motion has just moved from Up -> Right, with Up’s boundary changed from row_min = 0…
unreasonably effective 