Stacks Flashcards
- Valid Parentheses
Solved
Easy
Topics
Companies
Hint
Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = “()”
Output: true
Example 2:
Input: s = “()[]{}”
Output: true
Example 3:
Input: s = “(]”
Output: false
Constraints:
1 <= s.length <= 104
s consists of parentheses only ‘()[]{}’.
https://leetcode.com/problems/valid-parentheses/description/
Map of close to open or open to close both work
class Solution:
def isValid(self, s: str) -> bool:
stack = []
close = {‘}’: ‘{‘, ‘)’: ‘(‘, ‘]’: ‘[’}
for p in s:
if p in close and stack:
if close[p] != stack.pop():
return False
elif p in close:
return False
else:
stack.append(p)
return not stack and True
class Solution(object):
def isValid(self, s):
“””
:type s: str
:rtype: bool
“””
opens = {‘{‘: ‘}’, ‘[’: ‘]’, ‘(‘:’)’}
stack = []
for c in s:
if c in opens:
stack.append(opens[c])
elif stack:
if c != stack.pop():
return False
else:
return False
return len(stack) == 0
- Min Stack
Solved
Medium
Topics
Companies
Hint
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.
Example 1:
Input
[“MinStack”,”push”,”push”,”push”,”getMin”,”pop”,”top”,”getMin”]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2
Constraints:
-231 <= val <= 231 - 1
Methods pop, top and getMin operations will always be called on non-empty stacks.
At most 3 * 104 calls will be made to push, pop, top, and getMin.
Key is to only append to min stack if value on min stack’s head is = or > the incoming value. In other words min stack will be a monotonically decreasing stack from 0 to n
class MinStack:
def \_\_init\_\_(self):
self.stack = []
self.minstack = []
def push(self, val: int) -> None:
self.stack.append(val)
if not self.minstack:
self.minstack.append(val)
elif val <= self.minstack[-1]:
self.minstack.append(val)
def pop(self) -> None:
popval = self.stack.pop()
if self.minstack and popval == self.minstack[-1]:
self.minstack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.minstack[-1]
Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
- Evaluate Reverse Polish Notation
Solved
Medium
Topics
Companies
You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.
Evaluate the expression. Return an integer that represents the value of the expression.
Note that:
The valid operators are ‘+’, ‘-‘, ‘*’, and ‘/’.
Each operand may be an integer or another expression.
The division between two integers always truncates toward zero.
There will not be any division by zero.
The input represents a valid arithmetic expression in a reverse polish notation.
The answer and all the intermediate calculations can be represented in a 32-bit integer.
Example 1:
Input: tokens = [“2”,”1”,”+”,”3”,”*”]
Output: 9
Explanation: ((2 + 1) * 3) = 9
Example 2:
Input: tokens = [“4”,”13”,”5”,”/”,”+”]
Output: 6
Explanation: (4 + (13 / 5)) = 6
Example 3:
Input: tokens = [“10”,”6”,”9”,”3”,”+”,”-11”,””,”/”,””,”17”,”+”,”5”,”+”]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
Constraints:
1 <= tokens.length <= 104
tokens[i] is either an operator: “+”, “-“, “*”, or “/”, or an integer in the range [-200, 200].
https://leetcode.com/problems/evaluate-reverse-polish-notation/description/
Only add numbers to stack, when math operation comes up, pop last 2 , do the operation and push the result back on the stack, return the last element of stack
class Solution(object):
def evalRPN(self, tokens):
“””
:type tokens: List[str]
:rtype: int
“””
symbols = {
‘+’: lambda a,b: a+b,
‘-‘: lambda a,b: a-b,
‘’: lambda a,b: ab,
‘/’: lambda a,b: a/(b * 1.0)
}
stack = []
for token in tokens:
if token not in symbols:
stack.append(token)
else:
b = int(stack.pop())
a = int(stack.pop())
stack.append(symbolstoken)
return int(stack[-1])
- Daily Temperatures
Solved
Medium
Topics
Companies
Hint
Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.
Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Example 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Example 3:
Input: temperatures = [30,60,90]
Output: [1,1,0]
Constraints:
1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100
https://leetcode.com/problems/daily-temperatures/description/
Monotonic Decreasing Stack
# Stack will always have a descending order
class Solution(object):
def dailyTemperatures(self, temperatures):
“””
:type temperatures: List[int]
:rtype: List[int]
“””
answers = [0] * len(temperatures)
stack = []
for idx, temp in enumerate(temperatures):
if not stack:
stack.append((idx, temp))
continue
while stack and stack[-1][1] < temp:
i,t = stack.pop()
answers[i] = idx - i
stack.append((idx, temp))
return answers
- Car Fleet
Solved
Medium
Topics
Companies
There are n cars going to the same destination along a one-lane road. The destination is target miles away.
You are given two integer array position and speed, both of length n, where position[i] is the position of the ith car and speed[i] is the speed of the ith car (in miles per hour).
A car can never pass another car ahead of it, but it can catch up to it and drive bumper to bumper at the same speed. The faster car will slow down to match the slower car’s speed. The distance between these two cars is ignored (i.e., they are assumed to have the same position).
A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.
If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.
Return the number of car fleets that will arrive at the destination.
Example 1:
Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Explanation:
The cars starting at 10 (speed 2) and 8 (speed 4) become a fleet, meeting each other at 12.
The car starting at 0 does not catch up to any other car, so it is a fleet by itself.
The cars starting at 5 (speed 1) and 3 (speed 3) become a fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.
Note that no other cars meet these fleets before the destination, so the answer is 3.
Example 2:
Input: target = 10, position = [3], speed = [3]
Output: 1
Explanation: There is only one car, hence there is only one fleet.
Example 3:
Input: target = 100, position = [0,2,4], speed = [4,2,1]
Output: 1
Explanation:
The cars starting at 0 (speed 4) and 2 (speed 2) become a fleet, meeting each other at 4. The fleet moves at speed 2.
Then, the fleet (speed 2) and the car starting at 4 (speed 1) become one fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.
https://leetcode.com/problems/car-fleet/
monotonic increasing stack keep an eye on speed calculations
class Solution:
def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
eta = []
for pos, spd in zip(position, speed):
remaining = target - pos
time = remaining/(1.0 * spd)
eta.append((pos, time))
eta = sorted(eta, reverse=True)
fleet = 0
stack = []
fleetfound = False
for _, time in eta:
if not stack:
stack.append(time)
continue
if stack and stack[-1] < time:
stack.append(time)
return len(stack)
- Largest Rectangle in Histogram
Solved
Hard
Topics
Companies: Amazon
Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.
Example 1:
Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.
Example 2:
Input: heights = [2,4]
Output: 4
Constraints:
1 <= heights.length <= 105
0 <= heights[i] <= 104
https://leetcode.com/problems/largest-rectangle-in-histogram/descriptio
monotonic increasing stacks
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
stack = []
maxarea = 0
for idx, height in enumerate(heights):
position = idx
while stack and stack[-1][1] > height:
p, h = stack.pop()
wide = idx - p
high = h
maxarea = max(maxarea, wide * high)
position = p
stack.append((position, height))
while stack:
p, height = stack.pop()
wide = len(heights) - p
maxarea = max(maxarea, wide * height)
return maxarea
- Daily Temperatures
Solved
Medium
Topics
Companies Facebook, Amazon
Hint
Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.
Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Example 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Example 3:
Input: temperatures = [30,60,90]
Output: [1,1,0]
Constraints:
1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100
https://leetcode.com/problems/daily-temperatures/description/
Monotonic decreasing stacks
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
stack = []
ans = [0] * len(temperatures)
for idx, temp in enumerate(temperatures):
while stack and stack[-1][1] < temp:
i, _ = stack.pop()
ans[i] = idx - i
stack.append((idx, temp))
return ans
- Minimum Remove to Make Valid Parentheses
Solved
Medium
Topics
Companies
Hint
Given a string s of ‘(‘ , ‘)’ and lowercase English characters.
Your task is to remove the minimum number of parentheses ( ‘(‘ or ‘)’, in any positions ) so that the resulting parentheses string is valid and return any valid string.
Formally, a parentheses string is valid if and only if:
It is the empty string, contains only lowercase characters, or It can be written as AB (A concatenated with B), where A and B are valid strings, or It can be written as (A), where A is a valid string.
Example 1:
Input: s = “lee(t(c)o)de)”
Output: “lee(t(c)o)de”
Explanation: “lee(t(co)de)” , “lee(t(c)ode)” would also be accepted.
Example 2:
Input: s = “a)b(c)d”
Output: “ab(c)d”
Example 3:
Input: s = “))((“
Output: “”
Explanation: An empty string is also valid.
Constraints:
1 <= s.length <= 105
s[i] is either '(' , ')', or lowercase English letter.
https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/description/
Maintain stack of indices of open parentheses, (like to check if paraentheses is balanced)
if you encounter a closed , with no open, add it’s index to ignore else pop the open stack.
Once done, combine the remaining indices of unclosed parentheses and the invalid closed and re-create the string without those indices.
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
a = []
to_ignore = set()
i = 0
while i < len(s):
if s[i] == '(':
a.append(i)
elif s[i] == ')':
if a:
a.pop()
else:
to_ignore.add(i)
i+=1
for idx in a:
to_ignore.add(idx)
ret = ""
for i, c in enumerate(s):
if i in to_ignore:
continue
ret += c
return ret
10 Mins, never seen.
O(n), O(n)
