Day 8 of LeetCode

Documenting LeetCode solving.

Q1

155. Min Stack

Medium. Stack

Use two stacks. The minStack is to track current minimum number.

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)
        # Remember to append it
        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]

Q2

150. Evaluate Reverse Polish Notation

Medium. Stack

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()
                # int(b/a) is to truncate toward zero
                stack.append(int(b / a))
            else:
                stack.append(int(c))

        return stack[0]

Q3

22. Generate Parentheses

Medium. Stack, back tracking

From Neetcode, youtube.com/watch?v=s9fokUqJ76A

I love Neetcode videos.

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        stack = []
        res = []

        def backtrack(openN, closeN):
            # Base case: valid IIF openN == closeN == n
            if openN == closeN == n:
                res.append("".join(stack))
                return
            # Only add open parenthese if openN < n
            if openN < n:
                stack.append("(")
                backtrack(openN + 1, closeN)
                # Remeber to pop it to return to the previous stage
                stack.pop()
            # Only add close parenthese if closeN < openN
            if closeN < openN:
                stack.append(")")
                backtrack(openN, closeN + 1)
                stack.pop()

        backtrack(0, 0)
        return res

Q4

739. Daily Temperatures

Medium. Stack

Monotonic decreasing stack.

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        res = [0] * len(temperatures)
        stack = [] # pair: [temp, index]

        for i, t in enumerate(temperatures):
            # Pop from stack until the current temperature is smaller
            # then the top one, and update result
            while stack and t > stack[-1][0]:
                stackT, stackInd = stack.pop()
                res[stackInd] = i - stackInd

            stack.append([t, i])

        return res