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

    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]]

    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]

    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]

    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)

    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

    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)

Sol 1: Manual Condition Stack Check
1. stack = []
2. mapping = {closeChar: openChar}
3. for each c in s:
   a. if c is closing:
        if stack empty: return False
        topElem = stack.pop()
        if mapping[c] != topElem: return False
   b. if c is opening:
        stack.append(c)
4. return stack is empty

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

        # sc: O(n)
        stack = []

        # Open close paren matching map
        # sc: O(1)
        mapping = {
            ')' : '(',
            ']' : '[',
            '}' : '{'
        }

        # tc: O(n)
        for c in s:

            # Found Closed: 
            # need to match with open
            # tc: O(1)
            if c in ')]}':

                # Empty Check:
                # there is no open paren to match the current closed paren, invalid stack
                # tc: O(1)
                if not stack:
                    return False

                # Check:
                # the closed type should match the paren currently at the top of stack
                # tc: O(1)
                topElem = stack.pop()
                if mapping[c] != topElem:
                    return False

            # Matched open/closed:
            # we have found an open and closed paren,
            # append the open for the next pair for future matching
            # tc: O(1)
            if c in '([{':
                stack.append(c)
                               
        # Finished iterating over string,
        # validate that stack is empty and all paren have been matched
        isStackEmpty = not stack

        # overall: tc O(n)
        # overall: sc O(n)
        return isStackEmpty

Sol 1: Stack Postfix Expression Evaluation Algorithm
1. stack = []
2. for each token in tokens:
   a. if token is number:
        stack.append(int(token))
   b. else (operator):
        b = stack.pop()
        a = stack.pop()
        stack.append(a OP b)
3. return stack.pop()

    def evalRPN(self, tokens: List[str]) -> int:
        
        # Reverse Polish Notation:
        # We only push numbers to the stack,
        # and when we hit an operator we pop b the a
        # since the numbers are on the stack in reverse

        # input:    ["4","13","5","/","+"]
        # expected: 4 + (13 / 5) = 6
        # "4"    -> [4]         push() 4 to stack
        # "13"   -> [4, 13]     push() 13 to stack
        # "5"    -> [4, 13, 5]  push() 5 to stack
        # "/"    -> [4]         hit operator, pop() b = 5, pop() a = 13, complete operation int(13 / 5) = 2
        # "2"    -> [4, 2]      push() 2 to stack
        # "+"    -> []          hit operator, pop() b = 2, pop() a = 4, finish operator (4 + 2) = 6
        # "6"    -> [6]         push() 6 to stack

        # [6] stack holds answer

        # sc: stack holds up to n/2 intermediate results O(n)
        stack = []

        # tc: O(n)
        for token in tokens:

            # Found Integer:
            # Cast to int and push() to stack
            if token not in "+-*/":
                stack.append(int(token))
            
            # Found Operation:
            # Pop() 2 numbers from stack, b then a, and compute
            else:

                # tc: pop operation constant O(1)
                b = stack.pop()
                a = stack.pop()

                # Complete Operation: 
                # Push() result to stack
                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:        Remainder                                         x
                        # -7 // 3        # -3      floor division:  Rounds down "towards infinity"                    x
                        # int(-7 / 3)    # -2      int(division):   Rounds up "towards 0", as required by RPN      this one

                        stack.append(int(a / b))

        # Top of stack holds result
        res = stack[0]

        # overall: tc O(n)
        # overall: sc O(n)
        return res

Sol 1: Collision Resolution With Alive Flag

1. self.stack = []

2. for curr in asteroids:
    a. alive = True
    b. while alive and curr < 0 and stack and 0 < stack[-1]:
             if stack[-1] < -curr:
                 stack.pop()
                 continue
             elif -curr < stack[-1]:
                 alive = False
             else:
                 stack.pop()
                 alive = False
             if alive:
    c. stack.append(curr)

3. survivors = stack

3. return survivors

    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        
        # Collision Rule:
        # - Two stones only hit if a right mover behind a left mover (+ -)
        # - Same direction asteroids never meet (they move at same speed) (+ +) or (- -)
        # - A left mover behind a right mover will never hit (- +).

        # Tracking Survivors:
        # - Everything else gets pushed to stack to track surviving asteroids
        # - Only collide if a right mover hits a left mover (+ -)
        # - so we only collide if we find a new left mover 
        #   while the top of the stack holds a right mover

        # Stack:
        # - stores both left and right movers
        # - uses tracking survivors + collision rules to determine what to pop/push

        # Stack Progression Example: [-3, 10, -5]
        # - (-3) survives (no collisions)
        # - 10 survives (no collisions)
        # - (-5) destroyed (collides with 10)
        # - stack = [-3, 10]

        # sc: O(n)
        stack = []

        # tc: O(n)
        for curr in asteroids:

            # Alive:
            # - is curr alive
            alive = True

            # Right Movers:
            # - pushed immediately to the stack
            # - can never collide with anything already on the stack

            # Left Movers:
            # - if stack is empty, push to stack
            # - if top of stack is also a left mover, push to stack (can't hit reach each other)
            # - check if top stack is a right mover (collision will occur)
            # - if beats top of stack, continue to compare to top of stack

            # Collision If:
            # - curr is alive left mover (alive & negative: curr < 0)
            # - top of stack is right mover, (positive: 0 < stack[-1])
            # - then collide, either left or right survives or none
            # tc: O(n)
            while alive and curr < 0 and stack and 0 < stack[-1]:

                # Left mover is bigger than right:
                # - pop the destroyed right 
                # - keep compare curr against new top
                if stack[-1] < -curr:
                    stack.pop()
                    continue

                # Right mover is bigger than left:
                # - alive flag to false for destroyed left
                # - iterate to next curr
                elif -curr < stack[-1]:
                    alive = False


                # Neither survives:
                # - pop the destroyed right
                # - alive flag to false for destroyed left
                else:
                    stack.pop()
                    alive = False

            # Check for survivor: 
            # - no collision, always alive: (- +), (+ +), or (- -)
            # - left mover destroyed all right movers on top of stack
            if alive:
                stack.append(curr)

        # Stack holds any left or right movers that survived
        survivors = stack

        # overall: tc O(n)
        # overall: sc O(n)
        return survivors

