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:
        
        # note: 
        # in python, an empty string "" is falsy evaluating to false
        # not "" -> true

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

    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:

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

        for c in s:

            if c in mapping:

                if not stack:
                    return False

                topElem = stack.pop()

                if mapping[c] != topElem:
                    return False 

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

        return not stack

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

        stack = []

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

        for c in s:
            
            if c in mapping:

                if not stack:
                    return False

                topElem = stack.pop()

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

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

        # Empty List In Python []:
        # An empty list [] is falsy evaluating to false
        # not [] -> true

        # sc: relative to input O(n)
        stack = []

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

            # found close bracket, match with open

            # tc: constant length list check effectively constant O(1)
            if c in ')]}':

                # check if stack is empty, no open to match
                # tc: len check O(1)
                if not stack:
                    return False

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

                # check if open bracket matches
                # tc: equal in constant O(1)
                if  ((c == ')' and topElem != '(') or
                     (c == '}' and topElem != '{') or
                     (c == ']' and topElem != '[')):
                    return False

            # found open bracket, push to stack

            # tc: constant length list check effectively constant O(1)
            if c in '([{':

                # tc: list append amortized O(1)
                stack.append(c)
                               
        # stack is empty, success

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

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

        # sc: relative to input O(n)
        stack = []

        # bracket mapping: closed -> open

        # sc: create hashmap fixed entries O(1)
        mapping = {
            ')' : '(',
            ']' : '[',
            '}' : '{'
        }

        # tc: iterate over string of n length O(n)
        for c in s:
            
            # found close bracket, match open
            if c in mapping:

                # check if stack is empty, no open to match
                # tc: len check O(1)
                if not stack:
                    return False

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

                # check if open bracket matches
                # tc: equal in constant O(1)
                if mapping[c] != topElem:
                    return False
            
            # found opening bracket, push to stack
            else:

                # tc: list append amortized O(1)
                stack.append(c)
                
        # stack is empty, success

        # overall: time complexity O(n)
        # overall: space complexity O(n)
        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 

class MinStack:

    # Main + MinTracker Stack:
    # Tracks the min value at each level of the main stack. 

    # overall: sc O(n)
    def __init__(self):

        # sc: two stacks for n elements O(n)

        # all values
        self.mainStack = []
        # minimum value at current level
        self.minTracker = []
        # pointer to the curr element
        self.logicalSize = 0

    # helper:
    # edge case checker for empty stack
    def _validateNotEmpty(self, errMsg: str):
        if self.logicalSize == 0:
            raise IndexError(errMsg)

    # helper:
    # checks if logical pointer is behind actual length of stack
    def _checkLogicalVsActualSize(self, stack):
        return self.logicalSize < len(stack)
            
    # overall: tc O(1)
    def push(self, val: int):

        # If logical pointe ris behind actual length, we replace at pointer
        # else append to end of the stack
        if self._checkLogicalVsActualSize(self.mainStack):
            self.mainStack[self.logicalSize] = val
        else:
            self.mainStack.append(val)

        # new min:
        # check if non empty stack, if so compare against previous min
        # else update to new value
        currMin = min(val, self.minTracker[self.logicalSize - 1] if self.logicalSize > 0 else val)

        # If logical pointer is behind actual length, we replace at pointer
        # else append to end of the stack
        if self._checkLogicalVsActualSize(self.minTracker):
            self.minTracker[self.logicalSize] = currMin
        else:
            self.minTracker.append(currMin)
        
        # increase logical size
        self.logicalSize += 1

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

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

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

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

