LeetCode: Stacks

Stack Intro

LeetCode problems with elegant solutions using stacks.

Stack Application: Tracking Nested or Hierarchical Structures

We can track structure while iterating over an object ensuring it maintains some criteria

Ex: Validate if a string containing brackets ()[] is properly balanced:

    def balancedParentheses(s: str) -> bool:
        stack = []
        pairs = {')': '(', ']': '[', '}': '{'}
        for char in s:
            if char in pairs.values():
                stack.append(char)
            elif char in pairs:
                if not stack or stack.pop() != pairs[char]:
                    return False
        return not stack

Stack Application: Backtracking by Tracking History or State

We can use stacks in backtracking to store the state of exploration. When a branch reaches a dead end or a solution, we pop the state to return to the previous state and continue exploring other branches.

Ex: Subset Sum with Backtracking

    def subset_sum(nums, target):
        stack = [(0, [], 0)]  # (index, current_subset, current_sum)
        result = []
        
        while stack:
            index, current_subset, current_sum = stack.pop()
            
            if current_sum > target:  # Prune invalid paths
                continue
            
            if current_sum == target:  # Valid solution
                result.append(list(current_subset))
                continue
            
            # Push new states for further exploration
            for i in range(index, len(nums)):
                stack.append((i + 1, current_subset + [nums[i]], current_sum + nums[i]))
        
        return result

    # subset_sum([2, 3, 6, 7], 7) = [[7]]

Stack Application: Monotonic Property Maintenance

A stack can maintain a monotonic property (increasing or decreasing) over a sequence while processing elements, ensuring efficient lookups or modifications.

Ex: Find the Next Greater Element

    def nextGreaterElement(nums):
        stack = []  # Stores indices of elements in decreasing order
        result = [-1] * len(nums)  # Initialize result with -1
        
        for i in range(len(nums)):
            while stack and nums[i] > nums[stack[-1]]:
                idx = stack.pop()
                result[idx] = nums[i]  # Found the next greater element
            stack.append(i)
        
        return result

    # Example: nextGreaterElement([2, 1, 2, 4, 3]) -> [4, 2, 4, -1, -1]

Stack Application: Simulating Recursion or Call Stacks

We can use a stack to emulate recursion by explicitly managing the call stack.

Ex: Traverse a binary tree in preorder (root -> left -> right):

    def preorderTraversal(root):
        if not root:
            return []
        
        stack = [root]  # Start with the root node
        result = []
        
        while stack:
            node = stack.pop()  # Simulate recursion by processing the top of the stack
            if node:
                result.append(node.val)  # Visit the node
                # Push right child first so the left child is processed next
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)
        
        return result

    # Example: For a tree with root → 1, left → 2, right → 3, preorderTraversal(root) -> [1, 2, 3]

Stack Application: Expression Evaluation and Parsing

We can use a stack to evaluate or parse expressions by storing operands and incrementally applying operators. This approach is well-suited for postfix and prefix notations.

