Stack

20 Valid Parentheses

Time Complexity: O(1) for all operations

Space Complexity: O(n)

class MinStack:
  def __init__(self):
    self.stack = []
    self.min_stack = []
  
  def push(self, val: int) -> None:
    self.stack.append(val) 
    curr_min = min(val, self.min_stack[-1] if self.min_stack else val)
    self.min_stack.append(curr_min)
    
  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]

150 Evaluate Reverse Polish Notation

def evalRPN(tokens: List[str]) -> int:
  symbols = {'+', '-', '*', '/'}
  
  numbers = []

  for elem in tokens:
    if elem in symbols:
      b = numbers.pop()
      a = numbers.pop()
      match elem:
        case '+':
          numbers.append(a + b)
        case '-':
          numbers.append(a - b)
        case '*':
          numbers.append(a * b)
        case '/':
          numbers.append(int(float(a) / b))
    else:
      numbers.append(int(elem))
  return numbers[-1]

739 Daily Temperature

Time Complexity: O(n)

Space Complexity: O(n)

def dailytemperatures(temperatures: List[int]) -> List[int]:
  res = [0] * len(temperatures)
  stack = []

  for i, t in enumerate(temperatures):
    while stack and stack[-1][1] < t:
      top_idx, _ = stack.pop()
      res[top_idx] = i - top_idx
    stack.append((i, t))
  return res

853 Car Fleet

Time Complexity: O(n * log(n)). zip takes O(n), sorted takes O(n log(n)), the for loop takes O(n).

Space Complexity: O(n). The stack takes O(n) at worst, because we are only recording the fleet (furthest starting position, slowest speed). At worst we have n distinct fleets for n cars.

Note: The car with the furthest starting position forms a barrier. Since cars can’t pass, each trailing car either catches up and merges with the car ahead or never meets it. By sorting cars by position, we can determine fleet formation by comparing their times to reach the target.

def carFleet(target, position, speed):
  stack = [] # (group lead start pos, max time to finish)

  for p, s in sorted(zip(position, speed), key=lambda x: x[0], reverse=True):
    if stack:
      # compare time to finish
      curr_time_left = (target - p) / s
      closest_fleet_time_left = (target - stack[-1][0]) / stack[-1][1]
      if curr_time_left <= closest_fleet_time_left:
        stack[-1] = (stack[-1][0], min(stack[-1][1], s))
      else:
        stack.append((p,s))
    else:
      stack.append((p,s))
  return len(stack)

84 Largest Rectangle in Historgram

Time Complexity: O(n). We itereate through the heights forward once takes O(n), then backward to clear the stack which takes O(n) at worst.

Space Complexity: O(n). The extra stack used to store the tuples

def largestRectangleArea(heights):
  max_area = 0
  stack = [] # (start_indx, height)

  for idx, h in enumerate(heights):
    if stack and stack[-1][1] > h:
      while stack and stack[-1][1] > h:
        top_idx, top_h = stack.pop()
        max_area = max(top_h * (idx - top_idx), max_area)
      stack.append((top_idx, h))
    else:
      stack.append((idx, h))
  
  for idx, h in stack:
    max_area = max(max_area, h * (len(heights) - idx))
  
  return max_area