LeetCode: Stacks

    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 isValid(self, s: str) -> bool:
        
        # note: in python, an empty string "" is falsy evaluating to false
        # not "" -> true

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

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

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

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

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

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

                closingMatch = closing[c]

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

                # Matching opening bracket
                counts[closingMatch] -= 1

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

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

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

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

        # space complexity: 
        stack = []

        # time complexity:
        for c in s:

            # add opening parenthesis
            if c in '([{':
                stack.append(c)

            # validate closing parenthesis
            elif c in ')]}':
                if not stack or (c == ')' and stack[-1] != '(') or \
                                (c == '}' and stack[-1] != '{') or \
                                (c == ']' and stack[-1] != '['):
                    return False
                stack.pop()

        # overall: time complexity
        # overall: space complexity
        return not stack

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

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

        # time complexity: iterate over list of n length O(n)
        for c in s:
            
            # validate closing parenthesis
            if c in mapping:  
                
                # pop top element if stack is non-empty
                topElem = stack.pop() if stack else '#'

                if mapping[c] != topElem:
                    return False

            # append opening bracket
            else:
                stack.append(c)

        # overall: time complexity
        # overall: space complexity
        return not stack

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

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

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

        # increases logical size
        self.size += 1

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

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

        # decreases logical size
        self.size -= 1

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

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

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

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

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

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

        # increases logical size
        self.size += 1

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

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

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

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

    # overall: time complexity
    # overall: time complexity 

    def __init__(self):

        # using a minTracker stack, we track the min value at each
        # level of the main stack. Ensures when we pop a top value
        # we can instantly know the min value at that point

        # space complexity:
        self.mainStack = []
        self.minTracker = []
        self.mainSize = 0

    def push(self, val: int):

        # logical size vs physical size
        if self.mainSize < len(self.mainStack):
            self.mainStack[self.mainSize] = val
        else:
            self.mainStack.append(val)

        # logical size vs physical size
        if self.mainSize < len(self.minTracker)
            
            # compares new value with previous level of minTracker
            self.minTracker[self.mainSize] = min(val, self.minTracker[self.mainSize - 1] if self.mainSize > 0 else val)
        else:
            self.minTracker.append(min(val, self.minTracker[self.mainSize - 1] if self.mainSize > 0 else val))
        
        # increases logical size
        self.mainSize += 1

    def pop(self):
        # time complexity: 
        if self.mainSize == 0:
            raise IndexError("Pop from empty stack")
        
        self.mainSize -= 1

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

    def getMin(self):
        # time complexity:
        if self.mainSize == 0:
            raise IndexError("Stack is empty")

        return self.minTracker[self.mainSize - 1]

    # overall: time complexity
    # overall: time complexity 

    def __init__(self):

        # using of having a separate minTracker stack, we track the min value
        # at each level of the main stack using tuples (val, min).
        # Ensures when we pop a top value we can instantly know 
        # the min value at that level of the stack 

        # space complexity:
        self.stack = []
        self.size = 0

    def push(self, val: int):

        # compares val with previous level tuple minValue
        # sets new (val, minValue) to lower value
        currMin = min(val, self.stack[self.size - 1][1] if self.size > 0 else val)
        
        # logical size vs physical size
        if self.size < len(self.stack):
            self.stack[self.size] = (val, currMin)
        else:
            self.stack.append((val, currMin))

        # increases logical size
        self.size += 1

    def pop(self):
        # time complexity:
        if self.size == 0:
            raise IndexError("Pop from empty stack")
        self.size -= 1

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

    def getMin(self):
        # time complexity:
        if self.size == 0:
            raise IndexError("Stack is empty")

        return self.stack[self.size - 1][1]

    # overall: time complexity
    # overall: time complexity 

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

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

        return stack.pop()

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

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

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

        return stack.pop()

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

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

                match token:
                    case "+":
                        stack.append(a + b)
                    case "-":
                        stack.append(a - b)
                    case "*":
                        stack.append(a * b)
                    case "/":
                        stack.append(int(a / b))  # Explicit truncation towards zero

        return stack[-1]

    from operator import add, sub, mul, floordiv

    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        operations = {"+": add, "-": sub, "*": mul, "/": lambda a, b: int(a / b)}

        for token in tokens:
            if token not in operations:
                stack.append(int(token))
            else:
                b = stack.pop()
                a = stack.pop()
                stack.append(operations[token](a, b))

        return stack[-1]

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

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

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

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

            # validate all parentheses have match
            return balance == 0

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

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

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

        # while stack is non-empty
        while stack:

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

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

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

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

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

        # stack initial state
        stack = [("", 0, 0)] 

        # store valid parentheses
        result = []

        # 
        while stack:

            # grab the current state of the stack
            currentStr, openCount, closeCount = stack.pop()

            # base case: if we have used all open and close parentheses
            if openCount == n and closeCount == n:

                # add valid combination  
                result.append(currentStr)
                continue

            # push new state with '(' added
            if openCount < n:
                stack.append((currentStr + "(", openCount + 1, closeCount))

            # push new state with '(' added
            if closeCount < openCount:
                stack.append((currentStr + ")", openCount, closeCount + 1))

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

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

        res = []

        # Backtracking        
        def helper(current: List[str], num_open: int, num_closed: int):
            
            # Base case: If the length of the current combination is 2 * n, it's complete
            if len(current) == n * 2:
                # convert list to string and add to res
                res.append("".join(current))
                return

            # Recursive case 1: Add '(' if the number of '(' used is less than n
            if num_open < n: 
                current.append('(')
                helper(current, num_open + 1, num_closed)

                # Backtrack by removing the last added '('
                current.pop()  
            
            # Recursive case 2: Add ')' if the number of ')' used is less than the number of '('
            if num_closed < num_open:
                current.append(')')
                helper(current, num_open, num_closed + 1)

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

        # Start Backtracking process with an empty list and counts at 0
        helper([], 0, 0)

        # overall: time complexity
        # overall: space complexity
        return res

    def generateParenthesis(self, n: int) -> List[str]:
        
        res = []
        
        # Backtracking
        def backtrack(current, openCount, closeCount):

            # Base case: if we have used all open and close parentheses
            if openCount == n and closeCount == n:
                # add valid combination to res
                res.append(current)
                return
            
            # Recursive case 1: Add '(' if the number of '(' used is less than n
            if openCount < n: 

                # Backtrack by adding '(' to curr string, and incrementing openCount by 1
                # recursive call explores all combinations starting from this new state
                backtrack(current + "(", openCount + 1, closeCount)
            
            # recursive case: Add ')' if the number of ')' used is less than the number of '('
            if closeCount < openCount:

                # Backtrack by adding ')' to the curr string, and incrementing closeCount by 1
                # recursive call explores all combinations starting from this new state
                backtrack(current + ")", openCount, closeCount + 1)
        
        # starts recursion with an empty string and zero counts
        # backtracking process builds strings by choosing '(' or ')' at each step
        # and checking a possible valid paths through the recursion tree
        backtrack("", 0, 0)

        # overall: time complexity
        # overall: space complexity
        return res

    def generateParenthesis(self, n: int) -> List[str]:
        
        # Initialize a list to store DP results
        dp = [[] for _ in range(n + 1)]
        
        # Base case: valid combination for n = 0
        dp[0] = [""]  
        
        # dp for 1 to n
        # time complexity: iterate over list of n length O(n) 
        for i in range(1, n + 1): 

            # Partition parentheses into two parts: 
            # dp[j]: iterates from 0 -> i - 1
            # dp[i - 1 - j]: iterates from i - 1 -> 0
            # grabbing dp 0 + dp (i - 1) + parenthesis in (f"({left}){right}")
            # allows us to generate a valid combination for dp i
            for j in range(i):  

                # iterate over combinations from 0 parentheses pair, to i parentheses pairs
                for left in dp[j]:

                    # iterate over combinations from (i - 1) parentheses pairs dp[0]
                    for right in dp[i - 1 - j]:

                        # Add new permutation to list
                        # Since we are starting from a valid base case, if our formula builds a valid parentheses combination 
                        # any combination of parentheses will guarantee a new valid permutation 
                        # ({left}){right} or {left}({right}) are both valid formulas
                        dp[i].append(f"({left}){right}")

        # overall: time complexity
        # overall: space complexity 
        return dp[n]

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

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

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

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

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

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

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

            # INCORRECT: current day i is never pushed 

        return res

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

        # time complexity:
        for i in range(n):

            # compares curr temp with top of stack
            while stack and temperatures[i] > temperatures[stack[-1]]:
                idx = stack.pop()

                # Days until a warmer temperature
                res[idx] = i - idx  

            # Push current index
            stack.append(i)  
        
        return res

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

        for i in range(len(temperatures)):
            while st and temperatures[i] > temperatures[st[-1]]:
                idx = st.pop()
                res[idx] = i - idx
            st.append(i)
        
        return res

    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        res = [0] * n
        hottest_day = n - 1  # Track the hottest day from the end of the list

        for i in range(n - 2, -1, -1):  # Start from the second last element
            if temperatures[i] >= temperatures[hottest_day]:
                hottest_day = i  # Update the hottest day
            else:
                j = i + 1
                while temperatures[j] <= temperatures[i]:
                    j += res[j]  # Jump to the next warmer day
                res[i] = j - i  # Calculate days to next warmer temperature

        return res

    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        # Sort cars by position in descending order
        cars = sorted(zip(position, speed), reverse=True)
        
        # Stack to store the time each fleet takes to reach the target
        stack = []  

        # time complexity
        for pos, spd in cars:
            time_to_target = (target - pos) / spd  # Time for current car to reach target
            
            # Push the current car's time only if it doesn't merge with the fleet at the top
            if not stack or time_to_target > stack[-1]:
                stack.append(time_to_target)
        
        # overall
        # overall
        return len(stack)

    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        ans = prev = 0
        for pp, ss in sorted(zip(position, speed), reverse=True): 
            tt = (target - pp)/ss # time to arrive at target 
            if prev < tt: 
                ans += 1
                prev = tt
        return ans 

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

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

        return max_area

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

        for i, h in enumerate(heights + [0]):  # Add a sentinel height of 0
            while stack and heights[stack[-1]] > h:
                height = heights[stack.pop()]
                width = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, height * width)
            stack.append(i)

        return max_area

    def calculate_area(start, end):
        if start > end:
            return 0
        
        min_index = start
        for i in range(start, end + 1):
            if heights[i] < heights[min_index]:
                min_index = i
        
        left_area = calculate_area(start, min_index - 1)
        right_area = calculate_area(min_index + 1, end)
        current_area = heights[min_index] * (end - start + 1)
        
        return max(left_area, right_area, current_area)

    return calculate_area(0, len(heights) - 1)

    class SegmentTree:
        def __init__(self, heights):
            self.n = len(heights)
            self.tree = [0] * (4 * self.n)
            self.build(heights, 0, 0, self.n - 1)

        def build(self, heights, node, start, end):
            if start == end:  # Leaf node
                self.tree[node] = start
            else:
                mid = (start + end) // 2
                left = 2 * node + 1
                right = 2 * node + 2

                self.build(heights, left, start, mid)
                self.build(heights, right, mid + 1, end)

                # Combine the results of the children
                if heights[self.tree[left]] < heights[self.tree[right]]:
                    self.tree[node] = self.tree[left]
                else:
                    self.tree[node] = self.tree[right]

        def query(self, heights, node, start, end, l, r):
            if start > r or end < l:  # Range outside query bounds
                return -1
            if l <= start and end <= r:  # Range completely within query bounds
                return self.tree[node]

            mid = (start + end) // 2
            left = self.query(heights, 2 * node + 1, start, mid, l, r)
            right = self.query(heights, 2 * node + 2, mid + 1, end, l, r)

            if left == -1:  # If left part is out of range
                return right
            if right == -1:  # If right part is out of range
                return left
            return left if heights[left] < heights[right] else right

    
    def largestRectangleArea(self, heights: List[int]) -> int:
        def calculate_area(start, end):
                if start > end:
                    return 0
                min_index = tree.query(heights, 0, 0, len(heights) - 1, start, end)
                left_area = calculate_area(start, min_index - 1)
                right_area = calculate_area(min_index + 1, end)
                current_area = heights[min_index] * (end - start + 1)
                return max(left_area, right_area, current_area)

        tree = SegmentTree(heights)
        return calculate_area(0, len(heights) - 1)

    def removeKdigits(self, num: str, k: int) -> str:
        stack = []  # Stack to hold the digits of the resulting number

        for digit in num:
            # Remove digits from the stack if the current digit is smaller
            # and we still need to remove more digits (k > 0)
            while stack and k > 0 and stack[-1] > digit:
                stack.pop()
                k -= 1
            stack.append(digit)

        # If there are still digits to remove, remove from the end of the stack
        stack = stack[:-k] if k else stack

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

        # Return "0" if the result is empty
        return result or "0"