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)

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

        # sc: O(n)
        stack = []

        # 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 closed paren
                # tc: O(1)
                if not stack:
                    return False

                # tc: O(1)
                topElem = stack.pop()

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

            # Matched open and closed:
            # we have found a closed and popped the open,
            # append the open for the next pair
            # tc: O(1)
            if c in '([{':
                stack.append(c)
                               
        # stack is empty, no more paren to match

        # overall: tc O(n)
        # overall: sc O(n)
        return not stack

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

        # Monotonic Stack:
        # We scan nums2 left to right, maintaining a stack that is always
        # strictly decreasing from bottom to top. Whenever the current
        # number is greater than the number on top of the stack, that
        # means we've just found the "next greater element" for whatever
        # is on top -- so we pop it off and record the current number as
        # its answer. We repeat this for every number the current one beats.

        # Why this works:
        # Anything left on the stack has not yet found a next greater
        # element as we scan forward. Pushing the current number onto the
        # stack keeps it around as a candidate "next greater element" for
        # whatever gets pushed after it, until something bigger comes along
        # to pop it off.

        # 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.

        # sc: O(n), maps each number in nums2 to its next greater element
        nextGreater = {}

        # sc: O(n), holds numbers still waiting for their next greater element
        stack = []

        # tc: O(n), each number pushed and popped at most once
        for num in nums2:

            # Resolve:
            # current number is greater than the top of the stack,
            # so it's the next greater element for everything it beats
            while stack and num > stack[-1]:

                # Pop:
                # remove the smaller number, current num is its answer
                smaller = stack.pop()
                nextGreater[smaller] = num

            # Push:
            # current number becomes a candidate "next greater element"
            # for whatever gets pushed after it
            stack.append(num)

        # Leftovers:
        # anything still on the stack never found a next greater element
        while stack:
            nextGreater[stack.pop()] = -1

        # Build result for nums1 via O(1) lookups
        # tc: O(m), m = len(nums1)
        return [nextGreater[num] for num in nums1]

        # overall: tc O(n + m), n = len(nums2), m = len(nums1)
        # overall: sc O(n), for the stack and hash map

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

        # Result starts as the original prices.
        # If no discount exists, the price remains unchanged.
        answer = prices[:]

        # Monotonic Increasing Stack
        # Stores indices of items still waiting
        # for their first smaller-or-equal price.
        stack = []

        for i in range(len(prices)):

            # Current price becomes the discount
            # for every previous price that is
            # greater than or equal to it.
            while stack and prices[i] <= prices[stack[-1]]:

                previous = stack.pop()
                answer[previous] -= prices[i]

            # Current item now waits for its own discount.
            stack.append(i)

        return answer

    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        
        # Monotonic Stack: 
        # A stack that maintains monotonic decreasing temperatures 
        # When monotonic decreasing rule breaks, that means we have found a temperature 
        # that is hotter than 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

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

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

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

            # Check: if stack is non empty, need to verify monotonic decreasing
            # Check: if monotonic decreasing broken, current temperature will serve as hot day 
            # Implies: we need to pop off the stack until monotonic decreasing is true again
            # Implies: for those temperatures popped, we can calculate a hot day wait time
            while stack and temperatures[stack[-1]] < temperatures[i]:
                
                # i: hot day index
                # stack[-1]: cold day index
                coldDayIndex = stack.pop()
                hotDayIndex = i

                # hot day is the closest hotter day for the cold day,
                # get distance between indexes to get how many days must be waited
                coldDayWaitTime = hotDayIndex - coldDayIndex

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


            # Check: appending temperature will keep monotonic decreasing rule
            # Implies: this is the coldest day on the stack
            stack.append(i)  
        
        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return res

    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        
        # Aggressive Pruning:
        # Reverse tends to use less actual in memory.
        # In the reverse, we are only keep track of hot temperatures in monotonic decreasing order
        # ensuring we have a list of the most recent hot temperatures to ensure minimum wait time for cold
        # days. So due to the aggressive pruning of colder temperatures during reverse traversal
        # this tends to use less memory

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

        # Monotonic increasing stacks when iterating backwards, represent decreasing temperatures
        #                                        
        #               *                       *
        #            *  *                       *  *      
        #         *  *  *                       *  *  *
        #         *  *  *                       *  *  *  
        #      *  *  *  *                       *  *  *  *  
        #     ---------------     which      ---------------    none of these have hotter days,
        #      6  5  4  3   ... represents      3  4  5  6      so we do not care about monotonic increasing stacks
        

        # Monotonic decreasing stacks when iterating backwards, represent increasing temperatures
        #                                        
        #      *                                        *
        #      *  *                                  *  *  
        #      *  *                                  *  *
        #      *  *  *                            *  *  *
        #      *  *  *  *                      *  *  *  *  
        #     ---------------     which      ---------------   all of these have hotter days,
        #      3  2  1  0   ... represents     0  1  2  3      so we care about monotonic decreasing stacks


        # Forward vs Backwards Stack Tracking:
        # So the difference
        #       Forward iteration: we are tracking decreasing temperatures, in order to calculate distance when a hotter day appears
        #       Backwards iteration: we are tracking increasing temperatures, in order to keep track of the most recent hotter temperatures

        # sc: storing up to n indexes O(n)
        n = len(temperatures)
        stack = []

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

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

            # Check: monotonic decreasing
            # Implies: Keep list of decreasing temp of hot temps
            # Check: if monotonic decreasing broken, we have found a more recent hotter temperature
            # Then: pop() older hot temperature with new hotter temperature to ensure minimum wait time for cold days
            while stack and temperatures[stack[-1]] <= temperatures[i]:
                stack.pop()

            # Check: if stack is not empty
            # Implies: stack has a hotter temperature, can calculate wait days for current cold day
            if stack:

                # Hot and cold days
                # Hot and cold days
                futureHotDayIndex = stack[-1]
                currentColdDayIndex = i

                # Wait time calculation
                # Wait time calculation
                waitDays = futureHotDayIndex - currentColdDayIndex
                res[i] = waitDays
                res[i] = waitDays

            # Invariant: current cold day could serve as potential more recent hot day for earlier days for earlier days, append to stack
            # Invariant: this cold day will get replaced if a more recent hotter day appears
            stack.append(i)        
        
        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return res

    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        
        # Dynamic Programming:
        # Uses a jump approach building a next hottest day hopping path as we compute hotter days.
        # Avoids a stack of temperatures by iterating backwards and keeping 
        # track of the nearest hottest day, which can be used by other days to find 
        # their own hotter day.

        # Jump Traversal:
        # If we are trying to find the hottest day for index i, 
        # we know that our first candidate is the following day. 
        # If the following day is not the nearest hottest day, 
        # then we know that the first candidate needs a day hotter than this first candidate.
        # That implies, that the day at index i and the first candidate share the nearest hottest day.
        # By that logic, we can simply 'jump' to the candidate's own hotter day and use it as 
        # the next candidate for index i.
        
        # Essentially, days in the future help days in the past by building shortcuts to hotter days.
        
        # sc: result list for storing wait times o(n)
        n = len(temperatures)
        dp = [0] * n

        # Setting first hottest day as the last element
        hottest_day = n - 1

        # Reverse iteration to build future temperature list
        # tc: iterate over n O(n)
        for i in range(n - 2, -1, -1):

            # Check: current temperature is warmer than current hottest day
            # Implies: no future hotter day exists, no need for wait days calculation
            # Then: update the hottest day
            if temperatures[i] >= temperatures[hottest_day]:
                hottest_day = i

            # Check: current temperature is colder than current hottest day
            # Implies: current temperature has at least 1 hotter day in the future
            # Then: calculate wait days for current temperature
            else:

                # Current temperatures' first hotter day candidate is the following day
                tempCandidateIndex = i + 1

                # Check: continue while the candidate is colder than the current temperature
                while temperatures[tempCandidateIndex] <= temperatures[i]:
                    
                    # Implies: candidate is not hotter
                    # Then: to avoid checking days that are colder than the current candidate, we can
                    # skip to the candidates own hotter day, so we never decrease in temperature moving forward
                    tempCandidateIndex += dp[tempCandidateIndex]

                # Check: found a temperature hotter than current temperature
                # Then: calculate distance between hotter day and current temperature
                dp[i] = tempCandidateIndex - i 

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

