Stack:

Definitions:

A data structure with the trademark of LIFO (last in, first out). It has direct analogy to the list in Python, and I actually will use the built-in list as the stack. There are alternatives to have a stack (such as queue.LifoQueue), but normally, a python list suffices.

Problems:

1. Valid Parentheses

Intuition

This is the Two Sum of stack. The problem requirements can be translated into the intuition that if I push the left parenthesis into a stack and pop them out whenever I encounter a right parenthesis, the correct parenthesis sequence will generate all matching pairs.

Algorithm

Initialize, including a HashMap for right and left parenthesis, and check that the array has an even number of elements.
Traverse the array of parentheses.
If I encounter a left parenthesis, push it to a stack.
If I encounter a right parenthesis, compare it to the one I pop from the stack. If they do not match, return False immediately.
At the end, return True if the stack is empty, else False.

Complexity

Time complexity: \(O(n)\): Traversing the whole array once.
Space complexity: \(O(n)\): At the worst case, I will need to store half of the array inside the stack.

Code

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2:
            return False
        stack = []
        parenthesisDict = {'{':'}', '[':']', '(':')'}
        for parenthesis in s:
            if parenthesis in parenthesisDict:
                stack.append(parenthesis)
            else:
                if len(stack) == 0 or parenthesis != parenthesisDict[stack.pop()]:
                    return False
        return len(stack) == 0

2. Evaluate Reverse Polish Notation

Intuition

The notation works perfectly with a stack. Basically, whenever you encounter an operand, you need to pop from the end of the stack and perform operation in the correct order before append the result to the stack. Otherwise, just append the numbers in the order I encounter them.

Algorithm

Traverse the list.
If encounter a number, append it to the stack. If encounter an operand, pop from the stack two times, operate, and append the result.
Return the result.

Complexity

Time complexity: \(O(n)\): Traversing the whole array once.
Space complexity: \(O(n)\): At the worst case, I will need to store more than half of the array inside the stack.

Code

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for token in tokens:
            if token =='+':
                a, b = stack.pop(), stack.pop()
                stack.append(a+b)
            elif token =='*':
                a, b = stack.pop(), stack.pop()
                stack.append(a*b)
            elif token =='/':
                a, b = stack.pop(), stack.pop()
                stack.append(int(b/a))
            elif token =='-':
                a, b = stack.pop(), stack.pop()
                stack.append(b-a)
            else:
                stack.append(int(token))
        return stack.pop()

3. Daily Temperatures

Intuition

The number of days to wait is the difference in the indices of the days. The stack comes in handy here by storing the value of the element sequentially, and then I pop from it when I encounter a day with larger temperature.

Algorithm

Initialize the stack and the answer array, which is an array of 0s with the same length as temperatures.
Traverse the array. Storing the value and index to a stack if the value is not larger than the last element in the stack. Pop from the stack and update answer otherwise.
Return answer.

Complexity

Time complexity: \(O(n)\): Traversing the whole array once.
Space complexity: \(O(n)\): At the worst case, I will need to store nearly the whole array inside the stack.

Code

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        answer = [0]*len(temperatures)
        stack = []
        for ind, temp in enumerate(temperatures):
            while stack and stack[-1][0] < temp:
                stackTemp, stackInd = stack.pop()
                answer[stackInd] = ind - stackInd
            stack.append((temp, ind))
        return answer

4. Min Stack

Intuition

The trick is having another stack to store the minimum so far.

Algorithm

With the minimum so far stack, I just need to update it along with the main stack. The main task will be the push operation, where I need to append the new value if it is the new minimum, or the same last value.

Complexity

Time complexity: As required by the problem, everything is in \(O(1)\) time.
Space complexity: I am using two stacks, so it is double the memory. Nevertheless, it is \(O(n)\).

Code

class MinStack:
    # The trick is having the min stack so far
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.min_stack or val < self.min_stack[-1]:
            self.min_stack.append(val)
        else:
            self.min_stack.append(self.min_stack[-1])

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-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()

5. Generate Parentheses

Intuition

The problem gave me a taste of backtracking. It is time to realize that this is possible. Backtracking is built on recursion, which is built on the recursion call stack. So yeah, stack will be present in recursion problem.

In recursion problem, I start with the base case. The base case here revolves around the condition to add left and right parentheses. Simply, I can validly add a left parenthesis if the number of left parentheses is smaller than \(n\), while I can validly add a right parenthesis if the number of left parentheses is smaller than the number of right parentheses. The base case is when the number of left and the number of right all hit \(n\).

Algorithm

Initialize res and stack array. One to return, one to keep track of the string generated.
Define the backtracking function backtrack based on the conditions above.
Call backtrack to update res and return.

Complexity

Time complexity: \(O(\frac{4^n}{\sqrt n})\): It is complicated to derive this time complexity, related to Catalan numbers. An alternative is remembering the brute-force time complexity: \(O(2^{2n}*n)\). At each position in the \(2n\) string there are two ways to choose which parenthesis to add, and checking for validity takes \(O(n)\) time.
Space complexity: \(O(n)\): The maximum depth of the recursive stack.

