Stack¶

Table of Contents¶

20. Valid Parentheses (Easy)
155. Min Stack (Medium)
150. Evaluate Reverse Polish Notation (Medium)
22. Generate Parentheses (Medium)
739. Daily Temperatures (Medium)
853. Car Fleet (Medium)
84. Largest Rectangle in Histogram (Hard)

20. Valid Parentheses¶

LeetCode | LeetCode CH (Easy)
Tags: string, stack
Determine if the input string is valid.
Steps for the string ()[]{}:

char	action	stack
`(`	push	"("
`)`	pop	""
`[`	push	"["
`]`	pop	""
`{`	push	"{"
`}`	pop	""

20. Valid Parentheses - Python Solution

# Stack
def isValid(s: str) -> bool:
    hashmap = {
        ")": "(",
        "]": "[",
        "}": "{",
    }
    stack = []

    for c in s:
        if c in hashmap:
            if stack and stack[-1] == hashmap[c]:
                stack.pop()
            else:
                return False
        else:
            stack.append(c)

    return True if not stack else False


print(isValid("()"))  # True
print(isValid("()[]{}"))  # True
print(isValid("(]"))  # False

20. Valid Parentheses - C++ Solution

#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;
}

155. Min Stack¶

LeetCode | LeetCode CH (Medium)
Tags: stack, design
Implement a stack that supports push, pop, top, and retrieving the minimum element in constant time.

155. Min Stack - Python Solution

# 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

155. Min Stack - C++ Solution

#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;
}

150. Evaluate Reverse Polish Notation¶

LeetCode | LeetCode CH (Medium)
Tags: array, math, stack
Steps for the list ["2", "1", "+", "3", "*"]:

token	action	stack
`2`	push	`[2]`
`1`	push	`[2, 1]`
`+`	pop	`[3]`
`3`	push	`[3, 3]`
`*`	pop	`[9]`

150. Evaluate Reverse Polish Notation - Python Solution

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]


print(evalRPN(["2", "1", "+", "3", "*"]))  # 9
print(evalRPN(["4", "13", "5", "/", "-"]))  # 2
print(evalRPN(["18"]))  # 18
print(evalRPN(["4", "3", "-"]))  # 1

22. Generate Parentheses¶

LeetCode | LeetCode CH (Medium)
Tags: string, dynamic programming, backtracking

22. Generate Parentheses - Python Solution

from typing import List


# Backtracking
def generateParenthesis1(n: int) -> List[str]:
    path, res = [], []

    def dfs(openN, closeN):
        if openN == closeN == n:
            res.append("".join(path))
            return

        if openN < n:
            path.append("(")
            dfs(openN + 1, closeN)
            path.pop()

        if closeN < openN:
            path.append(")")
            dfs(openN, closeN + 1)
            path.pop()

    dfs(0, 0)

    return res


# Backtracking
def generateParenthesis2(n: int) -> List[str]:
    m = n * 2
    res, path = [], [""] * m

    def dfs(i, left):
        if i == m:
            res.append("".join(path))
            return

        if left < n:
            path[i] = "("
            dfs(i + 1, left + 1)
        if i - left < left:
            path[i] = ")"
            dfs(i + 1, left)

    dfs(0, 0)
    return res


if __name__ == "__main__":
    print(generateParenthesis1(3))
    # ['((()))', '(()())', '(())()', '()(())', '()()()']
    print(generateParenthesis2(3))
    # ['((()))', '(()())', '(())()', '()(())', '()()()']

739. Daily Temperatures¶

LeetCode | LeetCode CH (Medium)
Tags: array, stack, monotonic stack
Return an array res such that res[i] is the number of days you have to wait after the ith day to get a warmer temperature.

Index	Temp	> stack last	stack	result
0	73	False	`[ [73, 0] ]`	1 - 0 = 1
1	74	True	`[ [74, 1] ]`	2 - 1 = 1
2	75	True	`[ [75, 2] ]`	6 - 2 = 4
3	71	False	`[ [75, 2], [71, 3] ]`	5 - 3 = 2
4	69	False	`[ [75, 2], [71, 3], [69, 4] ]`	5 - 4 = 1
5	72	True	`[ [75, 2], [72, 5] ]`	6 - 5 = 1
6	76	True	`[ [76, 6] ]`	0
7	73	False	`[[76, 6], [73, 7]]`	0

739. Daily Temperatures - Python Solution

from typing import List


# Monotonic Stack
def dailyTemperatures(temperatures: List[int]) -> List[int]:
    res = [0 for _ in range(len(temperatures))]
    stack = []  # [temp, index]

    for i, temp in enumerate(temperatures):
        while stack and temp > stack[-1][0]:
            _, idx = stack.pop()
            res[idx] = i - idx

        stack.append([temp, i])

    return res


print(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]))
# [1, 1, 4, 2, 1, 1, 0, 0]

853. Car Fleet¶

LeetCode | LeetCode CH (Medium)
Tags: array, stack, sorting, monotonic stack

853. Car Fleet - Python Solution

from typing import List


# Stack
def carFleet(target: int, position: List[int], speed: List[int]) -> int:
    cars = sorted(zip(position, speed), reverse=True)
    stack = []

    for p, s in cars:
        time = (target - p) / s

        if not stack or time > stack[-1]:
            stack.append(time)

    return len(stack)


print(carFleet(12, [10, 8, 0, 5, 3], [2, 4, 1, 1, 3]))  # 3

84. Largest Rectangle in Histogram¶

LeetCode | LeetCode CH (Hard)
Tags: array, stack, monotonic stack

84. Largest Rectangle in Histogram - Python Solution

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