Sol 1: Decreasing Stack With Hash Map Lookup
1. (nextGreater = {})
2. (stack = [])
3. for curr in nums2:
    a. while stack and stack[-1] < curr:
         foundNextForIndex = stack.pop()
         nextGreater[foundNextForIndex] = curr
    b. stack.append(curr)
4. (res = [])
5. for query in nums1:
    a. if query in nextGreater:
         res.append(nextGreater[query])
       else:
         res.append(-1)
6. return res

    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:

        # Monotonic Stack:
        # - scan nums2 left to right
        # - maintain a stack strictly decreasing from bottom to top. 
        
        # [0] ... [i]
        # high     low
        
        # - if curr number is greater than top of stack,
        #   we have found the 'next greater element' for that top of stack
        # - continue comparing curr to top of stack
        # - anything left on top of stack does not have a next greater element

        # Hash Map:
        # - 
        # Since nums1 is a subset of nums2, we only need to solve
        # "next greater element" once per number in nums2, then look up
        # each answer for nums1 in O(1) instead of resolving it twice.

        # Hashmap:
        # - num2 value => next greatest element
        # - constraints guarantee all values in nums2 are unique, so it's
        #   safe to key this hashmap by value directly
        # - if duplicates were allowed, a value-keyed hashmap would break --
        #   a later occurrence of the same value could silently overwrite
        #   an earlier index's already-correct answer (this is exactly
        #   why 503 keys its stack/result by index instead of value)
        # - and we don't want to do by index here,
        #   is because the queries from nums1 are queries by value, not by index
        # sc: O(n)
        nextGreater = {}

        # sc: O(n)
        stack = []

        # Generate the next greatest element hashmap
        # tc: O(n)
        for curr in nums2:

            # Found Next Greatest:
            # - curr is greater than top of stack
            # - pop top of stack and record curr as its next greatest 
            while stack and stack[-1] < curr:

                # Next Greatest:
                # record curr as the next greatest for top of stack
                foundNextForIndex = stack.pop()
                nextGreater[foundNextForIndex] = curr

            # Pending:
            # - push curr to stack, waiting for its next greatest element
            stack.append(curr)

        # Next greatest num index for query stream
        # sc: O(n)
        res = []

        # Use next greatest element hashmap to respond to queries in nums1
        # tc: O(m), m = len(nums1)
        for query in nums1:

            # Query Stream:
            # - check we found a next greatest for num
            # - if not, return -1
            if query in nextGreater:
                res.append(nextGreater[query])
            else:
                res.append(-1)

        # overall: tc O(n + m)
        # overall: sc O(n)
        return res

Sol 1: Decreasing Stack of Indices Simulated Circular Scan
1. (n = len(nums))
2. (res = [-1] * n)
3. (stack = [])
4. for i in range(2 * n):
    a. curr = nums[i % n]
         while stack and nums[stack[-1]] < curr:
             foundNextForIndex = stack.pop()
             res[foundNextForIndex] = curr
    b. if i < n:
         stack.append(i)
5. return res

    def nextGreaterElements(self, nums: List[int]) -> List[int]:

        # Monotonic Stack (Circular):
        # - same idea as Next Greater Element I, but array is circular, 
        #   so element at end of list could have next greater near beginning of list
        # - simulate wrapping around by scanning the array twice
        #   (indices 0..2n-1), using i % n to map back into the real
        #   array, without actually building a doubled array in memory

        # [0] ... [i]
        # high     low

        # - if curr number is greater than the number at the index on top of stack, 
        #   we have found the 'next greater element' for that index
        # - continue comparing curr to the new index on top of the stack
        # - anything left on the stack after second passes does not have a next greater

        # Indices Instead Of Values:
        # - unlike Next Greater Element I, nums are not guaranteed unique values
        # - we can't use a value -> answer hashmap due to potential duplicate overwrite
        # - instead we store indexes and write next greatest into res array by index

        n = len(nums)

        # Next greatest num index
        # sc: O(n)
        res = [-1] * n

        # sc: O(n)
        stack = []

        # Simulated circular scan:
        # - pass around array twice to ensure last element
        #   can find its next greatest element if it exists via wrap around
        # tc: O(2n) ~ O(n)
        for i in range(2 * n):

            # Wrap:
            # - Turn doubled range back in bounds of real array
            curr = nums[i % n]

            # Found Next Greatest:
            # - curr is greater than the number at the index on top of stack
            # - pop that index and record curr as its next greatest
            while stack and nums[stack[-1]] < curr:

                # Next Greatest:
                # record curr as the next greatest for top of stack
                foundNextForIndex = stack.pop()
                res[foundNextForIndex] = curr

            # Booking Keeping:
            # - only push one copy of elements
            # - do not push anything during second iteration
            if i < n:
                stack.append(i)

        # overall: tc O(n)
        # overall: sc O(n)
        return res