class MinStack:

    # MinTracker Tuple Stack: 
    # We combine the main and minTracker stack with a tuple (val, min), 
    # tracking the min at each level of the stack.

    # overall: sc O(n)
    def __init__(self):

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

    # helper:
    # edge case checker for empty stack
    def _validateNotEmpty(self, errMsg: str):
        if self.size == 0:
            raise IndexError(errMsg)
 
    # helper:
    # checks if logical pointer is behind actual length of stack
    def _checkLogicalVsActualSize(self):
        return self.size < len(self.stack)

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

        # new min:
        # 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)
        
        # If logical pointer is behind actual length, we replace at pointer
        # else append to end of the stack
        if self._checkLogicalVsActualSize():
            self.stack[self.size] = (val, currMin)
        else:
            self.stack.append((val, currMin))

        # increase logical size
        self.size += 1

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

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

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

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

    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:

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

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

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

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

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

    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 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]:
       
        res = []

        def helper(curr, open_count, close_count):

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

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

            
        helper([], 0, 0)

        return res

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

        def helper(curr, open_paren, close_paren):

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

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

        helper([], 0, 0)

        return res

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

        def helper(curr, open_count, close_count):

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

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

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

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

        return res

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

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

        # Store valid parentheses
        result = []

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

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

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

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

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

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

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

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

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

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

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

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

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


        return dp[n]

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

        res = []

        def helper(currList, openCount, closedCount):

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

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

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

        
        helper([], 0, 0)

        return res

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

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

        dp[0] = [""]

        for i in range(n+1):

            for j in range(i):

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

        return dp[n]

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

        # String Immutability:
        # Every time we do current + "(" in python a new string is created
        # and the entire contents of current are copied.
        # Since this happens at every recursion level and there are Catalan(n) valid sequences,
        # the time becomes O(Catalan(n) * n^2)
        # due to copying. 
        # Solution 2 has a time of O(Catalan(n) * n), this is here to show the slow version

        # Temporary/Working Memory:
        # We also use more memory with strings as along one recursion path we create ~n strings
        # each of up to length n, so peak temporary memory is O(n^2)
        # Solution 2 has temporary memory of O(n), since we have a single stack we are popping/appending from

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

        res = []

        # tc: each recursion path creates  explores a state; only leaf call does ''.join(), leading to O(n)
        # sc: call stack depth is O(n), string copying adds O(n) per leaf path, leading to O(n^2)
        def dfs_backtrack(current: List[str], num_open: int, num_closed: int):

            # Process Root: reached valid string 
            if len(current) == n * 2:
                res.append(current)
                return

            # Explore Choice 1: add '('
            # Check: open count is less than total expected
            # Implies: adding '(' will create valid string
            if num_open < n: 

                # Build: append open '('
                # tc: concat O(n)
                new_str = current + "("

                # Explore: recursion with new string copy
                dfs_backtrack(new_str, num_open + 1, num_closed)

                # Backtrack: no need to modify copy as original string still exists

            # Explore Choice 2: add ')'
            # Check: closed count is less than open count
            # Implied: adding ')' is required for valid string
            if num_closed < num_open:
                
                # Build: append close ')'
                # tc: concat per iteration O(n)
                new_str = current + ")"
    
                # Explore: recursion with new string copy
                dfs_backtrack(new_str, num_open, num_closed + 1)

                # Backtrack: no need to modify copy as original string still exists

        # Initial call, empty list passed
        dfs_backtrack("", 0, 0)

        # overall: tc O(Catalan(n) * n^2)
        # overall: sc O(Catalan(n) * n)
        return res

    def generateParenthesis(self, n: int) -> List[str]:
        
        # List Mutability:
        # We use a single list curr and modify it in place using append/pop.
        # Append() and pop() are both constant O(1) and no copying happens at each recursion step.
        # The list only gets converted once we have found a valid combination using "".join(curr).
        # Since there are Catalan(n) valid sequences 
        # the time becomes O(Catalan(n) * n) which is faster than the string version of O(Catalan(n) * n^2)

        # Temporary/Working Memory:
        # We use a single stack to track our changes, so peak temporary memory is O(n)

        # Backtracking:
        # Explores all valid sequences of parentheses.
        # Only when a complete sequence is found (length == 2 * n), 
        # we convert the list to a string via concat in O(n)

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

            # Base case: 
            # If we have used all open and close parentheses
            if openCount == n and closeCount == n:
                # tc: convert once at leaf for 2n length O(n)
                res.append("".join(current))
                return

            # Recursive case 1: add '('
            # Check: open count is less than total expected
            # Ensures: string is always valid, with total number of parens being valid
            if openCount < n: 

                # Build: append open '('
                current.append('(')

                # Explore: recurse with updated list
                helper(current, openCount + 1, closeCount)

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

                # Build: append close ')'
                current.append(')')

                # Explore: recurse with updated list
                helper(current, openCount, closeCount + 1)

                # Backtrack: remove last open '('
                current.pop()

        # Initial call, empty list passed
        backtrack([], 0, 0)

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

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

        # Explicit Iterative Stack:
        # Simulates backtracking process iteratively by storing state on the stack.
        # Each state element holds the current string and counts of open and closed parentheses,
        # which allows state tracking without recursion

        # Store valid parentheses
        result = []

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

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

            # Process Root:
            # Grab/pop current state from stack, current state is explored only once
            curr, openCount, closeCount = stack.pop()

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

            # Explore Choice 1: add '('
            # Check: open count is less than total expected
            # Implies: we have space to add an open parenthesis
            if openCount < n:
                
                # Build: append open '('
                # Creating copy of list to avoid mutating other branches,
                # (cannot do curr.append('(') because that would modify the original list)
                new_curr = curr.copy()
                new_curr.append('(')

                # Explore: iterative recursion by putting new state on stack for future exploration
                stack.append((new_curr, openCount + 1, closeCount))

                # Backtrack:
                # No need to .pop() as the pop() from the stack will remove this new state eventually

            # Explore Choice 2: add ')'
            # Check: closed count is less than open count
            # Implies: we have a matching open for our closed parenthesis
            if closeCount < openCount:

                # Build: append close ')'
                # Creating copy of list to avoid mutating other branches,
                # (cannot do curr.append(')') because that would modify the original list)
                new_curr = curr + [')']

                # Explore: iterative recursion by putting new state on stack for future exploration
                stack.append((new_curr, openCount, closeCount + 1))

                # Backtrack:
                # No need to .pop() as the pop() from the stack will remove this new state eventually

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

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

        # Two Pointer:
        # If we have a list of valid combinations of parenthesis, 
        # we can append them in a format that generate more valid combinations

        # dp:    list of list of parentheses combinations 
        # dp[n]: list containing all valid parenthesis combinations for the nth level (n pair of parenthesis)
        dp = []
        for _ in range(n + 1):
            dp.append([])     

        # Base case: valid combination for n = 0
        dp[0] = [""]  
        
        # Iterate: create valid lists from dp[1] to dp[n]
        # Current: building list for ith pair
        # tc: iterate over list of n length O(n) 
        for i in range(1, n + 1): 

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

                # Opposite Ends Two Pointer Variation:
                # Since pointers will meet in middle and cross each other, 
                # they will get all variations of combinations already built,
                # which allows us to format them to generate more valid combinations

                # Setup: Opposite Ends Two Pointer Variation
                # Forward and Reverse Iteration

                # Forward Iteration List 1: 
                # Iterate over each valid string of parentheses for level j,
                # starting at first parentheses pairs level of 0 pairs of parenthesis
                for left in dp[j]:

                    # Reverse Iteration List 2: 
                    # Iterate over each valid string of parentheses for level (i - 1 - j),
                    # starting at last parenthesis pairs level of largest number pairs currently available
                    for right in dp[i - 1 - j]:

                        # Generation Format:
                        # ({left}){right} or {left}({right}) are both valid formulas
                        # Since we are doing Opposite Ends and left and right will cross over each other,
                        # left and right will both individually use all values
                        # which means with these 2 iterations
                        # we are eventually doing both the same thing
                        # dp[i].append(f"{left}({right})")
                        dp[i].append(f"({left}){right}")

        # overall: tc O(Catalan(n) * n)
        # overall: sc O(Catalan(n) * n)
        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]: 

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

        res = [0] * len(temperatures)

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

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

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

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

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

            stack.append(i)

        return res

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

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

        res = [0] * len(temperatures)

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

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

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

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

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

            stack.append(i)

        return res

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

        dp = [0] * len(temperatures)

        hottest_day = temperatures[len(temperatures)-1]

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

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

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

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

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


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

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

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

            stack.append(i)

        return res

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

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

        hottest_day = temperatures[n-1]

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

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

            else:
                j = i + 1

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

                dp[i] = j-i

        return dp

    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