Stack

Table of Contents

• 20. Valid Parentheses (Easy)
• 155. Min Stack (Medium)
• 394. Decode String (Medium)
• 739. Daily Temperatures (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;
}

394. Decode String

• LeetCode | LeetCode CH (Medium)

• Tags: string, stack, recursion

394. Decode String - Python Solution

# Stack
def decodeString(s: str) -> str:
    stack = []  # (str, int)
    num = 0
    res = ""

    for c in s:
        if c.isdigit():
            num = num * 10 + int(c)
        elif c == "[":
            stack.append((res, num))
            res, num = "", 0
        elif c == "]":
            top = stack.pop()
            res = top[0] + res * top[1]
        else:
            res += c

    return res


s = "3[a2[c]]"
print(decodeString(s))  # accaccacc

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]

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

Comments