Stack and Queue Questions Part 1
173. Print elements of a linked list
Using a stack to print the entries of a singly linked list.
T O(N), S O(N).
(We could also use the technique of reversing a linked list, then T O(N), S O(1).)
def print_linked_list_in_reverse(head):
nodes = []
while head:
nodes.append(head.data)
head = head.next
while nodes:
print(nodes.pop())
174. (LC 155) Min Stack
155. Min Stack Medium
We can improve on space:
-if a new element pushed to stack is greater then current max, then we don’t have to
add it to minStack (it will never be min).
-record min and min_count. So if elem=5 and we encounter a second 5, we record count+=1
for elem 5. E.g.:
stack = [2,2,1,4]
minStack = [(2,1), (2,2), (4,1)]
#can be tuples, named tuples, or class within our Stack class.
Solution 1 [10] [7] T O(1), S O(N)
class MinStack:
def __init__(self):
self.stack = []
self.minStack = []
def push(self, val: int) -> None:
self.stack.append(val)
val = min(val, self.minStack[-1] if self.minStack else val)
self.minStack.append(val)
def pop(self) -> None:
self.stack.pop()
self.minStack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.minStack[-1]
175. (LC 150) Evaluate Reverse Polish Notation
LC 150. Evaluate Reverse Polish Notation Medium
RPN (Reverse Polish Notation):
Example 1:
Input:
tokens = ["2","1","+","3","*"]Output: 9
Explanation: ((2 + 1) * 3) = 9
Ex 2:
Input:
tokens = ["4","13","5","/","+"]Output: 6
Explanation: (4 + (13 / 5)) = 6
Recognize the simplicity of the RPN mechanism:
No matter what form of RPN you are given, even if [num, num, num, oper, oper],
the procedure is the same:
-the partial results are added and removed in LIFO order, so use stack
-if cur char == num: then add to stack
if cur char == operator: then pop the last two nums from stack and use that operator on them,
add result to stack.
Approaches:
The differences in implementation concern only the way you implement the operators:
-don’t implement, use directly +,-,*,/
-use hash, map using lambda
-use hash, map to operator module functions
-the last entry in stack is the result of the last expression = our answer
Recall: passing args to lambda
a = lambda x, y: x + y print(a(2, 3))
Solution 1 [2] (LC accepted 95,85%)
stack = [] # intermidiate results
DELIMITER = ","
OPERATORS = {
"+": lambda x, y: x + y,
"-": lambda x, y: y - x,
"*": lambda y, x: x * y,
"/": lambda x, y: int(y / x),
}
for token in tokens.split(DELIMITER):
if token in OPERATORS:
stack.append(OPERATORS[token](stack.pop(), stack.pop()))
else: # token is a num
stack.append(int(token))
return stack[-1]
Solution 2 [7]
import operator
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
opt = {
"+": operator.add,
"-": operator.sub,
"*": operator.mul,
"/": operator.truediv,
}
s = []
for token in tokens:
if token in opt:
s.append(int(opt[token](s.pop(-2), s.pop(-1))))
else:
s.append(int(token))
return s[0]
Solution 3 [10] O(N)
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for c in tokens:
if c == "+":
stack.append(stack.pop() + stack.pop())
elif c == "-":
a, b = stack.pop(), stack.pop()
stack.append(b - a)
elif c == "*":
stack.append(stack.pop() * stack.pop())
elif c == "/":
a, b = stack.pop(), stack.pop()
stack.append(int(float(b) / a))
else:
stack.append(int(c))
return stack[0]
My V (LC accepted 48,85%)
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
operators = {'+': operator.add, '-': operator.sub,
'*': operator.mul, '/': operator.truediv}
stack = []
for s in tokens:
if s in operators:
val1 = stack.pop()
val2 = stack.pop()
val3 = operators[s](val2, val1)
stack.append(int(val3))
else:
stack.append(int(s))
return stack[0]
176. (LC 71) Simplify Path
71. Simplify Path Medium
Key:
-Understand the task, it is simple.
When given a path, it is a series of cd commands in the shell.
E.g. path = ‘/../abc//./def/’
0)We always start at the root.
1) cd .. (we are at the root, so .. does nothing.)
2) cd abc (we are at /abc)
3) ignore //, ignore .
4) cd def (we are at /abc/def)
Note: we always ignore //, and . (cd to current)
-Why stack
Because of ..
When we encounter .. we go back one dir, so pop from stack ONCE.
Our new path IS STACK itself (stack is not a helper data structure).
Solution 1
class Solution:
def simplifyPath(self, path: str) -> str:
stack = []
for i in path.split("/"):
# if i == "/" or i == '//', it becomes '' (empty string)
if i == "..":
if stack:
stack.pop()
elif i == "." or i == '':
# skip "." or an empty string
continue
else:
stack.append(i)
res = "/" + "/".join(stack)
return res
Note when splitting on ‘/’, we get empty
'':#1
>>> path = '/../ed//tr/'
>>> L = path.split("/")
>>> L
['', '..', 'ed', '', 'tr', '']
#2
To stack we just add, e.g.
stack = ['ed', 'tr']My V (LC accepted 85, 37%)
class Solution:
def simplifyPath(self, path: str) -> str:
stack = []
path = path.split('/')
for p in path:
if p == '.':
continue
elif p == '..':
if stack:
stack.pop()
elif p != '/' and p != '':
stack.append(p)
new_path = '/'.join(stack)
return '/' + new_path
177. (LC 22) Generate Parentheses
22. Generate Parentheses Medium
Background on Backtracking
Backtracking is a technique for listing all possible solutions for a combinatorial algorithm problem.
Backtracking is an algorithmic technique whose goal is to use brute force to find all solutions to a problem. It entails gradually compiling a set of all possible solutions. Because a problem will have constraints, solutions that do not meet them will be removed.
A backtracking algorithm uses the depth-first search method. If a proposed solution satisfies the constraints, it will keep looking. If it does not, the branch is removed, and <the algorithm returns to the previous level>.
State-Space Tree A tree that represents all of the possible states of the problem, from the root as an initial state to the leaf as a terminal state.
Intermediate checkpoints. If the checkpoints do not lead to a viable solution, the problem can return to the checkpoints and take another path to find a solution.
Backtracking boilerplate:
void FIND_SOLUTIONS(parameters):
if (valid solution):
store the solution
Return
for (all choice):
if (valid choice):
APPLY (choice)
FIND_SOLUTIONS (parameters)
BACKTRACK (remove choice) <===
Return
Our alg in terms of backtracking
So after finding and appending a valid solution.
res = [‘((()))’]
We start to backtrack -> stack.pop()
Till
stack = [‘(’, ‘(‘]
And then start to collect another valid answer.
Keys to our alg in general:
How do you decide which ( or ) to add to response?
You keep track of the counts for the number of closing and opening parentheses.
Initially openCount=0, closeCount=0
You deal with 2 cases:
1)add ‘(’ => if openCount < n
‘((’
Put an open one any time, just not more than <n> given times.
2)add ‘)’ => if openCount > closedCount
‘(’ -> ‘()’, ‘)’ -> No
Put closing one only if there are more open parentheses than closed ones.
I.e. there is a pending open one yet to close.
Use variable <cur> where you build a current valid string
Keys:
-two ifs, not else
-add closed if num of open > num closed
-add open if num of open < total num of pairs
Solution 2 (rewrite from C, LC accepted 30, 15%, 2nd run 70, 80)
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
cur = ''
res = []
def backtrack(cur, o, c):
if o == n == c:
res.append(cur)
return
# add open par
if o < n:
backtrack(cur + '(', o+1, c)
# add closed
if o > c:
backtrack(cur + ')', o, c+1)
backtrack(cur, 0,0)
return res
Solution 1
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
stack = []
res = []
def backtrack(openN, closedN):
if openN == closedN == n:
res.append("".join(stack))
return
if openN < n:
stack.append("(")
backtrack(openN + 1, closedN)
stack.pop()
if closedN < openN:
stack.append(")")
backtrack(openN, closedN + 1)
stack.pop()
backtrack(0, 0)
return res
Complexity Time O((2**n) * n)
Because we have 2 possibilities, closed or open (, ).
178. (LC 739) Daily Temperatures
739. Daily Temperatures Medium
Keys:
-Stack, mono decreasing, storing pairs [temp, index]
Brute force would take us O(n**n).
Using monotonic stack: O(n) Time&Space.
Solution 1 [10]
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
res = [0] * len(temperatures) #1
stack = [] # pair: [temp, index]
for i, t in enumerate(temperatures):
while stack and t > stack[-1][0]:
poppedT, poppedInd = stack.pop()
res[stackInd] = i - stackInd
stack.append((t, i))
return res
#1
After iterating over all temps, if something is still in the stack, then there is
not a warmer day for these temps. Then the defaults of our ans 0 will be used.
If we encounter temperature <greater than temp on stack>:
-we pop from stack and
-calculate response for the index on stack
/When no stack, put current (temp, index) to stack.
Going through the loop:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
1)(73,0)
stack=[]
res = [0,0,0,0,0,0,0]
stack=[(73,0)]
res = [0,0,0,0,0,0,0]
2)(74,1)
stack=[(73,0)]
res = [0,0,0,0,0,0,0]
stack=[]
poppedT, pippedInd = 73, 0
calculate res = curInd - poppedInd = 1-0=1
At ind 0 = 1
res = [1,0,0,0,0,0,0]
stack=[(74,1)]
3)(75,2)
stack=[(74,1)]
res = [1,0,0,0,0,0,0]
calculate res = curInd - poppedInd = 2-1=1
res = [1,1,0,0,0,0,0]
stack=[(75,2)]
4)(71,3)
stack=[(75,2)]
Cur val 71 NOT > 75, then we just put it on stack.
stack=[(75,2), (71, 3)]
5)(69,4)
Cur val 69 NOT > 71, then we put it on stack.
stack=[(75,2), (71, 3), (69, 4)]
6)(72, 5)
stack=[(75,2), (71, 3), (69, 4)]
calculate res = curInd - poppedInd = 5-4=1
At ind 4 = 1
stack=[(75,2), (71, 3)]
res = [1,1,0,0,1,0,0]
still 72 > 71
calculate res = curInd - poppedInd = 5-3=2
At ind 3 = 2
res = [1,1,0,2,1,0,0]
stack=[(75,2)]
72 NOT > 75, add 72 to stack
stack=[(75,2), (72,5)]
7)(76,6)
stack=[(75,2), (72,5)]
calculate res = curInd - poppedInd = 6-5=1
At ind 5 = 1
stack=[(75,2)]
res = [1,1,0,2,1,1,0]
still 76 > 75
calculate res = curInd - poppedInd = 6-2=4
At ind 2 = 4
stack=[]
res = [1,1,4,2,1,1,0]
stack=[(76,6)]
8)(73,7)
stack=[(76,6)]
73 NOT > 76, so we just put it to stack
stack=[(76,6), (73,7)]
179. (LC 853) Car Fleet
853. Car Fleet Medium
My V (LC accepted 65, 12)
In data:
position = [10, 8, 0, 5, 3]
speed = [2, 4, 1, 1, 3]
target = 12
Make array cars = [(position, time)] -> [(10,1), (8,1), (0,12), (5,7), (3,3)]
Sort cars on position, cars = [(0,12), (3,3), (5,7), (8,1), (10,1)]
Loop start with the car closest to target, (10,1).
Pop: time. If current time > previous time, then this car won’t catch up with
the previous car (because current is farther from target than previous, and
this farther car will take more time to reach the target).
class Solution:
def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
time = [0] * len(position)
cars = [0] * len(position)
for i in range(len(position)):
time[i] = (target - position[i]) / speed[i]
cars[i] = (position[i], time[i])
cars.sort()
fleet = 0
prev_time = 0
while cars:
p,t = cars.pop()
if t > prev_time:
fleet +=1
prev_time = t #update only if found greater time
return fleet
Solution, initial
Keys:
-sort input in reverse
-work with values in stack[-1], stack[-2]. Put only time to stack.
Steps
-make pairs (position, speed)
-sort pairs in reverse (meaning it will sort on position. Greatest..Smallest)
NOTE: Greater position means the car is Closer to target ==> 4 is closer than 2.
-loop our sorted pairs
-On stack we will be putting “Time to get to the target”
-The lookup stack[-1] and stack[-2] checks if:
the Further away car (stack[-1]) would get to target Faster than the closer car (stack[-2]).
If yes, we can join that faster car to the fleet of the slower car: stack.pop()
Solution [10]
def carFleet(target: int, position: List[int], speed: List[int]) -> int:
pair = [(p, s) for p, s in zip(position, speed)]
pair.sort(reverse=True)
stack = [] #[time1, time2..]
for p, s in pair: # Reverse Sorted Order
stack.append((target - p) / s) #**
if len(stack) >= 2 and stack[-1] <= stack[-2]:
stack.pop()
return len(stack)
#** - Unlike many algs where we put to stack as last step, here we first put to stack, and work with values stack[-1], stack[-2], because otherwise we don’t check if to merge the last car into a fleet with previous cars.
C++
My V (LC accepted 18, 5)
(Making a separate vector of vectors to store [[position, time]] is space costly, but helps with the clarity.)
class Solution {
public:
int carFleet(int target, vector<int>& position, vector<int>& speed) {
vector<vector<double>> cars;
for(size_t i = 0; i != position.size(); ++i){
double t = (target - position[i]) / static_cast<double>(speed[i]);
cars.push_back({static_cast<double>(position[i]), t});
}
sort(cars.begin(), cars.end());
int fleet = 0;
double prev_time = 0;
while (!cars.empty()){
double t = cars.back()[1];
cars.pop_back();
if(t > prev_time){
++fleet;
prev_time = t;
}
}
return fleet;
}
};
180. (LC 84) Largest Rectangle in Histogram
84. Largest Rectangle in Histogram Hard
Keys:
-If current height is greater than previous, then previous can extend its width +1.
->So monotonic increasing stack.
-Store in stack [index, height]
Details:
-After popping from stack, record the cur value not with its cur index,
but with index of the last popped greater value.
# stk=[(1,0),(5,2),(6,3)], next v=2, after popping stk=[(1,0),(2,3)]
# ^
Because the lesser value can start (extends) from the first greater value.
-After the main alg, when cleaning out values from stack, our stack is mono increasing,
means all items in stack can extend to the last index of heights.
int index = heights.size();
area = max(area, v * (index-ind));
My V (LC accepted 35, 30%)
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
ans = 0
stack = [] #[index, height]
for i, h in enumerate(heights):
start = i
while stack and stack[-1][1] > h:
index, height = stack.pop()
area = height * (i-index)
ans = max(ans, area)
start = index
stack.append([start, h])
for i, h in stack:
area = h * (len(heights) - i)
ans = max(ans, area)
return ans
My V2 (LC accepted 30, 42%)
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
stack = [] #[(v,i),..] mono increasing
area = 0
for i, n in enumerate(heights):
if not stack or stack[-1][0] <= n:
stack.append((n,i))
else:
while stack and stack[-1][0] > n:
v, ind = stack.pop()
area = max(area, (i-ind)*v)
stack.append((n, ind)) #append to stack with last popped index
index=len(heights)
while stack:
v,ind = stack.pop()
area = max(area, v*(index-ind))
return area
Solution 1 [10]
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
maxArea = 0
stack = [] # pair: (index, height)
for i, h in enumerate(heights):
start = i #**1
while stack and stack[-1][1] > h:
index, height = stack.pop()
maxArea = max(maxArea, height * (i - index))
start = index #**1
stack.append((start, h))
for i, h in stack: #**2
maxArea = max(maxArea, h * (len(heights) - i))
return maxArea
#**1
E.g.
heights = [5,6,2]
stack = [(1,5),(2,6)]
Looking at the height 2.
stack[-1][1]=5 > 2. We have to pop taller rects from the stack.
Pop, calculate area.
Then we record to stack not (2,2), but (0,2).
0 being the ==> index of the last popped rect.
==> Because rect 2 can extend backwards all the way to index 0 here.
Patterns:
- heights = [1,2]
Looking at 1, the next height is greater, means we can extend height=1 to the right.
We put (i, h) to stack
->2
1 2
- heights = [2,1]
Looking at 2, the next height is smaller, means we cannot extend height=2 to the right.
2->
2 1
Then we pop all taller rects from stack. Record area for each.
NOTE. The WIDTH = i of encountered shorter rect - index of popped rect
(See #**)
#**2
If there was only an upward trend in rects, then the stack will be full.
# 3
# 2 3
# 1 2 3
E.g.: Area of rect 1 = 1 * ((len=3) - index=0) = 3
C++
//My V (LC accepted 65, 55%)
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<pair<int,int>> stk; //{{val, index},..}
int area {0};
for(int i=0; i!=heights.size(); ++i){
int n = heights.at(i);
if(stk.empty() || stk.top().first <= n)
stk.push({n,i});
else{
int ind{0}; //have to declare not in while, otherwise stays in while locally
while(!stk.empty() && stk.top().first > n){
ind = stk.top().second;
int v = stk.top().first;
stk.pop();
area = max(area, v * (i-ind));
}
stk.push({n, ind});
}
}
int index = heights.size();
while(!stk.empty()){
int ind = stk.top().second, v = stk.top().first;
stk.pop();
area = max(area, v * (index-ind));
}
return area;
}
};