class MinStack:

    # MinStack:
    # We need to track 2 things
    #   - The item at the top of the stack
    #   - The min item currently in the stack

    # 4 Functions:
    # They may need to update the above 2 details:
    # Push(), Pop(), Top(), GetMin()
    # all in O(1)

    # Top Of Stack:
    #   - Stack with a push and pop will track the top push

    # Min Item:
    #   - Push(): Will track min item up to this level
    #   - Pop(): Will update min if min item if removed

    # Stack:
    # Tuple Representing (Top_Of_Stack, Min_At_Level):
    #
    #          (7, 1)       5
    #          (4, 1)       4
    #          (1, 1)       3
    #          (7, 5)       2
    #          (5, 5)       1
    #           Stack     Level

    def __init__(self):

        # Stack of Tuples Representing (Top_Of_Stack, Min_At_Level):
        # sc: O(n)
        self.stack = []
        self.size = 0
 
    # Helper:
    # If logical pointer is behind actual length of stack,
    # we can overwrite whatever is at the pointer index
    def _overwriteCheck(self):
        return self.size < len(self.stack)

    # Push():
    #   - Put new item at top of stack
    #   - Compare new item to current min item in stack
    def push(self, val: int):

        # Min at this level:
        # check if non empty stack, if so compare against previous min
        # else update to new value
        currMin = min(val, self.stack[self.size - 1][1] if self.size > 0 else val)
        
        # Overwrite whatever is at pointer index
        if self._overwriteCheck():
            self.stack[self.size] = (val, currMin)

        # Append to end of stack
        else:
            self.stack.append((val, currMin))

        # increase logical size
        self.size += 1

    # Pop():
    #   - Remove item at top of stack
    #   - Update min item if min item was removed
    def pop(self):
        self.size -= 1

    # Top():
    #   - Get item at top of stack
    #   - Do not remove item
    def top(self):
        return self.stack[self.size - 1][0]

    # GetMin():
    #   - Get current min element in the stack
    #   - Do not remove item
    def getMin(self):
        return self.stack[self.size - 1][1]

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