Sol 1: Monotonic Decreasing Stack of Cold Temps
1. (n = len(temperatures))
2. (res = [0] * n)
3. (stack = [])
4. for i in range(n):
    a. while stack and temperatures[stack[-1]] < temperatures[i]:
         hotDayIndex = i
         coldDayIndex = stack.pop()
         coldDayWaitTime = hotDayIndex - coldDayIndex
         res[coldDayIndex] = coldDayWaitTime
    b. stack.append(i)
5. return res


Sol 3: Reverse Iteration With Jump Traversal Using Dynamic Programming
1. (n = len(temperatures))
2. (dp = [0] * n)
3. (maxHottestDay = n-1)
4. for i in range(n-2, -1, -1):
    a. if temperatures[maxHottestDay] <= temperatures[i]:
         maxHottestDay = i
    b. else:
         tempCandidateIndex = i+1
         while temperatures[tempCandidateIndex] <= temperatures[i]:
             tempCandidateIndex = tempCandidateIndex + dp[tempCandidateIndex]
         dp[i] = tempCandidateIndex - i
5. return dp

    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        
        # Monotonic Stack: 
        # - maintains indexes for monotonic decreasing temperatures 
        # - When monotonic decreasing rule breaks, that means we have found a hotter temperature 
        #   for at least 1 of the previous temperatures
        
        # Stack:
        #      *                                   *                             *                        *                       *
        #      *  *                                *  *                          *  *                     *  *                    *  *    
        #      *  *             *                  *  *             *            *  *          *          *  *       *            *  *  * 
        #      *  *  *          *                  *  *  *          *            *  *  *       *          *  *       *            *  *  * 
        #      *  *  *          *                  *  *  *          *            *  *  *       *          *  *       *            *  *  * 
        #      *  *  *  *   +   *                  *  *  *  *   +   *            *  *  *   +   *          *  *   +   *            *  *  * 
        #     ------------     ---       ==>      ------------     ---    ==>   ---------     ---   ==>  ------     ---   ==>   --------- 
        #      0  1  2  3       4      calc wait   0  1  2  3       4            0  1  2       4          0  1       4   join()   0  1  4
        #     older          hot day     days          
        #                                          Day 3 waits 1 day           Day 2 waits 2 days     Day 4 is colder than Day 1

        n = len(temperatures)

        # Hotter day wait time for temperatures 
        # sc: O(n)
        res = [0] * n

        # Stores indexes for temperatures
        # sc: O(n)
        stack = []

        # tc: O(n)
        for i in range(n):

            # Hotter Temperature:
            # - if stack is non empty, verify monotonic decreasing
            # - if monotonic decreasing broken, curr temperature is hotter for at least 1 of the previous temperatures
            # - pop indexes for temperatures off the stack until monotonic decreasing is true again
            # - for each of the indexes for temperatures popped, we can calculate a hot day wait time
            while stack and temperatures[stack[-1]] < temperatures[i]:
                
                # i: Hotter day index
                hotDayIndex = i

                # stack[-1]: Cold day index
                coldDayIndex = stack.pop()

                # Wait time:
                # - Hot day is the closest hotter day for the cold day,
                # - Day 5 to Day 3 has a way time of 2 days, so wait time = (5 - 3) = 2
                coldDayWaitTime = hotDayIndex - coldDayIndex

                # Set wait time for current cold day
                res[coldDayIndex] = coldDayWaitTime

            # Monotonic Decrease:
            # - appending index for temperature will keep monotonic decreasing true
            # - this is the new coldest day on the stack
            # - this is now waiting for a new hotter day
            stack.append(i)  
        
        # overall: tc O(n)
        # overall: sc O(n)
        return res

    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        
        # Aggressive Pruning:
        # - Reverse tends to use less actual in memory
        # - In reverse, we are store hot temperatures in monotonic decreasing order
        # - This ensures we have a list of the most recent hot temperatures 
        #   to ensure minimum wait time for cold days 
        # - So colder temperatures are immediately resolved for their wait time, 
        #   so colder days are never stored waiting for hotter days 
        #   which can use less memory depending on the data

        # Temperatures:
        # temp:[ 1, 2, 4, 5, 4, 3, 1]
        # index: 0  1  2  3  4  5  6

        # Iterating Backwards + Monotonic Decrease (what we want):
        # - we represent increasing temperatures
        # - by storing hotter temperatures with the more recent days being on top of the stack
        
        #   list of temperatures            our stack
        
        #              *                     *              
        #           *  *                     *  *           
        #           *  *                     *  *           
        #        *  *  *                     *  *  *        
        #     *  *  *  *      represented    *  *  *  *    
        #   ---------------      by =>      --------------- 
        #     0  1  2  3      our stack      3  2  1  0
        

        n = len(temperatures)

        # Hotter day wait time for temperatures 
        # sc: O(n)
        res = [0] * n

        # Stores indexes for temperatures
        # sc: O(n)
        stack = []

        # tc: O(n)
        for i in range(n-1, -1, -1):

            # Hotter Temperature:
            # - if stack is non empty, verify monotonic decreasing
            # - if monotonic decreasing broken, curr temperature can serve as a hotter more recent temperature
            # - pop older hot temperature and replace with newer hotter temperature
            # - ensures minimum wait time for cold days
            while stack and temperatures[stack[-1]] <= temperatures[i]:
                stack.pop()

            # Monotonic Decreasing:
            # - curr is colder than top of stack
            # - ergo, everything on stack is hotter than curr
            # - top of stack guaranteed to be the closest hottest day to curr
            # - calculate wait days for current cold day
            if stack:

                # Closest hotter day to curr
                futureHotDayIndex = stack[-1]

                # Cold day curr
                currentColdDayIndex = i

                # Wait time calculation
                waitDays = futureHotDayIndex - currentColdDayIndex

                # Set wait time for current cold day
                res[i] = waitDays


            # Monotonic Decrease:
            # - appending index for temperature will keep monotonic decreasing true
            # - this is least hottest day on the stack
            # - this is acting as the most recent hottest day
            stack.append(i)        
        
        # overall: tc O(n)
        # overall: sc O(n)
        return res

    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        
        # Dynamic Programming:
        # - Use previously found hottest day to serve as jump skips for curr temperature

        # Jump Traversal:
        # - for curr i, try i+1 as the next hottest day
        # - if i+1 is the next hottest day, this is easy 1 day wait
        # - if its not, then the next hottest day for i+1, can also apply for i
        # - skip to next hottest day for i+1, to serve as a candidate for i

        n = len(temperatures)

        # Hotter day wait time for temperatures 
        # sc: o(n)
        dp = [0] * n

        # Hottest day found so far:
        maxHottestDay = n-1

        # Reverse iteration to build next hottest day dp list
        # tc: O(n)
        for i in range(n-2, -1, -1):

            # New Hottest Day
            # - curr is hotter than max hottest day
            # - no future possible days exist that are hotter
            if temperatures[maxHottestDay] <= temperatures[i]:
                maxHottestDay = i

            # Next Hottest Possible: 
            # - curr has at least 1 hotter day in the future
            # - calculate wait days for curr
            else:

                # Init candidate:
                # - curr's first candidate is the next day
                tempCandidateIndex = i+1

                # Update Candidate: 
                # - if candidate is not a hotter day
                # - jump to the candidates own next hottest
                while temperatures[tempCandidateIndex] <= temperatures[i]:
                    
                    # Jump to candidate's own next hottest day:
                    # candidate's next hottest day = candidate index + wait days time
                    tempCandidateIndex = tempCandidateIndex + dp[tempCandidateIndex]

                # Found next hottest day:
                # - Set wait time for curr
                dp[i] = tempCandidateIndex - i

        # overall: tc O(n)
        # overall: sc O(n)
        return dp

  oh! pseudocode hasn't been written yet, try another card! :)

    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        
        # Fleet Rule:
        # - a car that catches up to a slower car ahead of it is forced to go at the slower
        #   cars speed, which creates a fleet
        # - a car that never catches up to the car ahead of it forms its own fleet

        # Sorting By Distance To Target: 
        # - sort cars by closest to target first and farthest last

        # [0]      ...  [n-1]
        # (closest)    (farthest)
        #  higher val   lower val

        # Sort By Distance Implication:
        # - if a farther car has a lower time to target than the car ahead of it,
        #   it will catch up to that car and join its fleet
        # - that car ahead of it sets the time to target for the entire fleet

        # Iterate from closest cars to farthest cars: 
        #  - Check each car with the car/fleet ahead of it
        #  - If curr car has a lower time to arrival (faster) than the car/fleet ahead of it,
        #    it will join that fleetCompare arrival time with the most recently created fleet
        #  - If car has a higher time to arrival (slower) than the car/fleet ahead of it,
        #    it will be left behind and starts a new fleet

        # Monotonic Increasing Stack:
        # - top of stack holds the fleet with the slowest time to arrival
        # - we only need to check if a farther car catches up with the slowest fleet
        #   or if it becomes its own new slowest fleet


        # Tracks number of fleets from from low -> high time to arrival
        # sc: O(n)
        stack = []

        # Prepare to sort by distance:
        # O(n)
        cars = list(zip(position, speed))

        # Sort by descending (higher/closer to farther/lower):
        # tc: timSort O(n log n)
        cars.sort(reverse=True)

        # Iterate from closer to farther
        # tc: O(n) 
        for (pos, spd) in cars:

            # Time To Target:
            currTimeToTarget = (target - pos) / spd 

            # Monotonic Increasing Broken:
            # - curr car has lower time to target than top of stack (slowest fleet)
            # - curr car catches up to fleet, and now must follow that fleets time to target
            if stack and currTimeToTarget < stack[-1]:

                # Top of stack stays the same,
                # current slowest fleet stays the same
                continue

            # Monotonic Increasing Kept:
            # - stack is empty
            # - curr time to target is greater/slower than top of stack
            # - new curr becomes the new slowest fleet
            else:

                # Curr becomes new slowest fleet
                stack.append(currTimeToTarget)

        # Stack is storing all fleet time to targets,
        # total count of time to targets representing count of fleets
        numOfFleets = len(stack)

        # overall: tc O(n log n)
        # overall: sc O(n)
        return numOfFleets

    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        
        # Greedy Monotonic Stack Compression:
        # - previous stack is doing 2 things:
        #    tracks slowest fleet at top of stack
        #    tracks number of fleets by number of time to targets on stack
        # - we can do both of these with variables

        # Slowest Time To Target Variable:
        # - give a new car, compare to the slowest time to target
        # - if new car has a higher time to target, it is slower, and it becomes the new slowest
        # - if new car has a lower time to target, it is faster, and catches up to the slowest
        #   with the slowest time to target staying the same

        # Fleet Rule:
        # - a car that catches up to a slower car ahead of it is forced to go at the slower
        #   cars speed, which creates a fleet
        # - a car that never catches up to the car ahead of it forms its own fleet

        # Sorting By Distance To Target: 
        # - sort cars by closest to target first and farthest last

        # [0]      ...  [n-1]
        # (closest)    (farthest)
        #  higher val   lower val

        # Sort By Distance Implication:
        # - if a farther car has a lower time to target than the car ahead of it,
        #   it will catch up to that car and join its fleet
        # - that car ahead of it sets the time to target for the entire fleet

        numFleets = 0

        slowestFleetTimeToTarget = 0

        # Prepare to sort by distance:
        # O(n)
        cars = list(zip(position, speed))

        # Sort by descending (higher/closer to farther/lower):
        # tc: timSort O(n log n)
        cars.sort(reverse=True)

        # Iterate from closer to farther
        # tc: O(n) 
        for (pos, spd) in cars:
            
            # Time To Target:
            currCarTimeToTarget = (target - pos) / spd 

            # Curr Car Slower:
            # - curr car is slower than the current slowest time to target,
            #   so it can't catch up and starts a new fleet
            if slowestFleetTimeToTarget < currCarTimeToTarget: 

                # Update slowest time to target
                slowestFleetTimeToTarget = currCarTimeToTarget

                # Create new fleet
                numFleets += 1

            # Curr Car Faster:
            # - curr car is faster than the current slowest time to target,
            #   so it catches up and joins that fleet
            else:

                # Slowest fleet stays the same,
                # no new fleet created
                continue

        # overall: tc O(n log n)
        # overall: sc O(1)
        return numFleets