Code

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        # Backtracking problem
        # Revolve around conditions to add open parenthesis and
        # closed parenthesis
        # Open parenthesis can be added if it is less than n
        # Closed parenthesis can be added if it is less than open
        stack, res = [], []
        
        def backtrack(openN, closedN):
            if openN == closedN == n:
                res.append(''.join(stack))
                return
            
            if openN < n:
                stack.append('(')
                backtrack(openN+1, closedN)
                stack.pop()
            
            if closedN < openN:
                stack.append(')')
                backtrack(openN, closedN+1)
                stack.pop()
        backtrack(0, 0)
        return res

6. Largest Rectangle In Histogram

Intuition

The trick revolves around the condition to extend the rectangle. I can extend the rectangle if the current height is larger than the previous height. If not, I need to pop from the stack, calculate the area of the rectangle and update the maximum area. The next bit is storing the index of the last element that the current height can extend back to instead of its own index.

Algorithm

Initialize maxArea and stack array. One to return, one to keep track of the (index, height) pairs.
Iterate the heights arrray. At each height, if it is smaller than the previous one and the stack is not empty, I pop from the stack, calculate the maximum height possible, update maxArea if necessary, and push (index, height) pair to the stack.
Before return, I need to calculate the area of every rectangle left in the stack. The area is calculated by the height of the rectangle times the width, which is the difference between the current index and the index of the last element in the stack. Update maxArea if necessary and return.

Complexity

Time complexity: \(O(n)\): I iterate through the heights array once, and the stack once.
Space complexity: \(O(n)\): In the worst case, the stack will be the same size as the heights array.

Code

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        maxArea = 0
        stack = [] # (index, height)

        for i, h in enumerate(heights):
            start = i
            while stack and stack[-1][1] > h:
                index, height = stack.pop()
                maxArea = max(maxArea, height * (i-index))
                start = index
            stack.append((start, h))
        
        for i, h in stack:
            maxArea = max(maxArea, h * (len(heights)-i))
        
        return maxArea

7. Implement Queue using Stacks

Intuition

Just as Min Stack needs two stacks to store the values, here two stacks are required to make sure that the queue can \(O(1)\) performance for .pop(). Here, I learnt the meaning of amortized complexity i.e., incurring a debt at first so that subsequent call to the method enjoys discounted cost.

Algorithm

With the second stack, the .pop() method is implemented as followed: if the second stack is empty, elements from the first stack will be popped out one by one and then pushed one by one into the second stack before popping and returning the first element of the first stack. This has a cost of \(O(n)\) and essentially reverse the order of the first stack. Now subsequent .pop() will pop from this second stack, which enjoys \(O(1)\) runtime. For every \(O(n)\) call, subsequent \(n\) calls will enjoy \(O(1)\) cost, which amounts to an amortized cost of \(O(1)\).

Complexity

Time complexity: \(O(1)\): for every method.
Space complexity: \(O(n)\): for storing the two stacks.

Code

class MyQueue:

    def __init__(self):
        self.main_stack = []
        self.head_stack = []

    def push(self, x: int) -> None:
        self.main_stack.append(x)

    def pop(self) -> int:
        if self.empty():
            raise ValueError('The queue is empty!')
        if not self.head_stack:
            for _ in range(len(self.main_stack) - 1):
                temp = self.main_stack.pop()
                self.head_stack.append(temp)
            return self.main_stack.pop()
        return self.head_stack.pop()
    
    def peek(self) -> int:
        if self.empty():
            raise ValueError('The queue is empty!')
        if not self.head_stack:
            return self.main_stack[0]
        return self.head_stack[-1]

    def empty(self) -> bool:
        return len(self.main_stack) == 0 and len(self.head_stack) == 0


# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

8. Basic Calculator

Intuition

There are two ways to do this: 1. Turn the infix expression into postfix expression i.e., reverse Polish notation and use the solution for that problem to solve, which also makes use of stack. 2. Because this calculator only uses '+' and '-', only 1 stack is enough to deal with it.

The calculation will be evaluated from left to right. When you encounter a '(', that is a new expression. The current result will be pushed into the stack.

Algorithm

Initialize variables: an empty stack, result to store the calculated result so far, sign to store the sign, and number to store the current number read from the string.
Iterate the characters in the string. For each character, go into the corresponding case:
1. If char is a digit, add it to current number (multiply number with 10 for correction).
2. If char is a sign, this means a new calculation. Add sign * number to result and reset number to 0. sign is set to the correct sign encountered (via 1 or -1).
3. If char is '(', this means a new prioritized calculation. Cache result and sign to stack (in that order) and reset sign and result.
4. If char is ')', this means the end of prioritized calculation. Set result = sign * number as above, reset the number. Pop from the stack and add the results together with correct sign.
Return result + sign * number i.e., also add the current unevaluated sign * number.

Complexity

Time complexity: \(O(n)\) - iterate through the string.
Space complexity: \(O(n)\) - the size of the stack.

Code

class Solution:
    """
    @param s: the given expression
    @return: the result of expression
    """
    def calculate(self, s: str) -> int:
        # Write your code here
        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)
                sign = 1
                result = 0
            elif char == ')':
                result += sign * number
                number = 0
                result *= stack.pop()
                result += stack.pop()
        return result + sign * number