class MinStack:

    # MinStack:
    # We need to track 2 things
    #   - The item at the top of the stack
    #   - The min item currently in the stack

    # 4 Functions:
    # They may need to update the above 2 details:
    # Push(), Pop(), Top(), GetMin()
    # all in O(1)

    # Top Of Stack:
    #   - Stack with a push and pop will track the top push

    # Min Item:
    #   - Push(): Will track min item up to this level
    #   - Pop(): Will update min if min item if removed

    # Stack:
    # Tuple Representing (Top Of Stack, Min At Level):
    #
    #          (7, 1)       5
    #          (4, 1)       4
    #          (1, 1)       3
    #          (7, 5)       2
    #          (5, 5)       1
    #           Stack     Level

    def __init__(self):
        
        # Stack of Tuples Representing (Top_Of_Stack, Min_At_Level):
        # sc: O(n)
        self.stack = []

    # Push():
    #   - Put new item at top of stack
    #   - Compare new item to current min item in stack
    def push(self, val: int):
        currMin = min(val, self.stack[-1][1] if self.stack else val)
        self.stack.append((val, currMin))

    # Pop():
    #   - Remove item at top of stack
    #   - Update min item if min item was removed
    def pop(self):
        self.stack.pop()

    # Top():
    #   - Get item at top of stack
    #   - Do not remove item
    def top(self):
        return self.stack[-1][0]

    # GetMin():
    #   - Get current min element in the stack
    #   - Do not remove item
    def getMin(self):
        return self.stack[-1][1]

    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: iterate over n 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[-1]

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

    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        
        # Sorting By Distance To Target: 
        # We sort the cars by order of closest to target to farthest from target 
        # (higher value is closer, smaller value is further).
        
        # Sorting By Distance Allows For 2 implications:
        #  1. Farther cars with lower arrival times (faster) than the car directly in front of it
        #     will catch up with the car in front of it and form a fleet.
        #    The entire fleet will then be determined by the slower car that was just caught up with (think of traffic)
        #
        #  2. Farther cars with higher arrival times (slower) than the car directly in front of it
        #     will never catch up with the car in front of it, 
        #    thus, the slower car will be left behind and form a new fleet.
        #     This new fleet will be determined by the slower car

        # As we iterate from closest to farthest: 
        #  - Start with a new car
        #  - Compare arrival time with the most recently created fleet
        #  - Check if new car catches up with fleet (joins) or is does not catch up and is left behind (forms new fleet)
        
        # Implication Summary:
        #  1. if that car has a lower (faster) arrival time than the car in front of it, it will join the car ahead (join fleet)
        #  2. if the car has a higher (slower) arrival time than the car in front of it, it will stay behind the car ahead (form new fleet)

        # Example: Cars ordered from farthest to closest to target, with numbers representing arrival times:
        #                  
        #                                     (estimated)                                                             fleet number
        #   Time to                           no fleets exist, car 0 forms the first fleet                                 1
        #   target   1  4  3  7  1  2         car 1 has higher time than car 0, does not catch up, forms second fleet      2
        #           ------------------        car 2 has lower time than car 1, catches up, joins second fleet              2
        #            0  1  2  3  4  5         car 3 has higher time than car 2, does not catch up, forms third fleet       3 
        #       Closest             Farther   car 4 has lower time than car 3, catches up, joins third fleet               3 
        #       car        -->      car       car 5 has lower time than car 3, catches up, joins third fleet               3

        # Monotonic Stack: 
        # Maintains a monotonic increasing stack of times to target (lower times (faster) to high times (slower)).
        # Every time a higher (slower) time to target is found, it means a car is slower than the current fleet, gets left behind, and creates a new fleet (is pushed to stack)
        # Every time a lower (faster) time to target is found, it means a car catches up to the current fleet, and nothing is done as the car joins the current fleet, which is still limited by the current fleet's time

        # Monotonic Summary:
        # Implication 1: And every time monotonic increasing is broken, the current fleet is joined, no new fleets are formed
        # Implication 2: So every time monotonic increasing is kept, a new fleet is formed

        # sc: stores times for up to n fleets O(n)
        # sc: stores times for up to n fleets O(n)
        stack = []

        # Grabbing Info:
        # Pair each car's position with its speed
        cars = list(zip(position, speed))

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

        # Iterate by closer to farthest cars
        # tc: iterate over n cars O(n) 
        for (pos, spd) in cars:

            # Calculate: time to target for new car
            currTimeToTarget = (target - pos) / spd 

            # top of stack[-1]: represent the current fleet's time to target, which new cars will be compared to
            
            # Check: if stack is empty, new car automatically becomes first fleet -> push()
            # Check: if stack is not empty, fleet exists -> compare time to targets
            # Implication 2. if new car is slower (new time to target > stack top), it will never catch up and thus form a new fleet
            if not stack or currTimeToTarget > stack[-1]:

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

            # Implication 1. if new car is faster (new time to target <= stack top), it will catch up with fleet and merge
            else:

                # Do not change current fleet
                continue
        
        # Total number of fleets represented by time to targets/fleets on stack
        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:
        
        # Pointer Value:
        # The previous stack is doing 2 things:
        #   1. keeping track of the current fleet (top of the stack)
        #   2. keeping track of the number of total fleets (number of time to targets/fleets on the stack)
        # We can do both of these without using a stack and save space

        # Greedy:
        # Strategy based on our arrival times implication
        # When a new car is checked, we just compare it with the current slowest fleet.
        # So all we need to do is keep track of the current slowest fleets and the number of fleets.

        # Traffic Single Lane Road:
        # If you think of a one lane road, a single car (the slowest) will block all traffic before it.
        # So we only need to keep track of a single slowest fleet at a time, as this will be the limiting factor
        # for the entire single lane, until a slower car is found, at which point that new slower car becomes 
        # the new limiting factor for the entire road

        num_fleets = 0
        slowest_fleet_time = 0

        # Grabbing Info:
        # Pair each car's position with its speed
        cars = list(zip(position, speed))

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

        # Iterate by closer to farthest cars
        # tc: iterate over n cars O(n) 
        for (pos, spd) in cars:
            
            # Calculate: time to target for new car
            currCarTimeToTarget = (target - pos)/spd 

            # Implication 2. if new car is slower (higher) (new time to target > stack top), it will never catch up and thus form a new fleet
            if currCarTimeToTarget > slowest_fleet_time: 

                # Create new fleet and update its slowest time
                num_fleets += 1
                slowest_fleet_time = currCarTimeToTarget

            # Implication 1. if new car is faster (lower) (new time to target <= stack top), it will catch up with fleet and merge
            else:

                # Do not change current fleet
                continue

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

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

        # README.md:

        # Monotonic Stack: 
        # A stack that maintains monotonic increasing heights
        # When monotonic increasing rule breaks, that implies the new height is smaller than at least 1 of the older heights.
        # When monotonic increasing rule is true, that implies the new height is taller than all older heights.
        # If stack is non empty, that means we have a stack full of tall bars that can serve to generating an area
        # by covering new shorter walls.
        # The width of the rectangle is determined by the distance between the index of the tall bar on top of the stack 
        # that is covering and the index of the new shorter bar.

        # Diagram 1:
        # All the areas generated by the bars that are taller than the new candidate
        #               *                                  A                    *                    *       
        #            *  *                               *  A                 A  A                 *  *       
        #         *  *  *          *                 *  *  A  *           *  A  A  *           A  A  A  A 
        #      *  *  *  *     +    *       ==>    *  *  *  A  *   ==>  *  *  A  A  *   ==>  *  A  A  A  A  ?
        #     ------------   new  ---             ---------------      ---------------      --------------- 
        #    older --> newer                      0  1  2  3  4        0  1  2  3  4        0  1  2  3  4      
        #                                   area from 3-3            area from 2-3          area from 1-4 (NOT GENERATED NOW)
        #                                                                                   (RIGHT BOUNDARY IS MISSING)

        # Diagram 1: Notes
        # Notice how, for some bar x on the stack, every bar in front of x is taller and thus 'covers' it
        # All bars, except the new bar that breaks the monotonic rule
        # We will use this 'stack covering' assumption to build areas, using the x bar as the left boundary
        # and the new bar as the right boundary

        # Diagram 1: Not Generated Notes
        # Also notice how the last area is not generated.
        # This is because areas are not generated until a smaller bar appears
        # which serves as a right boundary.
        # So that area is generated in Diagram 2 below

        # Diagram 1: Pop() 1, Generating the walls while popping
        #               *                                  *                    A                                      
        #            *  *                               *  *                 *  A                           *          
        #         *  *  *          *                 *  *  *  *           *  *  A  *                     *  *     * 
        #      *  *  *  *     +    *       ==>    *  *  *  *  *   ==>  *  *  *  A  *   ==> pop() ==>  *  *  *     * 
        #     ------------   new  ---  pop off   ---------------      ---------------                --------------- 
        #    older --> newer           taller walls               area generated by bounding 
        #                                                              via shorter bar

        # Diagram 1: Pop() 2                                                                                                     
        #            *                       A  A                                             
        #         *  *     *              *  A  A  *                      *        *   
        #      *  *  *     *    ==>    *  *  A  A  *   ==> pop() ==>   *  *        * 
        #     ---------------          ---------------                ---------------  
        #    older --> newer   area generated by bounding  + using monotonic bar                
        #                           via shorter bar          assumption 

        # Diagram 1: Final Result
        #
        #         *  *   
        #      *  *  * 
        #     ---------------  
        #    final result                          

        # Diagram 1: Just the pop()'s                                                                                                                                                                   
        #               *                                     *                                                
        #            *  *                                  *  *                 *                             
        #         *  *  *          *                    *  *  *   *          *  *   *          *   *          *  *
        #      *  *  *  *    +     *        ==>      *  *  *  *   *   =>  *  *  *   *   =>  *  *   *  ==>  *  *  *
        #     ------------   new  ---     pop off   ------------ ---     --------- ---     ------ ---     ---------
        #    taller bars   shorter bar    taller walls                                                      final result

        # Diagram 2: Pop() 1, Generating the walls while popping
        #
        #         *  *                           A  A 
        #      *  *  *         +    *    ==>  *  A  A  *  
        #     ----------      new  ___       ------------
        #    older --> newer                   (WE ARE MISSING THE CORRECT WIDTH)

        # 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: iterate over n 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: iterate over n 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

    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: iterate over n 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