Sol 1: Increasing Stack of Pending Indices
1. stack = []
    a. for i in range(len(prices)):
         while stack and prices[i] <= prices[stack[-1]]:
             origPriceIndex = stack.pop()
             discount = prices[i]
             prices[origPriceIndex] -= discount
2. stack.append(i)
3. return prices

    def finalPrices(self, prices: List[int]) -> List[int]:

        # Discount Rule:
        # - each prices has a change to get a discount 1 time
        # - the first later price that is less than, subtract that from the price 

        # Monotonic Stack:
        # - stores prices that are waiting for a discount
        # - once a price gets its 1 time discount, remove from stack and update prices

        # [0] ... [i]
        # low     high

        # Stack Progression Example: [7, 4, 6, 2, 3]
        # - 7 pending => [7]
        # - 4 is 7's discount (7 - 4 = 3), 4 pending => [4]
        # - 6 pending => [4, 6]
        # - 2 resolves 6's discount (6-2=4), then resolves 4's discount (4-2=2), 2 pending (stack: [2])
        # - 3 pending => [2, 3]
        # - loop ends, 2 and 3 never found a discount, keep original prices

        # - discountedPrices = [3, 2, 4, 2, 3]

        # Pending Indices
        # sc: O(n)
        stack = []

        # tc: O(n)
        for i in range(len(prices)):

            # Discount Found:
            # - current price[i] is less than top of stack
            # - then we found discount for top of stack
            # - discount top of stack, pop price we just discounted, 
            #   and compare with new top if discount also applies
            while stack and prices[i] <= prices[stack[-1]]:

                # Grab original price index
                origPriceIndex = stack.pop()

                # Get discount
                discount = prices[i]

                # Reduce price by discount
                prices[origPriceIndex] -= discount

            # Push curr price to pending for a discount
            stack.append(i)

        # overall: tc O(n)
        # overall: sc O(n)
        return prices