Ex: Post and Prefix

    def evaluatePostfix(expression):
        stack = []  # To hold operands during evaluation
        
        for token in expression.split():
            if token.isdigit():  # If it's an operand, push it to the stack
                stack.append(int(token))
            else:  # If it's an operator, pop two operands and apply the operator
                b = stack.pop()
                a = stack.pop()
                if token == '+':
                    stack.append(a + b)
                elif token == '-':
                    stack.append(a - b)
                elif token == '*':
                    stack.append(a * b)
                elif token == '/':  # Assuming integer division
                    stack.append(a // b)
        
        return stack.pop()  # Final result is the only item left in the stack

    # Example:
    # Input: "3 4 + 2 * 1 +"
    # Output: 15 (Equivalent to (3 + 4) * 2 + 1)

Stack Application: Dynamic Programming State Compression

We can use a stack to compress the necessary state while scanning through data, especially when enforcing a specific constraint or invariant like monotonicity. Instead of storing the entire history, we prune irrelevant elements from the stack to keep only the most useful summary of the past

Ex: Given an array, partition it into the minimum number of strictly increasing subsequences

    def min_partitions(nums):
        stacks = []  # Each element represents the last number in a subsequence
        
        for num in nums:
            placed = False
            for i in range(len(stacks)):
                # If we can append to subsequence i
                if stacks[i] < num:
                    stacks[i] = num
                    placed = True
                    break
            if not placed:
                # Start a new subsequence (partition)
                stacks.append(num)
        return len(stacks)

    # Example usage:
    nums = [1, 3, 2, 4, 6, 5]
    print(min_partitions(nums))  # Output: 2

Stack Application: Interval and Range Processing

We can use stacks to efficiently process intervals or ranges, such as merging overlapping intervals, calculating spans, or finding next/previous smaller or larger elements within a range.

Ex: Largest Rectangle in Histogram

    def largestRectangleArea(heights):
        stack = []  # stores indices of bars
        max_area = 0
        
        for i, h in enumerate(heights + [0]):  # Add sentinel to flush stack
            while stack and heights[stack[-1]] > h:
                height = heights[stack.pop()]
                left = stack[-1] if stack else -1
                width = i - left - 1
                max_area = max(max_area, height * width)
            stack.append(i)
        
        return max_area

    # Example:
    # Input: [2, 1, 5, 6, 2, 3]
    # Output: 10  (largest rectangle is formed by heights 5 and 6)

20. Valid Parentheses ::2:: - Easy

Topics: String, Stack

Intro

Given a string s containing: ( ) [ ] { }, determine if the input string is valid. An input string is valid if: 1. Open brackets must be closed by the same type of brackets 2. Open brackets must be closed in the correct order. 3. Every close bracket has a corresponding open bracket of the same type.

Input	Output
"()"	true
"()"	false
"(]"	true
"([])"	true

Constraints:

1 ≤ s.length ≤ 10⁴

s consists of parentheses only '()[]'

Abstract

We need to validate that every open parenthesis has a matching close in the correct order.

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark
Brute Force (replace with empty)
Stack (redundant operations)
Stack

Brute Force: Replace Pairs with empty

    def isValid(self, s: str) -> bool:
        
        # note: 
        # in python, an empty string "" is falsy evaluating to false
        # not "" -> true

        # each iterate removes at least one pair 
        # there are at most n/2 pairs so O(n/2) iterations O(n/2)
        # each iteration takes O(n)
        # leading to: O(n) * O(n/2) = O(n^2)
        # time complexity: iterate over string of n length O(n)
        while '()' in s or '{}' in s or '[]' in s:
            # time complexity: n/2 replacements O(n/2), per total outer iterations O(n), leading to O(n^2)
            s = s.replace('()', '').replace('{}', '').replace('[]', '')
        
        # overall: time complexity O(n^2)
        # overall: space complexity O(1)
        return not s

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Iterate over string	O(n)	O(1)	Iterate over array of n length O(n)	No additional memory allocation for iteration O(1)
Total Iterations	O(n/2)	O(1)	At most n/2 pairs and thus n/2 removals O(n/2)	No additional memory allocation for iteration O(1)
Overall	O(n²)	O(1)	Single iteration in O(n) for total iterations n/2 O(n/2), leading to O(n²) time complexity	No additional memory allocation for iteration, leading to constant O(1)

Find the Bug: Hashmap Count (does not track order)

    def isValid(self, s: str) -> bool:

        # time complexity: constant hashmap of 3 length O(1)
        counts = {"(": 0, "[": 0, "{": 0}
        closing = {")": "(", "]": "[", "}": "{"}

        # time complexity: iterate over string of n length O(n)
        for c in s:

            # Count opening brackets
            # time complexity: lookup operation in constant O(1)
            if c in counts:  
                counts[c] += 1

            # Count closing brackets
            # time complexity: lookup operation in constant O(1)
            else c in closing:  

                closingMatch = closing[c]

                # No matching opening bracket
                if counts[closingMatch] == 0:  
                    return False

                # Matching opening bracket
                counts[closingMatch] -= 1

        # INCORRECT: hashmap open value may be 0, but did not take into 
        # consideration whether they were in the correct order
        # time complexity: iterate over hashmap of 3 length O(1)
        for count in counts.values():
        if count != 0:
            return False

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return True

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Iterate
Verify
Overall

Find the Bug: Forgot to append to stack

    def isValid(self, s: str) -> bool:

        stack = []
        mapping = {
            ')' : '(',
            ']' : '[',
            '}' : '{'
        }

        for c in s:

            if c in mapping:

                if not stack:
                    return False

                topElem = stack.pop()

                if mapping[c] != topElem:
                    return False 

            # INCORRECT:
            # missing else clause to append char to stack
            # should be:
            # else:
            #   stack.append(c)

        return not stack

Find the Bug: Did not check for empty Stack

    def isValid(self, s: str) -> bool:

        stack = []

        mapping = {
            ')' : '(',
            ']' : '[',
            '}' : '{'
        }

        for c in s:
            
            if c in mapping:

                if not stack:
                    return False

                topElem = stack.pop()

                if mapping[c] != topElem:
                    return False
            else:
                stack.append(c)
        
        # INCORRECT:
        # stack could still have elements and be invalid
        return True

Solution 1: Manual Condition Stack Check - Stack/Tracking Nested or Hierarchical Structures

    def isValid(self, s: str) -> bool:

        # note: in python, an empty list [] is falsy evaluating to false
        # not [] -> true

        # space complexity: stack stores up to n opening brackets O(n)
        stack = []

        # time complexity: iterate over list of n length O(n)
        for c in s:

            # found closing bracket, match with opening bracket
            if c in ')]}':

                # check stack is empty, no matching opening available
                if not stack:
                    return False

                # time complexity: pop in constant O(1)
                topElem = stack.pop()

                # check if opening matches closing
                if  ((c == ')' and topElem != '(') or
                     (c == '}' and topElem != '{') or
                     (c == ']' and topElem != '[')):
                    return False

            # found opening bracket, push to stack
            if c in '([{':
                stack.append(c)
                               
        # if stack is empty, success

        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return not stack

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Iteration	O(n)	O(n)	Iteration string of n length O(n)	Memory allocation for n opening brackets O(n)
Validation	O(1)	O(1)	Pop in constant O(1) and char comparison in constant O(1)	No additional memory allocation for pop or comparison O(1)
Overall	O(n)	O(n)	Iteration over string of n length dominates, leading to O(n)	Memory allocation for stack with n opening brackets dominates, leading to O(n)

Solution 2: Stack with Hashmap lookup - Stack/Tracking Nested or Hierarchical Structures

    def isValid(self, s: str) -> bool:

        # space complexity: stack stores opening brackets for string n length O(n)
        stack = []

        # space complexity: closed -> open mapping in constant O(1)
        mapping = {
            ')' : '(',
            ']' : '[',
            '}' : '{'
        }

        # time complexity: iterate over string of n length O(n)
        for c in s:
            
            # found closing bracket, match with opening bracket
            if c in mapping:

                # check stack is empty, no matching opening available
                if not stack:
                    return False

                # time complexity: pop in constant O(1)
                topElem = stack.pop()

                # check if opening matches closing
                if mapping[c] != topElem:
                    return False
            
            # found opening bracket, push to stack
            else:   
                stack.append(c)
                
        # if stack is empty, success

        # overall: time complexity O(n)
        # overall: space complexity
        return not stack

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Iteration	O(n)	O(n)	Iteration over string of n length O(n)	Memory allocation for stack for n opening brackets O(n)
Validation	O(1)	O(1)	Pop in constant O(1) and char comparison in constant O(1)	No additional memory allocation for pop or comparison O(1)
Overall	O(n)	O(n)	Iteration over string of n length dominates, leading to O(n)	Memory allocation for stack for n opening brackets dominates, leading to O(n)

155. Min Stack ::2:: - Medium

Topics: Stack, Design

Intro

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the MinStack class: MinStack() initializes the stack object. void push(int val) pushes the element val onto the stack. void pop() removes the element on the top of the stack. int top() gets the top element of the stack. int getMin() retrieves the minimum element in the stack. You must implement a solution with O(1) time complexity for each function.

Input	Output
["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]	[null,null,null,null,-3,null,0,-2]

Constraints:

-2³¹ ≤ val ≤ 2³¹ - 1

Methods pop, top and getMin operations will always be called on non-empty stacks.

At most 3 * 10⁴ calls will be made to push, pop, top, and getMin.

Abstract

We need to design a stack that runs in O(1) time complexity for each main function.

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Brute Force:

    def __init__(self):
        
        # tracking logical size vs physical size
        # space complexity: stores all n elements O(n)
        self.stack = []
        self.size = 0

    def push(self, val: int) -> None:
        # time complexity: append operation in constant O(1)

        # size = 1     vs [5, _, _]
        # logical size vs physical size -> 
        # stack will only grow when absolutely necessary / avoids unnecessary resizing
        if self.size < len(self.stack):
            # self.size == length, so append at self.size
            self.stack[self.size] = val
        else:
            # stack needs to grow
            self.stack.append(val)

        # increases logical size
        self.size += 1

    def pop(self) -> None:       
        if self.size == 0:
            raise IndexError("Pop from empty stack")

        # size = 2 [5, 4]
        # size = 1 [5, 4]
        # logical size vs physical size -> 
        # time complexity: pop operation in constant O(1)

        # decreases logical size
        self.size -= 1

    def top(self) -> int:
        if self.size == 0:
            raise IndexError("Stack is empty")
 
         # time complexity: index top element in constant O(1)
        return self.stack[self.size - 1]

    def getMin(self) -> int:
        if self.size == 0:
            raise IndexError("Stack is empty")
        
        minVal = float('inf')

        # stack is not minSorted
        # time complexity: iterate over entire stack n length O(n)
        for i in range(self.size):
            if self.stack[i] < minVal:
                min = self.stack[i] 
        return minVal

    # overall: time complexity O(n)
    # overall: space complexity O(n)

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

    def __init__(self):
        # space complexity: 
        self.stack = []
        self.size = 0
        self.minVal = float('inf')

    def push(self, val: int):
        # time complexity:
        if self.size < len(self.stack)
            self.stack[self.size] = val
        else:
            self.stack.append(val)

        # increases logical size
        self.size += 1

        if val < self.minVal:
            self.minVal = val

    def pop(self):
        # time complexity:
        if self.size == 0:
            raise IndexError("Pop from empty stack")
        
        # decreases logical size
        # INCORRECT: does not update minVal when the popped value is the minVal
        # Stack implementation does not track previous minVal for updates
        self.size -= 1

        
    def top(self):
        # time complexity:
        if self.size == 0:
            raise IndexError("Stack is empty")
        
        return self.stack[self.size - 1]

    def getMin(self):
        # time complexity:
        return self.minVal

    # overall: time complexity
    # overall: time complexity

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Solution 1: 2 Stacks for main and min - Stack/Dynamic Programming State Compression

class MinStack:

    # overall: space complexity O(n)
    def __init__(self):

        # Note:
        # minTracker stack tracks the min value at each level of the main stack. 

        # space complexity: two stacks for n elements O(n)

        # stores all pushed values
        self.mainStack = []
        # for each level, stores minimum value
        self.minTracker = []
        # logical size
        self.mainSize = 0

    def _validateNotEmpty(self, errMsg: str):
        if self.mainSize == 0:
            raise IndexError(errMsg)

    def _compressStack(self, stack):
        return self.mainSize < len(stack)
            
    # overall: time complexity O(1)
    def push(self, val: int):

        # add new val at index or append
        if self._compressStack(self.mainStack):
            self.mainStack[self.mainSize] = val
        else:
            self.mainStack.append(val)

        # add new min at index or append
        if self._compressStack(self.minTracker):
            # min between (new value, previous level of min stack)
            self.minTracker[self.mainSize] = min(val, self.minTracker[self.mainSize - 1] if self.mainSize > 0 else val)
        else:
            self.minTracker.append(min(val, self.minTracker[self.mainSize - 1] if self.mainSize > 0 else val))
        
        # increases logical size
        self.mainSize += 1

    # overall: time complexity O(1)
    def pop(self):
        # validate non empty, decrease logical length
        self._validateNotEmpty("Invalid pop, stack is empty")
        self.mainSize -= 1

    # overall: time complexity O(1)
    def top(self):
        # validate non empty, return elem
        self._validateNotEmpty("Invalid top, stack is empty")
        return self.mainStack[self.mainSize - 1]

    # overall: time complexity O(1)
    def getMin(self):
        # validate non empty, return min
        self._validateNotEmpty("Invalid getMin, stack is empty")
        return self.minTracker[self.mainSize - 1]

    # overall: time complexity O(1)
    # overall: space complexity O(n)

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Push	O(1)	O(1)	Insert to main and min stack in constant O(1)	No additional memory allocation for push operation O(1)
Pop	O(1)	O(1)	Decrease logical length in constant O(1)	No additional memory allocation for logical length decrease O(1)
Top	O(1)	O(1)	Indexing into main array in constant O(1)	No additional memory allocation for indexing array O(1)
getMin	O(1)	O(1)	Indexing into min array in constant O(1)	No additional memory allocation for indexing array O(1)
Overall	O(1)	O(n)	Each individual operation takes constant O(1)	MainStack and minTracker memory allocation dominate for n values, leading to O(n)

Solution 2: Tuple Stack - Stack/Dynamic Programming State Compression

class MinStack:
    
    # overall: space complexity O(n)
    def __init__(self):

        # Note: 
        # We combine the main and minTracker stack via a tuple (val, min), 
        # to track the min at each level of the stack.

        # space complexity: stores all pushed tuples (val, min) O(n)
        self.stack = []
        self.size = 0

    def _validateNotEmpty(self, errMsg: str):
        if self.size == 0:
            raise IndexError(errMsg)

    def _compressStack(self):
        return self.size < len(self.stack)

    # overall: time complexity O(1)
    def push(self, val: int):

        # min between (new value, previous level of stack)
        currMin = min(val, self.stack[self.size - 1][1] if self.size > 0 else val)
        
        # update min at index, or append
        if self._compressStack():
            self.stack[self.size] = (val, currMin)
        else:
            self.stack.append((val, currMin))

        # increases logical size
        self.size += 1

    # overall: time complexity O(1)
    def pop(self):
        self._validateNotEmpty("Invalid pop, stack is empty")
        self.size -= 1

    # overall: time complexity O(1)
    def top(self):
        self._validateNotEmpty("Invalid top, stack is empty")
        return self.stack[self.size - 1][0]

    # overall: time complexity O(1)
    def getMin(self):
        self._validateNotEmpty("Invalid getMin, stack is empty")
        return self.stack[self.size - 1][1]

    # overall: time complexity O(1)
    # overall: space complexity O(n)

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Push	O(1)	O(1)	Insert into stack in constant O(1)	No additional memory allocation for insert O(1)
Pop	O(1)	O(1)	Decrease logical length in constant O(1)	No additional memory allocation for decreasing logical length O(1)
Top	O(1)	O(1)	Indexing into array in constant O(1)	No additional memory allocation for indexing O(1)
getMin	O(1)	O(1)	Indexing into array in constant O(1)	No additional memory allocation for indexing O(1)
Overall	O(1)	O(n)	Each individual operation takes constant O(1)	Stack memory allocation dominates for n values, leading to O(n)

150. Evaluate Reverse Polish Notation ::1:: - Medium

Topics: Array, Stack, Math, Design

Intro

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation. Evaluate the expression. Return an integer that represents the value of the expression. Note that: The valid operators are '+', '-', '*', and '/'. Each operand may be an integer or another expression. The division between two integers always truncates toward zero. There will not be any division by zero. The input represents a valid arithmetic expression in a reverse polish notation. The answer and all the intermediate calculations can be represented in a 32-bit integer.

Input	Output
["2","1","+","3","*"]	9
["4","13","5","/","+"]	6
["10","6","9","3","+","-11","","/","","17","+","5","+"]	22

Constraints:

1 ≤ tokens.length ≤ 10⁴

tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

Abstract

We're designing abstract syntax tree that when execute, will execute the given operations in reverse polish notation.

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Brute Force:

    def evalRPN(self, tokens: List[str]) -> int:
        stack = []

        for token in tokens:
            if token not in "+-*/":
                # Push operand onto stack
                stack.append(int(token))
            else:
                # Pop two operands
                b = stack.pop()
                a = stack.pop()
                
                # Perform operation and push result
                if token == "+":
                    stack.append(a + b)
                elif token == "-":
                    stack.append(a - b)
                elif token == "*":
                    stack.append(a * b)
                elif token == "/":
                    stack.append(int(a / b))  # Truncate towards 0

        return stack.pop()

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug: Operand Order

    def evalRPN(self, tokens: List[str]) -> int:
        stack = []

        for token in tokens:
            if token not in "+-*/":
                stack.append(int(token))
            else:

                # INCORRECT order of popping operands
                a = stack.pop()  # a should be second operand
                b = stack.pop()  # b should be the first operand
                
                if token == "+":
                    stack.append(a + b)  # Incorrect operand order
                elif token == "-":
                    stack.append(a - b)  # Incorrect operand order
                elif token == "*":
                    stack.append(a * b)  # Correct, since order doesn't matter
                elif token == "/":
                    stack.append(int(a / b))  # Incorrect operand order

        return stack.pop()

Find the Bug: Pushing Characters onto stack instead of Int

    def evalRPN(self, tokens: List[str]) -> int:
        
        stack = []

        for token in tokens:

            # found operand, push to stack
            if token not in "+-*/":
                
                # INCORRECT:
                # pushed chars instead of int onto stack
                stack.append(token)
            
            # found operator, calculate
            else:

                # stack:
                # [1, 6, 3] 
                # INCORRECT:
                # should not need to do int() when popping
                # this is a band aid 
                b = int(stack.pop()) # b
                a = int(stack.pop()) # a

                if token == "+":
                    stack.append(a+b)
                elif token == "-":
                    stack.append(a-b)
                elif token == "*":
                    stack.append(a*b)
                elif token == "/":

                    # truncate towards 0
                    # -5 / 2 = -2.3333 -> -2.0
                    # not floor, but int()
                    stack.append(int(a/b))

        # return top of stack
        # INCORRECT:
        # stack is list of characters, will return "2" instead of 2
        # error fixed when appending
        return stack[-1]

Solution 1: Postfix Expression Evaluation Algorithm - Stack/Expression Evaluation and Parsing

    def evalRPN(self, tokens: List[str]) -> int:
        # space complexity: stack holds up to n/2 intermediate results O(n)
        stack = []

        # time complexity: iterate over tokens array of n length O(n)
        for token in tokens:

            # found operand, cast to int and push to stack
            if token not in "+-*/":
                stack.append(int(token))
            
            # found operator, grab operands and compute
            else:
                # time complexity: pop two operands from stack O(1)
                # input:    ["4","13","5","/","+"]
                # expected: 4 + (13 / 5) = 6
                # "4"    -> [4]
                # "13"   -> [4, 13]
                # "5"    -> [4, 13, 5]
                # "/"    -> [4, 2]         # a = 13, b = 5 → int(13 / 5) = 2
                # "+"    -> [6]            # a = 4, b = 2 → 4 + 2 = 6

                # 5
                b = stack.pop()
                # 13
                a = stack.pop()

                # apply operator manually and push result
                match token:
                    case "+":
                        stack.append(a + b)
                    case "-":
                        stack.append(a - b)
                    case "*":
                        stack.append(a * b)
                    case "/":
                        # a / b
                        # 13 / 5

                        # Explicit truncation towards zero
                        # -7 / 3         # -2.333  division:        leaves remainder
                        # -7 // 3        # -3      floor division:  rounds down "towards infinity"
                        # int(-7 / 3)    # -2      int(division):   truncates "toward 0", as required by RPN
                        stack.append(int(a / b))

        # return top of stack

        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return stack[-1]

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Operands Stack	O(1)	O(n)	Insert into operands stack in constant O(1)	Stack will store at most n/2 operands, leading to O(n)
Token iteration	O(n)	O(1)	Iteration over tokens array of n length O(n)	No additional memory allocation for iteration O(1)
Stack operations	O(1)	O(1)	Push and pop from stack in constant O(1)	No additional memory allocation for stack operations O(1)
Stack operations	O(1)	O(1)	Add, sub, multi, and div all in constant O(1)	No additional memory allocation for operations
Overall	O(n)	O(n)	Iterating over tokens array dominates, leading to O(n)	Operands stack for token array of n length dominates, leading to O(n)

22. Generate Parentheses ::4:: - Medium

Topics: String, Stack, Dynamic Programming, Backtracking

Intro

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Input	Output
1	["()"]
3	["((()))","(()())","(())()","()(())","()()()"]

Constraints:

1 ≤ n ≤ 8

Abstract

Given a number, generate all possible combinations of parentheses.

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Brute Force:

    def generateParenthesis(self, n: int) -> List[str]:
        
        # generates all possible combinations of n pairs of parentheses
        def generate_combinations(current, length, combinations):
            
            # base case: if 
            if length == 2 * n:
                combinations.append(current)
                return

            # recursively add '(' and ')' to the current string to generate all possible combinations
            generate_combinations(current + "(", length + 1, combinations)
            generate_combinations(current + ")", length + 1, combinations)

        # checks if given parentheses string is valid
        def isValid(s: str) -> bool:
            # counter to track balance of parentheses
            balance = 0

            # iterate through parentheses string
            for char in s:
                
                # increment balance
                if char == '(':
                    balance += 1
                # decrement balance
                else:
                    balance -= 1
                # closing parenthesis has no matching
                if balance < 0:
                    return False

            # validate all parentheses have match
            return balance == 0

        # grab all possible combinations
        combinations = []
        generate_combinations("", 0, combinations)

        result = []
        
        # generate and validate all combinations
        for combo in combinations:
            if isValid(combo):
                result.append(combo)
        
        # overall: time complexity
        # overall: space complexity
        return result

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug: Adding Closing Parentheses Before Opening

    def generateParenthesis(self, n: int) -> List[str]:
        
        # Initialize a stack to simulate depth-first search (DFS)        
        # (currString, openParenCount, closedParenCount)
        stack = [("", 0, 0)]
        result = []

        # while stack is non-empty
        while stack:

            # 
            current, openCount, closeCount = stack.pop()

            # if we have a valid combination of n '(' and n ')' add to list
            if openCount == n and closeCount == n:
                result.append(current)
                continue

            # INCORRECT: condition allows ')' to be added even if they exceed the number of '('
            # should be `closeCount < openCount`
            if closeCount < n:
                stack.append((current + ")", openCount, closeCount + 1))
            if openCount < n:
                stack.append((current + "(", openCount + 1, closeCount))

        # overall: time complexity
        # overall: space complexity
        return result

Find the Bug: Else clause instead of Adding Closed Parentheses based on Open Count

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

        def helper(curr, open_count, close_count):

            if open_count + close_count == (2*n):
                res.append("".join(curr))
                return

            if open_count < n:
                curr.append('(')
                helper(curr, open_count + 1, close_count)
                curr.pop()
            
            # INCORRECT:
            # we only want to add a closing parentheses if the closed count 
            # is less than the opening parentheses count
            # to ensure that every closed has a matching open
            # Instead:
            # if close_count < open_
            else:
                curr.append(')')
                helper(curr, open_count, close_count + 1)
                curr.pop()

            
        helper([], 0, 0)

        return res

Find the Bug: Mutually exclusive if and if instead of if and elif

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

        def helper(curr, open_paren, close_paren):

            if open_paren == n and close_paren == n:
                res.append("".join(curr))
                return

            if open_paren < n:
                curr.append('(')
                helper(curr, open_paren + 1, close_paren)
                curr.pop()
            
            # INCORRECT:
            # the two if statements should be mutually exclusive
            # we do not one to skip the elif, when the if is true
            # Instead:
            # if close_paren < open_paren
            elif close_paren < open_paren:
                curr.append(')')
                helper(curr, open_paren, close_paren + 1)
                curr.pop()

        helper([], 0, 0)

        return res

Find the Bug: list.append() modifies in place and returns None

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

        def helper(curr, open_count, close_count):

            if open_count + close_count == (2*n):
                res.append("".join(curr))
                return

            if open_count < n:
                # INCORRECT:
                # treating list as string
                # list.append() modifies the list in-place and returns None.
                # So curr.append('(') does append the character, but returns None
                # instead:
                # curr.append()
                # helper(curr, open_count + 1, close_count)
                # curr.pop()
                helper(curr.append('('), open_count + 1, close_count)

            if close_count < open_count:
                # INCORRECT:
                # treating list as string
                # list.append() modifies the list in-place and returns None.
                # So curr.append('(') does append the character, but returns None
                # instead:
                # curr.append()
                # helper(curr, open_count + 1, close_count)
                # curr.pop()
                helper(curr.append(')'), open_count, close_count + 1)

        stack = []
        helper(stack, 0, 0)

        return res

Find the Bug: Iterative Affects Other Branches Instead of Recursive

    def generateParenthesis(self, n: int) -> List[str]:

        # Note:
        # Explicit stack simulates backtracking process iteratively.
        # Each stack element stores the current string and counts of open and closed parentheses.
        # Allows state tracking without recursion.

        # Store valid parentheses
        result = []

        # Tracks state (current_string, open_count, closed_count)
        stack = [([], 0, 0)] 

        # Simulate backtracking
        # time complexity: each state processed once, building up to O(Catalan(n)) strings
        # space complexity: stack can grow to O(Catalan(n)), result stores O(Catalan(n)) strings
        while stack:

            # Pop current state, current state is explored only once
            curr, openCount, closeCount = stack.pop()

            # Base case: reached valid string
            if openCount == n and closeCount == n:
                result.append("".join(curr))
                continue

            # Check: open count is less than total expected
            # Ensures: string is always valid, with total number of parens being valid
            # Iterative step 1: add '('
            if openCount < n:
                
                # INCORRECT:
                # since there is only 1 curr,
                # appending will affect all branches
                # Instead:
                # make a copy
                # new_curr = curr + ['(']
                curr.append('(')
                stack.append((curr, openCount + 1, closeCount))

            # Check: closed count is less than open count
            # Ensures: string is always valid, with each open having a matching close
            # Iterative step 2: add '('
            if closeCount < openCount:
                # INCORRECT:
                # since there is only 1 curr,
                # appending will affect all branches
                # Instead:
                # make a copy
                # new_curr = curr + ['(']
                curr.append(')')
                stack.append((curr, openCount, closeCount + 1))

        # overall: time complexity O(Catalan(n) * n)
        # overall: space complexity O(Catalan(n) * n)
        return result

Find the Bug: Forgot to initialize 0th level of DP

    def generateParenthesis(self, n: int) -> List[str]:

        dp = [[] for i in range (n+1)]

        # INCORRECT:
        # dp is never initialized, so it can never be built upon
        # Instead:
        # dp[0] = [""]

        # generate for level i pairs
        for i in range(n+1):

            # iterate over created lists up to i
            for j in range(i):

                # forward iteration
                for left in dp[j]:
                    # backward iteration
                    for right in dp[i - 1 - j]:
                        dp[i].append(f"({left}){right}")


        return dp[n]

Find the Bug: Forgot to update Parentheses count

    def generateParenthesis(self, n: int) -> List[str]:

        res = []

        def helper(currList, openCount, closedCount):

            if openCount + closedCount == (2*n):
                res.append("".join(currList))
                return

            if openCount < n:
                currList.append("(")
                helper(currList, openCount+1, closedCount)
                currList.pop()

            if closedCount < openCount:
                currList.append(")")
                
                # INCORRECT:
                # closed count was not updated
                # Instead:
                # helper(currList, openCount, closedCount + 1)
                helper(currList, openCount, closedCount)
                currList.pop()

        
        helper([], 0, 0)

        return res

Find the Bug: Cannot initialize empty list with multiplication, use bucket sort method

def generateParenthesis(self, n: int) -> List[str]:

        # INCORRECT:
        # Instead:
        # dp = [[] for i in range(n+1)]
        dp = [] * (n+1)

        dp[0] = [""]

        for i in range(n+1):

            for j in range(i):

                for left in dp[j]:
                    for right in dp[i-1-j]:
                        dp[i].append(f"({left}){right}")

        return dp[n]

Solution 1: BackTracking Recursive with String Concatenation - Stack/Backtracking by Tracking History or State

    def generateParenthesis(self, n: int) -> List[str]:

        # Note:
        # Backtracking explores all valid sequences of parentheses.
        # A new string is created on each recursive call using string 
        # concatenation for string length up to 2n leading to O(n^2).

        res = []

        # Backtracking        
        # space complexity: call stack depth is O(n), string copying adds O(n) per leaf path, leading to O(n^2)
        def helper(current: List[str], num_open: int, num_closed: int):

            # Base case: if the length of the current combination is 2 * n, it's complete
            if len(current) == n * 2:
                # time complexity: concat add to res for 2n length O(n)
                res.append(current)
                return

            # Check: open count is less than total expected
            # Ensures: string is always valid, with total number of parens being valid
            # Recursive case 1: add '('
            if num_open < n: 
                # time complexity: concat per iteration O(n)
                helper(current + "(", num_open + 1, num_closed)
            
            # Check: closed count is less than open count
            # Ensures: string is always valid, with each open having a matching close
            # Recursive case 2: add ')'
            if num_closed < num_open:
                # time complexity: concat per iteration O(n)
                helper(current + ")", num_open, num_closed + 1)

        # Start backtracking process with an empty list and counts at 0
        helper("", 0, 0)

        # overall: time complexity O(Catalan(n) * n^2)
        # overall: space complexity O(Catalan(n) * n)
        return res

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Recursive Paths	O(Catalan(n))	O(n)	Explanation of Catalan Derivation
String concatenation	O(n) per path	O(n) per result	Explanation of total O(n²) is the same as the double for loop derivation
Overall	O(Catalan(n) * n²)	O(Catalan(n) * n)	Catalan(n) unique strings with copy cost dominates as string grows O(n²) per solution dominates, leading to O(Catalan(n) * n²)	Catalan(n) valid strings each of length 2n dominates, leading to O(Catalan(n) * n)

Solution 2: BackTracking Recursive with Mutable List - Stack/Backtracking by Tracking History or State

    def generateParenthesis(self, n: int) -> List[str]:
        
        # Note:
        # Backtracking explores all valid sequences of parentheses.
        # Only when a complete sequence is found (length == 2 * n), 
        # we convert the list to a string via concat in O(n)

        res = []
        
        # Backtracking
        # time complexity: each recursion explores a state; only leaf call does ''.join(), leading to O(n)
        # space complexity: call stack depth O(n), current list holds up to 2n
        def backtrack(current, openCount, closeCount):

            # Base case: if we have used all open and close parentheses
            if openCount == n and closeCount == n:
                # time complexity: convert once at leaf for 2n length O(n)
                res.append("".join(current))
                return
            
            # Check: open count is less than total expected
            # Ensures: string is always valid, with total number of parens being valid
            # Recursive case 1: add '('
            if openCount < n: 
                current.append('(')

                # Recursive call explores all combinations from new state
                helper(current, openCount + 1, closeCount)

                # Backtrack by removing the last added '('
                current.pop()
            
            # Check: closed count is less than open count
            # Ensures: string is always valid, with each open having a matching close
            # recursive case: add ')'
            if closeCount < openCount:

                current.append(')')

                # Recursive call explores all combinations starting from new state
                helper(current, openCount, closeCount + 1)

                # Backtrack by removing the last added ')'
                current.pop()

        # starts recursion with an empty string and zero counts
        backtrack([], 0, 0)

        # overall: time complexity O(Catalan(n) * n)
        # overall: space complexity O(Catalan(n) * n)
        return res

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Recursive paths	O(Catalan(n))	O(n)	Exponential branching	Stack depth of 2n
String creation	O(n) per complete path	O(n) per result	Only joined once per result	Each string result is size 2n
Overall	O(Catalan(n) * n)	O(Catalan(n) * n)	Avoids repeated copies	Stores all valid combinations

Solution 3: Iterative State Tracking Stack - Stack/Backtracking by Tracking History or State

    def generateParenthesis(self, n: int) -> List[str]:

        # Note:
        # Explicit stack simulates backtracking process iteratively.
        # Each stack element stores the current string and counts of open and closed parentheses.
        # Allows state tracking without recursion.

        # Store valid parentheses
        result = []

        # Tracks state (current_string, open_count, closed_count)
        stack = [([], 0, 0)] 

        # Simulate backtracking
        # time complexity: each state processed once, building up to O(Catalan(n)) strings
        # space complexity: stack can grow to O(Catalan(n)), result stores O(Catalan(n)) strings
        while stack:

            # Pop current state, current state is explored only once
            curr, openCount, closeCount = stack.pop()

            # Base case: reached valid string
            if openCount == n and closeCount == n:
                result.append("".join(curr))
                continue

            # Check: open count is less than total expected
            # Ensures: string is always valid, with total number of parens being valid
            # Iterative step 1: add '('
            if openCount < n:
                
                # copy list to avoid mutating other branches
                new_curr = curr + ['(']
                stack.append((new_curr, openCount + 1, closeCount))

            # Check: closed count is less than open count
            # Ensures: string is always valid, with each open having a matching close
            # Iterative step 2: add '('
            if closeCount < openCount:
                new_curr = curr + [')']
                stack.append((new_curr, openCount, closeCount + 1))

        # overall: time complexity O(Catalan(n) * n)
        # overall: space complexity O(Catalan(n) * n)
        return result

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
States explored	O(Catalan(n))	O(n) per path	One entry and exit per valid state	Stack holds up to O(Catalan(n)) intermediate states
Mutable list ops	O(1) per op	O(n) per path	Append and pop are in-place (no copies)	Each state contains up to 2n
Final string join	O(n) per result	O(n) per result	Each completed list is joined into a string once	Output list contains O(Catalan(n)) strings, each of length O(n)
Overall	O(Catalan(n) * n)	O(Catalan(n) * n)	One entry and exit per valid state exploring ?	Final output dominates space; stack and temp lists also contribute O(n) each

Solution 4: Dynamic Programming Building Parentheses Combinations - Stack/Dynamic Programming State Compression

    def generateParenthesis(self, n: int) -> List[str]:
        
        # Note:
        # We exploit the recursive structure of Catalan numbers
        # by building a list of all valid parentheses combinations for each level n

        # dp:    list of list of parentheses combinations 
        # dp[n]: list containing all valid parenthesis combinations for n pairs
        dp = [[] for i in range(n + 1)]
        
        # Base case: valid combination for n = 0
        dp[0] = [""]  
        
        # Iterate: create valid lists from dp[1] to dp[n]
        # Current: building list for i pairs
        # time complexity: iterate over list of n length O(n) 
        for i in range(1, n + 1): 

            # iterate over stored lists up to now
            for j in range(i):  

                # Setup: Two Pointer Variation: Opposite Ends

                # forward iteration: over each valid string of parentheses for level j
                # start: first parentheses pairs level (0) pairs
                for left in dp[j]:

                    # reverse iteration: over each valid string of parentheses for level (i - 1 - j)
                    # start: last parentheses pairs level (i-1) pairs
                    for right in dp[i - 1 - j]:

                        # Two Pointer Variation: Opposite Ends
                        # as pointers meet in middle, number of parentheses will remain balanced
                        # which allows us to just add them randomly within valid rules:

                        # Why:
                        # ({left}){right} or {left}({right}) are both valid formulas
                        # Since we are doing Opposite Ends and left and right will cross over each other,
                        # left and right will both individually use all values
                        # which means with these 2 iterations
                        # we are eventually doing both ({left}){right} and {left}({right})

                        dp[i].append(f"({left}){right}")

        # overall: time complexity O(Catalan(n) * n)
        # overall: space complexity O(Catalan(n) * n)
        return dp[n]

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
DP State build	O(Catalan(n))	O(Catalan(n))	Combines all previous results	dp[0] to dp[n] built cumulatively
String construction	O(n) per combination	O(n) per result	Each result takes O(n) to form	Final dp[n] holds all combinations
Overall	O(Catalan(n) * n)	O(Catalan(n) * n)	No recursion but same asymptotic bound	Store all intermediate and final results

739. Daily Temperatures ::3:: - Medium

Topics: Array, Stack, Monotonic Stack, Two Pointers, Dynamic Programming

Intro

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Input	Output
[30,40,50,60]	[1,1,1,0]
[30,60,90]	[1,1,0]
[73,74,75,71,69,72,76,73]	[1,1,4,2,1,1,0,0]

Constraints:

1 ≤ temperatures.length ≤ 10⁵

30 ≤ temperatures[i] ≤ 100

Abstract

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Brute Force: Stack

    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        
        # space complexity: 
        n = len(temperatures)
        res = [0] * n

        # time complexity: iterate over list of n length O(n)
        for i in range(n):

            # time complexity: iterate over list of n length per outer iteration O(n^2)
            for j in range(i + 1, n):

                # found higher temperature, calculate difference
                if temperatures[j] > temperatures[i]:
                    res[i] = j - i
                    break  # Stop once the first warmer day is found
        
        # overall: time complexity O(n^2)
        # overall: space complexity O(1)
        return res

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug: Forgot to Push onto Stack

    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        
        # space complexity:
        st = []
        res = [0] * len(temperatures)

        # time complexity:
        for i in range(len(temperatures)):

            # 
            while st and temperatures[i] > temperatures[st[-1]]:
                idx = st.pop()
                res[idx] = i - idx  # Correctly compute days difference

            # INCORRECT: current day i is never pushed 

        return res

Find the Bug: Comparing Indexes to Temperatures, instead of Temp to Temp

    def dailyTemperatures(self, temperatures: List[int]) -> List[int]: 

        # foward track colder days
        # monotonic decreasing
        stack = []

        res = [0] * len(temperatures)

        # time complexity: iterate over index temperatures
        for i in range(len(temperatures)):

            # Check: stack is non empty
            # Check: if current breaks monotonic decreasing
            # Implies: have found higher temperature
            # Then: pop and calculate

            # INCORRECT:
            # stack[-1] is an index of a temperature
            # and we are comparing it to a temperature
            # Instead:
            # while stack and temperature[stack[-1]] < temperatures[i]:
            while stack and stack[-1] < temperatures[i]:

                #   0  1  2  3
                # [ 8, 6, 3, 9]
                # 9 pops ever element
                # index of lower temperature
                lowerTempIndex = stack.pop()

                # calculate distance between higher temp and curr low temp
                res[lowerTempIndex] = i - lowerTempIndex

            stack.append(i)

        return res

Find the Bug: Pop with If Statement instead of a While Loop

    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:  

        # foward track colder days
        # monotonic decreasing
        stack = []

        res = [0] * len(temperatures)

        # time complexity: iterate over index temperatures
        for i in range(len(temperatures)):

            # Check: stack is non empty
            # Check: if current breaks monotonic decreasing
            # Implies: have found higher temperature
            # Then: pop and calculate

            # INCORRECT:
            # using if statement to pop()
            # which i\
            # instead of using while loop to pop
            # while monotonic property is broken
            # 
            if stack and temperatures[stack[-1]] < temperatures[i]:

                #   0  1  2  3
                # [ 8, 6, 3, 9]
                # 9 pops ever element
                # index of lower temperature
                lowerTempIndex = stack.pop()

                # calculate distance between higher temp and curr low temp
                res[lowerTempIndex] = i - lowerTempIndex

            stack.append(i)

        return res

Find the Bug: Added extra if else statement during day calculation

    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:

        dp = [0] * len(temperatures)

        hottest_day = temperatures[len(temperatures)-1]

        for i in range(len(temperatures)-2, -1, -1):

            if temperatures[i] >= hottest_day:
                hottest_day = temperatures[i]
            else:
                
                j = i+1
                # INCORRECT:
                # no need for if else statement,
                # as hottest_day check + while loop guarantees
                # there to be a hotter day eventually
                # Instead:
                # remove if else, leave while loop:
                # j = i+1
                # while temperatures[i] >= temperatures[j]:
                #   j += dp[j]
                # dp[i] = j - i
                if temperatures[i] < temperatures[j]:
                    dp[i] = j-i

                else:
                    while temperatures[i] >= temperatures[j]:
                        j += dp[j]
                    dp[i] = j - i
        return dp

Find the Bug: Reverse Iteration, forgot to pop matching old hot Temperatures

    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:

        # monotonic decreasing 
        stack = []
        res = [0] * len(temperatures)


        for i in range(len(temperatures)-1, -1, -1):

            # monotonic decreasing broken
            # INCORRECT:
            # only popping index if temperature is greater than
            # however, we also want to pop if new hot temperature
            # matches old ho temperature as we want to track 
            # more recent days 
            # Instead:
            # while stack and temperatures[stack[-1]] <= temperatures[i]
            while stack and temperatures[stack[-1]] < temperatures[i]:
                stack.pop()

            # there is a hotter temperature left
            if stack:
                res[i] = stack[-1] - i

            stack.append(i)

        return res

Find the Bug: Dynamic, forgot to replace hottest_day with equal temperatures

    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:

        n = len(temperatures)
        dp = [0] * n

        hottest_day = temperatures[n-1]

        for i in range(n-2, -1, -1):

            # INCORRECT:
            # need to remove to equal hot day as well
            # Instead:
            # if temperatures[i] >= hottest_day:
            if temperatures[i] > hottest_day:
                hottest_day = temperatures[i]

            else:
                j = i + 1

                while temperatures[i] >= temperatures[j]:
                    j += dp[j]

                dp[i] = j-i

        return dp

Solution 1: Forward Iteration Monotonic Decreasing Stack of Cold Temps - Stack/Monotonic Property Maintenance

    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        
        # Note:
        # Monotonic Stack: A stack that maintains monotonic decreasing temperatures 
        # When monotonic decreasing rule breaks, the current temperature will serve as new higher temperature,
        # and if stack is non empty, wait days distance for top of stack 
        # while monotonic decreasing rule breaks 

        # space complexity: list wait days for n temperatures O(n)
        n = len(temperatures)
        res = [0] * n

        # space complexity: stores indices for up to n unresolved temperatures O(n)
        stack = []

        # time complexity: iterate over list of n length O(n)
        for i in range(n):

            # Check: stack is non empty, unresolved temperature exists
            # Check: if current temperature[i] breaks monotonic decreasing order,
            # will be viable to act as right temperature
            # implies: we keep appending while monotonic decreasing stays valid
            # implies: stack is kept in monotonic decreasing order
            # implies: when monotonic decreasing breaks, we have found right temperature
            while stack and temperatures[stack[-1]] < temperatures[i]:
                
                # curr while loop iteration:
                # temperatures[i]: right temperature
                # pop stack[-1]: tempWaitDaysCandidateIndex

                # while stack is non-empty:
                # stack.pop() will iterate tempWaitDays candidate
                # essentially dragging the right temperature over the monotonic stack,
                # calculating all the tempWaitDays, until a temperature is higher than
                # the current right temperature,
                # then we just add the right wall to the stack maintaining monotonic order
                tempWaitDaysCandidateIndex = stack.pop()
                
                # After stack.pop():
                # height[i]: right temperature
                # tempWaitDays: tempWaitDaysCandidateIndex

                # Distance from right temperature to current tempWaitDaysCandidate
                # is the days until a warmer temperature for the current candidate
                res[tempWaitDaysCandidateIndex] = i - tempWaitDaysCandidateIndex  

            # monotonic decreasing has been re-enabled
            # add right temperature to monotonic stack
            # push right temperature index
            stack.append(i)  
        
        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return res

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Result List	O(n)	O(n)	Initialization of list for n temperature wait days O(n)	Stores wait time for n temperatures O(n)
Iteration	O(n)	O(1)	Iteration over list of temperatures n length O(n)	No additional memory allocation for iteration O(1)
Stack operations	O(n)	O(n)	Each index is pushed and popped at most once for n length O(n)	Monotonic stack stores at most n indices O(n)
Temperature comparisons	O(1)	O(1)	Comparison operation in constant O(1)	No additional memory allocation for comparison O(1)
Overall	O(n)	O(n)	Iteration over temperatures dominates, leading to O(n)	Stack and result list dominates, leading to O(n)

Solution 2: Reverse Iteration Monotonic Decreasing Stack of Warm Temps - Stack/Monotonic Property Maintenance

    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        
        # Note:
        # Solution 2 tends to use less actual in memory due to more 
        # aggressive pruning of colder temperatures during reverse traversal

        # iterating reverse: why monotonic decreasing?
        # index: 0  1  2  3  4  5  6
        # temp:[ 1, 4, 6, 8, 5, 3, 2]

        # a monotonic increasing (iterating backwards) would be [2, 3, 5, 8]
        # but we don't care about decreasing cold values, but increasing hot values
        # so we still want a monotonic decreasing (backwards) [8, 6, 4, 1]
        
        # difference from forward iteration is that we are tracking the hot values
        # rather than tracking the cold values 
        
        # space complexity: storing up to n indexes O(n)
        n = len(temperatures)
        stack = []

        # space complexity: storing wait days for n temperatures
        res = [0] * n

        # time complexity: iterate over list of n temperatures O(n)
        for i in range(n-1, -1, -1):

            # maintain decreasing temp of hot temps by:
            # prevent equal or hotter temp from being added
            # which will remove older hot temps
            # and replacing with newer hot temps
            while stack and temperatures[stack[-1]] <= temperatures[i]:
                stack.pop()

            # check: monotonic decreasing kept with stack (backwards)
            # which means top of stack has a hotter temperature, calculate distance
            if stack:
                # stack[-1]: previous hot temperature
                res[i] = stack[-1] - i

            # Invariant: monotonic decreasing, append to list 
            stack.append(i)        
        
        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return res

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Result list	O(n)	O(n)	Stores wait day for n temperatures O(n)	Stores wait day for n temperatures O(n)
Reverse Iteration	O(n)	O(1)	Iteration over list of n temperatures O(n)	No additional memory allocation for iteration O(n)
Stack operations	Amortized O(n)	O(n)	Each element is pushed and popped at most once in for n elements Amortized O(n)	Stack holds unresolved future warmer day indices for up to n temperatures O(n)
Temperature comparison	O(1)	O(1)	Comparison in constant O(1)	No additional memory allocation for comparison O(1)
Overall	O(n)	O(n)	Iteration over list of n temperatures dominates, leading to O(n)	Efficient pruning of colder temperatures often leads to smaller stack than forward pass but still for n elements O(n)

Solution 3: Dynamic Programming Jump Traversal using Future Warm Temperatures - Stack/Algorithm

    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        
        # Note:
        # This solution uses a jump-based approach via leveraging 
        # results from previously computed indices.
        # It avoids an explicit stack by simulating the search for 
        # the next warmer temperature using a two-pointer like mechanism,
        # jumping ahead using previously filled results.
        # This effectively builds a "path" toward the next warmer day

        # Key Insight:
        # Once we know the next warmer day for some index j, we can skip
        # forward using res[j] to find the next warmer day for earlier indices i.
        
        # space complexity: result list for storing wait times o(n)
        n = len(temperatures)
        dp = [0] * n

        # tracking index of hottest day seen so far right to left
        # set hottest day to last element
        hottest_day = n - 1

        # time complexity: reverse iterate through temperatures from second last to first O(n)
        for i in range(n - 2, -1, -1):

            # found new hottest day, 
            # then ignore wait days calculation
            # Check: if current temperature is >= hottest_day temp,
            # Implies: found new hottest day, 
            # and since we are iterating right to left, 
            # then no hotter day can be to the right of new hottest
            if temperatures[i] >= temperatures[hottest_day]:
                # new hottest day index
                hottest_day = i

            # find hottest day
            else:
                # check hotter day for next index
                j = i + 1

                # while hotter day not found
                while temperatures[j] <= temperatures[i]:
                    # jump to hottest day candidate's hottest day
                    j += dp[j]

                # found hotter day
                dp[i] = j - i 

        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return dp

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Result list	O(n)	O(n)	Storing next hottest day distance for n temperatures O(n)	Storing next hottest day distance for n temperatures O(n)
Hottest day tracker	O(1)	O(1)	Single variable used to track hottest future day O(1)	Constant memory allocation O(1)
Jump pointer search	Amortized O(n)	O(1)
Overall	O(n)	O(n)	Iteration over list of temperatures n length dominates, leading to O(n)

853. Car Fleet ::2:: - Medium

Topics: Array, Stack, Sorting, Monotonic Stack

Intro

There are n cars at given miles away from the starting mile 0, traveling to reach the mile target. You are given two integer array position and speed, both of length n, where position[i] is the starting mile of the ith car and speed[i] is the speed of the ith car in miles per hour. A car cannot pass another car, but it can catch up and then travel next to it at the speed of the slower car. A car fleet is a car or cars driving next to each other. The speed of the car fleet is the minimum speed of any car in the fleet. If a car catches up to a car fleet at the mile target, it will still be considered as part of the car fleet. Return the number of car fleets that will arrive at the destination.

Input	Output
target = 10, position = [3], speed = [3]	1
target = 100, position = [0,2,4], speed = [4,2,1]	1
target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]	3

Constraints:

1 ≤ n ≤ 10⁵

0 < target ≤ 10¹⁰

0 ≤ position[i] < target

All of values of position are unique

0 < speed[i] ≤ 10⁶

Abstract

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Brute Force: Stack

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug: Base Case Add if Stack Empty or New Fleet

    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        stack = []

        stack

        for (pos,spd) in sorted(zip(position, speed), reverse=True):
            timeToTarg = (target-pos)/spd

            # new fleet
            # INCORRECT:
            # fleet is never added to fleet stack,
            # here, we only need to check if a fleet exists
            # if grab, else initialize first fleet
            # Instead:
            # if not stack or timeToTarg > stack[-1]
            if stack and timeToTarg > stack[-1]:
                stack.append(timeToTarg)

        return len(stack)

Solution 1: Monotonic Increasing Stack of Slower/Higher Fleet Times - Stack/Monotonic Property Maintenance

    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        # Note: 
        # Each car is represented by its position and speed
        # We calculate the the time for each car to reach the target mile.
        # We sort the cars by highest distance first (higher value closer to target, smaller farther),
        # so that we can process the cars in order from target to start (closer to farther),
        # to check the generation of fleets

        # Note:
        # Monotonic stack: maintains a monotonic increasing stack of times to target
        
        # space complexity: stores times for up to n fleets O(n)
        stack = []

        # Sort cars by position in descending order
        # time complexity: timSort cars by starting position distance descending O(n log n)
        # generate fleets by going iterating over closest to target -> farthest to target        
        # time complexity: iterate over n cars O(n) 
        for pos, spd in sorted(zip(position, speed), reverse=True): 
            
            # current car time to target
            currTimeToTarget = (target - pos) / spd 
            
            # A new fleet means if a farther car has a higher time to target than closer car
            # then this car will never catch up to the fleet and instead will form a new fleet

            # A fleet means if a farther car has a lower time to target than a closer car
            # it will catch up to the current fleet

            # stack[-1]: will have the current lowest time to target value for some fleet
            # For each new car we check its time to target relative to the current fleet 

            # Thus:
            # If current car is faster (time to target <= stack top), it will catch up with fleet and merge
            # If current car is slower (time to target > stack top), it will never catch up and thus form a new fleet
            
            # Check: stack is empty, create first fleet
            # Check: is farther car slower than current fleet, create new fleet
            if not stack or currTimeToTarget > stack[-1]:

                # Create new fleet at top of stack
                stack.append(currTimeToTarget)

            # Otherwise, catches up to the fleet in front (we do nothing)
        
        # overall: time complexity O(n log n)
        # overall: space complexity O(n)
        return len(stack)

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Sorting	O(n log n)	O(n)	TimSort cars by descending position O(n log n)	Store cars of list of n length o(n)
Fleet generation	O(n)	O(n)	Iterate over list of cars n length O(n)	Stack tracks time to target for up to n fleets O(n)
Overall	O(n log n)	O(n)	TimSort cars by descending position dominates, leading to O(n log n)	Cars and stack dominate, leading to O(n)

Solution 2: Greedy Tracking One Slowest/Higher Fleet - Stack/Algorithm

    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        
        # Note:
        # Greedy strategy based on arrival times
        # We only need to track 1 fleet at a time,
        # since if current car cannot catch up with current fleet,
        # it cannot catch up with previously created fleets

        num_fleets, slowest_fleet_time = 0
        for pos, spe in sorted(zip(position, speed), reverse=True): 
            
            # current car time to target
            currCarTimeToTarget = (target - pos)/spe 

            # Check: current car has higher time to target than current fleet
            if currCarTimeToTarget > slowest_fleet_time: 

                # update tracking fleet and total num of fleets
                num_fleets += 1
                slowest_fleet_time = currCarTimeToTarget

        # overall: time complexity O(n log n)
        # overall space complexity O(n)
        return num_fleets

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Sorting	O(n log n)	O(n)	TimSort cars by descending position O(n log n)	Storing cars for list of n length O(n)
Fleet Counting	O(n)	O(1)	Iterate over cars for list of n length O(n)	No additional memory allocation for iteration
Overall	O(n log n)	O(n)	TimSort cars by descending position dominates, leading to O(n log n)	Storing cars for list of n length dominates, leading to O(n)

84. Largest Rectangle in Histogram ::2:: - Hard

Topics: Array, Stack, Monotonic Stack

Intro

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Input	Output
[2,4]	4
[2,1,5,6,2,3]	10

Constraints:

1 ≤ heights.length ≤ 10⁵

0 ≤ heights[i] ≤ 10⁴

Abstract

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Brute Force: Stack

    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        max_area = 0

        for i in range(n):
            min_height = heights[i]
            for j in range(i, n):
                min_height = min(min_height, heights[j])
                max_area = max(max_area, min_height * (j - i + 1))

        return max_area

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug: Did not append to stack correctly

    def largestRectangleArea(self, heights: List[int]) -> int:
        
        # monotonic increasing
        stack = []
        maxArea = 0

        # INCORRECT:
        # this creates a copy of the heights
        # does not append in place
        # Instead:
        # heights.append(0)
        heights + [0]

        for i in range(len(heights)):

            # monotonic is broken
            while stack and heights[stack[-1]] > heights[i]:
                
                # monotonic is broken
                # 
                heightIndex = stack.pop()
                tallHeight = heights[heightIndex]

                # entire stack was pop goes from 0->i
                if not stack:
                    width = i

                # left wall exists, bounded by left wall and tall
                else:
                    leftWallIndex = stack[-1]
                    width = i - leftWallIndex - 1

                currArea = tallHeight * width
                maxArea = max(maxArea, currArea)

            stack.append(i)

        return maxArea

Solution 1: Double Dragging Forward Iteration Monotonic Increasing of Higher Bar Height Index - Stack/Monotonic Property Maintenance

    def largestRectangleArea(self, heights: List[int]) -> int:

        # "we keep popping as long as the current small height candidate
        #  is still covered by the taller bars before it,
        #  which means that either:
        #  1. the stack gets completely popped, which means the small height candidate
        #     is the smallest height encountered, so it spans from 0 -> i, which is
        #     a width of i
        #  2. there is a left height on the stack, a tall wall which we can drag up until
        #     the small height candidate, since we know all popped walls were taller than
        #     this current left height, so we can do i - left index - 1
        
        # Note:
        # Monotonic stack: A stack that maintains monotonic increasing heights
        # When monotonic increasing rule breaks, curr height will serve as right boundary
        # If stack is non empty, that means we have a stack full of tall bars.
        # Each popped bar acts as as the height of a rectangle. 
        # The width of the rectangle is determined by the distance 
        # to the previous smaller bar, the left boundary 

        # Note: 
        # Sentinel: 
        # Given that are trigger for the area check is that we have found the tallest wall
        # when the monotonic increasing rule has broken
        # we need to add a height wall of 0 at the end of the heights array as a sentinel
        # so that it triggers and checks the last valid height

        # Space complexity: stores heights for up to n heights O(n)
        stack = []
        max_area = 0

        # Sentinel: 0-height bar to trigger monotonic increasing rule break
        heights.append(0)

        # time complexity: iterate over list of n length O(n)
        for i in range(len(heights)):

            # Check: if current bar breaks monotonic increasing order
            # First Implies: First time this triggers, tallest bar found so far is on stack[-1]
            # Invariant Implies: There is a tall wall at stack[-1], which is covered by 
            #  previously popped tall walls
            while stack and heights[stack[-1]] > height[i]:
                
                # grab tall bar index and height
                tallWallIndex = stack.pop()
                tallWall = heights[tallWallIndex]

                # if stack is empty
                # smallest height popped off all other heights
                # so we are guaranteed width of 0 through i, width length of i
                if not stack:
                    width = i

                # stack is not empty
                # current tallWall is bounded by the left wall in distance
                # -1 is to account for the left wall
                else:
                    leftWallIndex = stack[-1]
                    width = i - leftWallIndex - 1

                # check new max area
                max_area = max(max_area, tallWall * width)

            # monotonic increasing is maintained: 
            # curr height is no longer covered by the tall bars, add to stack 
            stack.append(i)

        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return max_area

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Stack operations	O(n)	O(n)	Each index is pushed and popped at most once O(n)	Stack can contain up to n indexes O(n)
Sentinel	O(1)	O(1)	Ensures all heights are processed O(1)	No additional memory allocation for sentinel O(1)
Area calculation	O(1)	O(1)	Height calculation in constant O(1)	No additional memory allocation for calculation O(1)
Overall	O(n)	O(n)	Iterate over list of n length dominates, leading to O(n)	Stack index storage dominates, leading to O(n)

Solution 2: Double Dragging Reverse Iteration Monotonic Increasing of Higher Bar Height Index - Stack/Monotonic Property Maintenance

    def largestRectangleArea(self, heights: List[int]) -> int:
        
        n = len(heights)
        max_area = 0

        # We process from right to left, so we reverse the indices
        stack = []

        # Sentinel: iteration through -1
        # time complexity: iterate over list of n length O(n)
        for i in range(n-1, -2, -1):

            # Sentinel: append a sentinel index of -1, height of 0
            curr_height = 0 if i == -1 else heights[i]

            # maintain monotonic increasing height
            while stack and heights[stack[-1]] > curr_height:

                # monotonic increasing broken, pop until true again
                index = stack.pop()
                height = heights[index]

                # if stack is empty
                # small height popped all taller walls
                # so current height extends from i to (n-1)
                if not stack:
                    width = (n - 1) - i
                
                # if stack is not empty
                # the width is bounded from i to the right wall
                # right wall is currently on the stack on stack[-1]
                # -1 is to account for the right wall
                else:
                    rightWall = stack[-1]
                    width = (rightWall - 1) - i

                # check new area
                max_area = max(max_area, height * width)

            # if non-sentinel index, append
            if i >= 0:
                stack.append(i)

        # overall: time complexity 
        # overall: space complexity
        return max_area

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Iteration	O(n)	O(1)	Iterate over list of n length O(n)	No additional memory allocation for iteration O(1)
Stack operations	O(n)	O(n)	Each index is push and popped at most once for n indexes O(n)	Stack can hold up to n indexes O(n)
Sentinel	Final iteration i = -1 triggers processing remaining stack, constant value O(1)	No additional memory allocation for sentinel O(1)
Area Calculation	O(1)	O(1)	Rectangle area computed in constant time per pop O(1)	No additional memory allocation for area calculation O(1)
Overall	O(n)	O(n)	Iteration over list dominates, leading to O(n)	Stack storage dominates, leading to O(n)

402. Remove K Digits ::1:: - Medium

Topics: String, Stack, Greedy, Monotonic Stack

Intro

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

Input	Output
num = "10", k = 2	"0"
num = "10200", k = 1	"200"
num = "1432219", k = 3	"1219"

Constraints:

1 ≤ k ≤ num.length ≤ 10⁵

num consists of only digits

num does not have any leading zeros except for 0 itself

Abstract

Remove k digits in a way so that resulting integer is as large as possible.

Solution 1: Forward Iteration Monotonic Increasing Digits Stack - Stack/Monotonic Property Maintenance

    def removeKdigits(self, num: str, k: int) -> str:

        # Same as histogram or graph problem
        # We are removing a taller height if a smaller height follows it

        # Note:
        # Monotonic stack: a stack that maintains increasing digits
        # Greedy: remove from top of stack if higher digit at top of stack 
        # is followed by a smaller one, as this lowers value
        # Inverse Greedy: don't remove smaller digit if higher digit follows, as this increases value 

        # space complexity: stack holds increasing digits up to n digits O(n)
        stack = []

        # time complexity: iterate over list of n length O(n)
        for digit in num:

            # Check: non empty stack
            # Check: we still need to remove more digits (k > 0)
            # Check: if monotonic increasing broken
            # Implies: found smaller digits in front of larger, replace larger value at top of stack
            while stack and k > 0 and stack[-1] > digit:
                
                # remove higher digit at top of stack
                stack.pop()
                k -= 1

            # monotonic increasing valid
            stack.append(digit)

        # monotonic stack is valid

        # Check: if we still need to remove digits k
        # ignore larger digits on right side, 
        # splice and grab digits from the left side

        # "12345" [:3] -> "123"
        # "12345" [:-3] -> "12"
        # -3 removes 3 digits
        if k > 0:
            stack = stack[:-k]

        # Join the stack into a number and remove leading zeros "0200" -> "200" 
        result = ''.join(stack).lstrip('0')

        # Return "0" if the result is empty

        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return result or "0"

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Iteration	O(n)	O(n)	Each digit is pushed and popped at most once O(n)	Stack stores up to n digits O(n)
Postprocessing	O(k)	O(1)	Remove k remaining digits from end	No additional memory allocation for splicing O(1)
Conversion	O(n)	O(n)	Build result and strip leading zeros for n length O(n)	String of up to n length O(n)
Overall	O(n)	O(n)	Iteration over n length dominates, leading to O(n)	Stack storing n digits dominates, leading to O(n)