Stack¶
Table of Contents¶
- 20. Valid Parentheses (Easy)
- 232. Implement Queue using Stacks (Easy)
- 150. Evaluate Reverse Polish Notation (Medium)
- 155. Min Stack (Medium)
- 42. Trapping Rain Water (Hard)
- 224. Basic Calculator (Hard)
- 84. Largest Rectangle in Histogram (Hard)
20. Valid Parentheses¶
# Stack
def is_valid(s: str) -> bool:
if len(s) % 2:
return False
pairs = {
"(": ")",
"{": "}",
"[": "]",
}
stack = []
for ch in s:
if ch in pairs:
stack.append(ch)
elif not stack or ch != pairs[stack.pop()]:
return False
return True if not stack else False
def test_is_valid():
assert is_valid("()[]{}")
assert not is_valid("(]")
assert not is_valid("([)]")
assert is_valid("{[]}")
#include <cassert>
#include <stack>
#include <string>
#include <unordered_map>
using namespace std;
class Solution {
public:
bool isValid(string s) {
unordered_map<char, char> map{{')', '('}, {'}', '{'}, {']', '['}};
stack<char> stack;
if (s.length() % 2 == 1) return false;
for (char& ch : s) {
if (stack.empty() || map.find(ch) == map.end()) {
stack.push(ch);
} else {
if (map[ch] != stack.top()) {
return false;
}
stack.pop();
}
}
return stack.empty();
}
};
int main() {
Solution s;
assert(s.isValid("()") == true);
assert(s.isValid("()[]{}") == true);
assert(s.isValid("(]") == false);
assert(s.isValid("([)]") == false);
assert(s.isValid("{[]}") == true);
return 0;
}
232. Implement Queue using Stacks¶
"""
- Implement the following operations of a queue using stacks.
- `push(x)` - Push element x to the back of queue.
- `pop()` - Removes the element from in front of queue.
- `peek()` - Get the front element.
- `empty()` - Return whether the queue is empty.
"""
class MyQueue:
def __init__(self):
self.stack_in = []
self.stack_out = []
def push(self, x: int) -> None:
self.stack_in.append(x)
def pop(self) -> int:
if self.empty():
return None
if self.stack_out:
return self.stack_out.pop()
else:
for _ in range(len(self.stack_in)):
self.stack_out.append(self.stack_in.pop())
return self.stack_out.pop()
def peek(self) -> int:
answer = self.pop()
self.stack_out.append(answer)
return answer
def empty(self) -> bool:
return not (self.stack_in or self.stack_out)
obj = MyQueue()
obj.push(1)
print(obj.pop()) # 1
print(obj.peek()) # None
print(obj.empty()) # False
150. Evaluate Reverse Polish Notation¶
from typing import List
# Stack
def evalRPN(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(b / a))
else:
stack.append(int(c))
return stack[0]
def test_evalRPN():
print(evalRPN(["2", "1", "+", "3", "*"])) # 9
print(evalRPN(["4", "13", "5", "/", "-"])) # 2
print(evalRPN(["18"])) # 18
print(evalRPN(["4", "3", "-"])) # 1
155. Min Stack¶
"""
- Implement a stack that supports push, pop, top, and retrieving the minimum element in constant time.
"""
# Stack
class MinStack:
def __init__(self):
self.stack = []
def push(self, val: int) -> None:
if self.stack:
self.stack.append((val, min(val, self.getMin())))
else:
self.stack.append((val, val))
def pop(self) -> None:
self.stack.pop()
def top(self) -> int:
return self.stack[-1][0]
def getMin(self) -> int:
return self.stack[-1][1]
obj = MinStack()
obj.push(3)
obj.push(2)
obj.pop()
print(obj.top()) # 3
print(obj.getMin()) # 3
#include <algorithm>
#include <climits>
#include <iostream>
#include <stack>
#include <utility>
using namespace std;
class MinStack {
stack<pair<int, int>> st;
public:
MinStack() { st.emplace(0, INT_MAX); }
void push(int val) { st.emplace(val, min(getMin(), val)); }
void pop() { st.pop(); }
int top() { return st.top().first; }
int getMin() { return st.top().second; }
};
int main() {
MinStack minStack;
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
cout << minStack.getMin() << endl; // -3
minStack.pop();
cout << minStack.top() << endl; // 0
cout << minStack.getMin() << endl; // -2
return 0;
}
42. Trapping Rain Water¶
"""
- 
<iframe width="560" height="315" src="https://www.youtube.com/embed/ZI2z5pq0TqA?si=OEYg01dbmzvmtIwZ" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe>
| Approach | Time | Space |
| ---------- | ---- | ----- |
| DP | O(N) | O(N) |
| Left Right | O(N) | O(1) |
| Monotonic | O(N) | O(N) |
"""
from typing import List
# DP
def trapDP(height: List[int]) -> int:
if not height:
return 0
n = len(height)
maxLeft, maxRight = [0 for _ in range(n)], [0 for _ in range(n)]
for i in range(1, n):
maxLeft[i] = max(maxLeft[i - 1], height[i - 1])
for i in range(n - 2, -1, -1):
maxRight[i] = max(maxRight[i + 1], height[i + 1])
res = 0
for i in range(n):
res += max(0, min(maxLeft[i], maxRight[i]) - height[i])
return res
# Left Right Pointers
def trapLR(height: List[int]) -> int:
if not height:
return 0
left, right = 0, len(height) - 1
maxL, maxR = height[left], height[right]
res = 0
while left < right:
if maxL < maxR:
left += 1
maxL = max(maxL, height[left])
res += maxL - height[left]
else:
right -= 1
maxR = max(maxR, height[right])
res += maxR - height[right]
return res
# Monotonic Stack
def trapStack(height: List[int]) -> int:
stack = []
total = 0
for i in range(len(height)):
while stack and height[i] > height[stack[-1]]:
top = stack.pop()
if not stack:
break
distance = i - stack[-1] - 1
bounded_height = min(height[i], height[stack[-1]]) - height[top]
total += distance * bounded_height
stack.append(i)
return total
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
print(trapDP(height)) # 6
print(trapLR(height)) # 6
print(trapStack(height)) # 6
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
class Solution
{
public:
int trap(vector<int> &height)
{
if (height.empty())
return 0;
int res = 0;
int left = 0, right = height.size() - 1;
int maxL = height[left], maxR = height[right];
while (left < right)
{
if (maxL < maxR)
{
left++;
maxL = max(maxL, height[left]);
res += maxL - height[left];
}
else
{
right--;
maxR = max(maxR, height[right]);
res += maxR - height[right];
}
}
return res;
}
};
int main()
{
vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
Solution solution;
cout << solution.trap(height) << endl;
return 0;
}
224. Basic Calculator¶
# Stack
def calculate(s: str) -> int:
stack = []
result = 0
number = 0
sign = 1
for char in s:
if char.isdigit():
number = number * 10 + int(char)
elif char == "+":
result += sign * number
number = 0
sign = 1
elif char == "-":
result += sign * number
number = 0
sign = -1
elif char == "(":
stack.append(result)
stack.append(sign)
result = 0
sign = 1
elif char == ")":
result += sign * number
number = 0
result *= stack.pop() # pop sign
result += stack.pop() # pop previous result
result += sign * number
return result
print(calculate("(1+(4+5+2)-3)+(6+8)")) # 23
84. Largest Rectangle in Histogram¶
from typing import List
# Monotonic Stack
def largestRectangleArea(heights: List[int]) -> int:
stack = []
max_area = 0
n = len(heights)
for i in range(n + 1):
h = 0 if i == n else heights[i]
while stack and h < heights[stack[-1]]:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
return max_area
print(largestRectangleArea([2, 1, 5, 6, 2, 3])) # 10