Sol 1: Decreasing Stack of (Price, Span) Pairs
1. def __init__(self):
    a. (self.stack = [])

2. def next(self, price: int) -> int:
    a. span = 1
    b. while self.stack and self.stack[-1][0] <= price:
         (prevPrice, prevSpan) = self.stack.pop()
         span += prevSpan
    c. self.stack.append((price, span))
    d. return span

class StockSpanner:

    # Price Stream:
    # - Given a stream of prices
    # - For each index i, find find out how many consecutive days immediately preceding today 
    #   had prices less than or equal to today's price
    # - Consecutive days cannot be broken up by a more expensive day

    # Monotonic Stack (Price, Span):
    # - monotonic decreasing prices:
    
    # [0] ... [i]
    # high     low
    
    # - Tuples carry the span they 'own'
    #   representing their number of consecutive days (including itself) 

    # When today's price is greater than or equal to the price on top of the stack, 
    # that top entry can never again be the answer for any future day 
    # (today always dominates it looking backward), 
    # so we absorb its span into today's before pushing.

    # Why this works:
    # Absorbing spans instead of popping and forgetting means we
    # never have to re-walk days we've already collapsed. 
    # Each day is pushed once and popped at most once over the life of the object, 
    # so the amortized cost per call stays O(1).

    def __init__(self):

        # Tracking: (price, span)
        # sc: O(n)
        self.stack = []

    def next(self, price: int) -> int:

        # Spanning:
        # today always spans at least itself
        span = 1

        # Calculate Span:
        # - stack is non empty
        # - todays price is greater than the top of the stack
        # - top of the stack should be included into todays span 
        # - we can remove it from the top of the stack, since in the future
        #   it will be included within todays span
        while self.stack and self.stack[-1][0] <= price:

            # Popped span is now included within todays span,
            # no need to keep it on the stack anymore
            (prevPrice, prevSpan) = self.stack.pop()

            # Include span we popped into curr's span
            span += prevSpan

        # Monotonic Decreasing:
        # - Curr becomes new max needed to surpass to have a valid span
        self.stack.append((price, span))

        # Each (price, span) pushed/popped at most once across all calls to next()
        # tc: O(1) amortized
        return span

    # overall: tc O(n)
    # overall: sc O(n)

  oh! pseudocode hasn't been written yet, try another card! :)

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

        # Monotonic Stack: 
        # - maintains monotonic increasing heights
        # - when monotonic increasing stays true, 
        #   that implies new height is taller than all older heights
        # - when monotonic increasing is false, 
        #   that implies new height is smaller than at least 1 of the older heights
        # - if stack is non empty, that means we have multiple tall bars 
        #   that will serve to generate an area by covering shorter walls
        # - the width of the rectangle is distance between the index 
        #   the tall bar on top of the stack and index of the new shorter wall

        # Small Bar Popping Tall Bar Area Generation:
        # - a small bar to that breaks the monotonic increasing rule triggers area generation
        # - we know that the tallest bar on the stack, 'covers' all other bars on the stack
        # - we can use the tallest bar as the right boundary while using each smaller bars height,
        #   which gives us a valid width (tallest bar index - some smaller bar index)
        #   as well as a valid height (smaller bar height) which is guaranteed to be covered by the tallest bar,
        #   allowing use to use it as the height for the rectangle

        #                    *                                        A                         *        |                 *       
        #            *       *                               *        A                 A       A        |         *       *       
        #         *  *       *          *                 *  *        A  *           *  A       A  *     |      A  A       A  A 
        #      *  *  *       *     +    *       ==>    *  *  *        A  *   ==>  *  *  A       A  *     |   *  A  A       A  A 
        #     --------- ... ---        ---             --------- ... ------      --------- ... ------    |  --------- ... ------
        #    older     --> newer       new             0  1  2        6  7        0  1  2       6  7     |    0  1  2       6  7 
        #                                                                                                |
        #                                                 area from 6-6            area from 2-6         |  We do not generate area from 1-4
        #                                                 using height             using height          |  as 7 cannot act as its own right boundary
        #                                                 from 6 bar               from the 2 bar        |


        # Round 1: Generating areas while popping

        # - notice how we can't generate an area with a right boundary
        # - areas are not generated until a smaller bar appears
        # - tallest bar will serve as a right boundary for all areas generated per round

        # Pop() 1
        #                     *                                *                           A                                      
        #            *        *                        *       *                 *         A                           *          
        #         *  *        *        *            *  *       *  *           *  *         A  *                     *  *       * 
        #      *  *  *        *        *   ==>   *  *  *       *  *   ==>  *  *  *         A  *   ==> pop() ==>  *  *  *       * 
        #     --------- ... ----  +   ---       --------- ... ------       --------- ... -------      tall      --------- ... ---
        #      0  1  2        6  new   7         0  1  2       6  7          0  1  2       6  7       bar        0  1  2       7


        # Pop() 2
        #                                                                                                                 
        #            *                          *                      A                                           
        #         *  *          *            *  *       *           *  A        *                     *        * 
        #      *  *  *          *   ==>   *  *  *       *   ==>  *  *  A        *   ==> pop() ==>  *  *        * 
        #     --------- ... +  ---       --------- ... ---       --------- ... ---      tall      ------- ... ---
        #      0  1  2     new  7         0  1  2       7        0  1  2        7       bar        0  1        7


        # Final Result                                                                                                          
        #                                     
        #         *          *            *       * 
        #      *  *          *   ==>   *  *       *  
        #     ------ ... +  ---       ------ ... --- 
        #      0  1     new  7         0  1       7  


        # Round 2: Generating the walls while popping

        # Pop() 1
        #
        #         *       *                                *       *            *        * 
        #      *  *       *    +    *    ==> pop() ==>  *  *       *  *  ==> pop() ==>  *  *        *  A  A  *  
        #     ------ ... ---  new  ___       tall      ------ ... ------  ... ---
        #     0  1        7         8                   0  1       7  8   0  1        7

        # Diagram 2: Correcting the distance
        # If you recall, the distance between these two walls is actually:
        #
        #       *        *                      *        *               A  A  A  A  
        #    *  *        *    +    *    ==>  *  *        *  *   ==>   *  A  A  A  A  * 
        #   ---------------  new  ---       -----------------         -----------------

        # Diagram 2: A Stack Of Indexes
        # So to solve this problem, we keep the indexes on the stack not the heights,
        # in order to save the distance between the walls for when the time comes
        # to calculate the width of areas.

        # Diagram 2: Indexes
        #     A  A  A  A  
        #  *  A  A  A  A  * 
        # -----------------
        #  0  1  2  3  4  5                                

        # Diagram 2: Width Calculation
        # For any bar x
        #   - Left boundary = the nearest bar to the left that is shorter
        #   - Right boundary = the nearest bar to the right that is shorter
        #   - Width = (right boundary index - left boundary index) - 1
        # So for here: = (5 - 0) - 1 =  5 - 1 = 4 wide

        # Summary Popping Rule:
        # We keep popping as long as the stack has taller bars than the new smaller bar.
        # A taller bar implies that previous bars on the stack are covered  the new smaller bar is covered and can generate an area.
        # Once an area can be generated, we just need to calculate the width or the distance between the shorter bar and taller bar

        # Popping Rule Implies either:
        #
        #  1. The stack gets completely popped:
        #     Implies the new height candidate is the smallest height encountered so far 
        #     and was covered by all other previous tall bars.
        #     This allows the area being generated to span from 
        #     0 -> new_candidate = 0 -> i = i - 0: so width = i
        #     and the height to be the height of the new height candidate, so height = new height candidate
        #
        #  2. The stack does not get completely popped:
        #     Implies the new height candidate is taller than at least 1 older bar
        #     and is not covered by all other previous tall bars.
        #     This creates a left bound for the area being generated to span from
        #     left bound -> new candidate, left bound -> i = i - left_bound: so width = i - left_bound
        #     The height 
        #     After the area is generated, the new height candidate becomes the new top of the stack, 
        #     and is compared against new walls, which may or may not be taller or shorter.
        
        # Sentinel: 
        # With the rule that area is not calculated until a smaller bar appears, 
        # we need to add a 0 to flush the remaining bars on the stack, 
        # so that every bar is eventually processed regardless of height

        sentinel = 0
        heights.append(sentinel)

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

        # tc: O(n)
        for i in range(len(heights)):

            # Monotonic increasing is broken: 
            # Check: if new bar breaks monotonic increasing order
            # Implies: The new candidate is shorter than at least 1 bar on the stack
            # Implies: We have found a right boundary
            # Rule: The taller bar can generate an area, pop() height for taller bar,
            # then check top of stack for the left boundary
            while stack and heights[stack[-1]] > heights[i]:
                
                # Grab taller bar index and height
                tallWallIndex = stack.pop()
                tallWallHeight = heights[tallWallIndex]

                # Check: if stack is empty after pop()
                # Implies: the new wall is shorter than all previous heights,
                # Implies: the left boundary goes up until an imaginary index -1 before the start
                if not stack:
                    # Actual rectangle is from 0 to i-1
                    # So the surrounding boundaries are at -1 and i:
                    # width = (right boundary) - (left boundary) - 1
                    #       = i - (imaginary index -1 before the start) - 1
                    #       = i - (-1) - 1
                    width = i - (-1) - 1

                # Check: Stack is not empty after pop()
                # Implies: top of stack can serve as left boundary
                else:
                    # Grab left boundary
                    leftWallIndex = stack[-1]

                    # Actual rectangle is from (leftWallIndex + 1) to (i-1)
                    # So the surrounding boundaries are at (leftWallIndex) and i
                    # width = (right boundary) - (left boundary) - 1
                    #       = i - (left wall on top of stack) - 1
                    #       = i - stack[-1] - 1
                    width = i - leftWallIndex - 1

                # Check: new max area
                max_area = max(max_area, tallWallHeight * width)

            # Monotonic increasing is maintained: 
            # Curr height is taller than all walls on the stack, there is no area to generate, append to stack and grab next new wall
            stack.append(i)

        # overall: tc O(n)
        # overall: sc O(n)
        return max_area

    def largestRectangleArea(self, heights: List[int]) -> int:
        
        # Monotonic Stack: 
        # A stack that maintains monotonic increasing heights

        # Stack popping off taller bars:                                                                                                                                                                    
        #               *                                     *                                                
        #            *  *                                  *  *                 *                             
        #         *  *  *          *                    *  *  *   *          *  *   *          *   *          *  *
        #      *  *  *  *    +     *        ==>      *  *  *  *   *   =>  *  *  *   *   =>  *  *   *  ==>  *  *  *
        #     ------------   new  ---     pop off   ------------ ---     --------- ---     ------ ---     ---------
        #    taller bars   shorter bar    taller walls                                                final result

        # Reverse Iteration Notice:
        # The diagram is the same for left to right iteration and right to left iteration
        # even though we are grabbing the bars on the right vs the left.
        # That is because the stack itself cannot tell the difference and just does the same algorithm.
        # Thus, all that changes is the width calculation with the indexes

        # Index Math:
        # Follow the same approach as forward iteration of finding the imaginary boundaries

        n = len(heights)
        max_area = 0

        stack = []

        # tc: 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]

            # Monotonic increasing is broken: 
            # Check: if new bar breaks monotonic increasing order
            # Implies: The new candidate is shorter than at least 1 bar on the stack
            # Implies: We have found a right boundary
            # Rule: The taller bar can generate an area, pop() height for taller bar,
            # then check top of stack for the left boundary
            while stack and heights[stack[-1]] > curr_height:

                # Grab taller bar index and height
                index = stack.pop()
                height = heights[index]

                # Check: if stack is empty after pop()
                # Implies: the new wall is shorter than all previous heights,
                # Implies: the right boundary goes up until an imaginary index n after the end
                if not stack:
                    # Actual rectangle is from (i+1) to (n-1)
                    # So the surrounding boundaries are at i and n:
                    # width = (right boundary) - (left boundary) - 1
                    #       = (imaginary index) - i - 1
                    #       = n - i - 1
                    width = n - i - 1

                # Check: Stack is not empty after pop()
                # Implies: top of stack can serve as right boundary
                else:
                    # Grab right boundary
                    rightWallIndex = stack[-1]

                    # Actual rectangle is from (i+1) to (rightWallIndex - 1)
                    # So the surrounding boundaries are at i and rightWallIndex:
                    # width = (right boundary) - (left boundary) - 1
                    #       = (right wall on top of stack) - i - 1
                    #       = stack[-1] - i - 1
                    width = rightWallIndex - i - 1

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

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

        # overall: tc O(n)
        # overall: sc O(n)
        return max_area

  oh! pseudocode hasn't been written yet, try another card! :)

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

        # Monotonic Stack:
        # A Stack that maintains increasing digits
        # To create the smallest number possible, we want our stack to keep smaller numbers
        # on the left side and larger numbers on the right:
        
        # Smaller number (left to right):
        # stack = [ 1 2 3 4 5 ]
        
        # Instead of larger number (right to left):
        # stack = [ 5 4 3 2 1 ]

        # A monotonic increasing stack allows us to create the smallest number possible
        # A monotonic decreasing stack allows us to create the largest number possible

        # So with a monotonic increasing stack, by ordering left to right,
        # we can slice at the end and grab as many numbers as we need or remove
        # more numbers (if we still have k left)
        
        # Slicing Grabbing:
        # "12345" [:3] -> "123"
        # 3 grabs the leftmost digits, creates the smallest number possible
        
        # Slicing Removal:
        # "12345" [:-2] -> "123"
        # -2 removes rightmost 2 digits, creates the smallest number possible

        # Greedy Summary:
        # The greedy removal is ensuring monotonic stack, 
        # as we want the smaller numbers to be to the left as much as possible, 
        # and we want to keep removing from the stack as long as we can (have k left)
        
        # sc: stack holds increasing digits up to n digits O(n)
        stack = []

        # tc: O(n)
        for digit in num:
            
            # Check: if stack is non empty, we have a candidate for removal
            # Check: if (k > 0) we still have digits to remove
            # Implies: if monotonic increasing broken, there is a larger digit to remove
            # Then: remove larger digit on stack to allow lower digit to be more to the left
            while stack and k > 0 and stack[-1] > digit:
                
                # Top of stack is larger than new digit, remove
                stack.pop()
                # Decrease remaining digits to remove
                k -= 1

            # Monotonic increasing valid:
            # New digit is as far to the left as possible
            stack.append(digit)

        # Building stack complete:
        # Digits are now ordered left to right with smallest being on the left
        # Check: if (k > 0) we still have digits to remove
        # Then: remove larger digits from the right side, to produce final smallest answer
        if k > 0:
            stack = stack[:-k]

        # Join all digits in the stack into a single string
        smallerNumber = ''.join(stack)

        # Clean answer:
        # Remove leading zeros "0000200" -> "200"
        result = smallerNumber.lstrip('0')

        # 0 Check:
        # if smallerNumber was all zeros, we will get an empty string after removing zeros
        # "0000" -> ""  
        # so check if empty and return "0"
        if not result:
            result = "0"

        # overall: tc O(n)
        # overall: sc O(n)
        return result