def money!(n: int) -> int:

        return n+1

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

        # Divide & Conquer Approach:
        # The maximum subarray can be found by recursively splitting the array.
        # Key idea:
        #   1. Divide array into left and right halves
        #   2. Maximum subarray is either:
        #       - entirely in left half
        #       - entirely in right half
        #       - crossing the midpoint
        #   3. Combine results from left, right, and cross-midpoint to get current max
        # Recursion continues until single-element subarrays are reached

        # Early Stop vs Cross Midpoint Computation:
        # In Kadane, skipping negative running sums works because we 
        # only care about subarrays ending at current index.
        # In Divide & Conquer, we cannot break, because negative numbers 
        # might still be included in the optimal cross-midpoint subarray.

        # Note:
        # Divide & Conquer approach
        # 1. Process root -> split array into halves
        # 2. Explore Choices -> max subarray is:
        #       - starts at mid and scans into left half
        #       - starts at mid and scans into right half
        #       - starts at mid and includes both left and right half
        #         (sum of the left and right half results)
        # 3. Build -> recursively compute max of a section via max(left, right, cross_sum)
        # Result -> max sum of array

        # Recursive helper to compute max subarray in nums[left:right]
        def helper(left, right):
            
            # Base Case: single element
            # Only one element, max subarray is the element itself
            # tc: O(1), sc: O(1)
            if left == right:
                return nums[left]

            # Split array: compute midpoint
            # This reduces the search space to two halves
            # left half: nums[left:mid] 
            # right half: nums[mid+1:right]
            mid = (left + right) // 2

            # Recursive call on left half
            # Helper computes max subarray entirely in left half
            # tc: O(n/2 * log(n/2)) per left recursive calls (overall summed to O(n log n))
            left_max = helper(left, mid)

            # Recursive call on right half
            # Helper computes max subarray entirely in right half
            # tc: O(n/2 * log(n/2)) per right recursive calls (overall summed to O(n log n))
            right_max = helper(mid + 1, right)

            # Start at mid and linear scan into left half
            left_sum = float('-inf')
            curr = 0
            for i in range(mid, left - 1, -1):
                curr += nums[i]
                left_sum = max(left_sum, curr)

            # Start at mid and linear scan into right half
            right_sum = float('-inf')
            curr = 0
            for i in range(mid + 1, right + 1):
                curr += nums[i]
                right_sum = max(right_sum, curr)

            # Compute max subarray crossing mid:
            # bridge left and right scan results 
            cross_max = left_sum + right_sum

            # return left, right, and middle max to previous call
            return max(left_max, right_max, cross_max)

        # max subarray from [0, n-1]
        res = helper(0, len(nums) - 1)

        # overall: tc O(n log n)
        # overall: sc O(log n) recursion depth
        return res

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

        # Kadane's Algorithm (Greedy / 1D DP):
        # The maximum subarray problem can be solved by iterating through the array
        # and maintaining two key variables:
        #   1. local_max -> maximum subarray sum ending at the current index
        #   2. global_max -> maximum subarray sum seen so far
        # At each step, we either:
        #   - Extend the previous subarray (local_max + nums[i])
        #   - Start a new subarray at current element (nums[i])
        # The invariant: global_max always stores the maximum sum encountered

        # num of nums
        # tc: O(1)
        n = len(nums)

        # local_max: max sum ending at current index
        # global_max: overall max sum
        # sc: O(1)
        local_max = nums[0]
        global_max = nums[0]

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

            # At each index:
            # we are deciding whether to extend the array, 
            # or to stop the array and start a new one at the current index

            # extend previous subarray
            extend_prev = local_max + nums[i]

            # start a new subarray at current element
            start_new = nums[i]

            # choose the better option
            local_max = max(start_new, extend_prev)

            # Update global max if current local_max is greater
            # tc: O(1)
            global_max = max(global_max, local_max)

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

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

        # Kadane’s Algorithm (Greedy / Practical):
        # The maximum subarray problem can also be solved by maintaining:
        #   1. current_sum -> running sum of the subarray ending at the current index
        #   2. max_sum -> maximum sum seen so far
        # At each step, we either:
        #   - Extend the previous subarray by adding nums[i] (current_sum + nums[i])
        #   - Reset current_sum to 0 if the previous sum would reduce the total
        # This ensures current_sum always represents the best subarray ending at current index
        # max_sum tracks the overall maximum sum encountered

        # Initialize variables
        # sc: O(1)

        # overall max subarray sum
        max_array_sum = nums[0]

        # max sum ending at current index
        subarray_sum = 0

        # tc: iterate over n O(n)
        for num in nums:

            # Extend the previous subarray to include current index
            # tc: O(1)
            subarray_sum += num

            # Decision point: 
            #   - if current index causes subarray_sum to become negative,
            #     it is better to start a new subarray.
            #   - In other words, if current index causes subarray_sum to 
            #     at least be 0 or positive, it should be included.
            if subarray_sum < 0:
                subarray_sum = 0

            # Update max_sum if current_sum is greater
            if subarray_sum > max_array_sum:
                max_array_sum = subarray_sum

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

    def canJump(self, nums: List[int]) -> bool:
        
        # Greedy / 1D DP Approach:
        # We want to determine if we can reach the last index of the array.
        # Key idea:
        #   1. Maintain a rolling variable 'farthest' that represents 
        #      the farthest reachable index so far
        #   2. Iterate through the array:
        #       - If 'farthest' < current index, we cannot reach the current index, we got stuck
        #       - Otherwise, update 'farthest' to include jumps from current index
        #       - If last index <= 'farthest', we have passed the end, we can early exit
        
        # This is effectively a linear greedy scan, 
        # using previously computed reachability to avoid recomputation

        # number of indexes
        # tc: O(1)
        n = len(nums)

        # Rolling Variable:
        # farthest index currently reachable
        # sc: O(1)
        farthest = 0

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

            # Check: is current index past what we can reach
            # Implies: we cannot jump to current index, we got stuck
            # tc: O(1)
            if farthest < i:
                return False

            # Implies: we are able to jump to the current index
            # Then: add the jumping distance from the current index to our farthest counter
            # tc: O(1)
            farthest = max(farthest, i + nums[i])

            # Check: have we passed the last index
            # Implies: we can early exit, we reached the end
            # tc: O(1)
            if n-1 <= farthest:
                return True

        # Implies: ran out of index to jump from,
        #          we never reached the end

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

    def jump(self, nums: List[int]) -> int:
        
        # Greedy / Layer-by-Layer Expansion (BFS Analogy):
        # We want the minimum number of jumps to reach the last index.
        
        # Key Idea:
        # Treat the array like levels in BFS.
        #   - All indexes reached in k jumps are in the same k layer 
        #   - When we finishing checking all indexes within the k layer, we will determine
        #     the rightmost index we can jump to from any index in this k layer

        # We keep track of:
        #   1. current_end: boundaries of current k layer
        #   2. farthest:    farthest index reachable from this layer 
        
        # When we reach 'current_end', we:
        #   - Increment jump count
        #   - Move to next layer by setting current_end = farthest
        
        # This works because we always greedily expand the next layer
        # as far as possible before committing to another jump.

        n = len(nums)

        # Single Index: no jumps needed
        if n == 1:
            return 0

        # Tracker for current number of jumps
        k_jumps = 0
        
        # We check every k layer, to fins the rightmost index we can jump to,
        # we use layer_boundary to mark the end of the current layer we are checking
        k_layer_boundary = 0

        # While checking k layer, we track of the furthest index we can reach from this layer
        farthest = 0

        # We are guaranteed to reach the last index,
        # can simply iterate without checking for unreachable indexes
        # tc: iterate over n O(n)
        for i in range(n-1):

            # Check: candidate i within layer k, how far can we jump
            reach_from_i = i + nums[i]

            # Check: does candidate i provide a farther jump than the current
            #        farthest possible for this k layer
            farthest = max(farthest, i + nums[i])

            # Check: does our farthest jump pass the last index
            # Implies: found shortest number of jumps
            if farthest >= n - 1:
                return k_jumps + 1

            # Check: have we finished checking all indexes within this k layer
            # Implies: we have checked all of our options
            # Then: jump to the rightmost index we have found for this k layer
            if i == k_layer_boundary:

                # update jump count
                k_jumps += 1

                # mark next layer as the farthest jump
                k_layer_boundary = farthest

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

    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        
        # Greedy / Linear Scan Approach:
        # We want to determine the unique starting station (if any)
        # from which we can complete a full circuit.

        # Key Ideas:
        #   1. If total gas < total cost, completing the circuit is impossible.
        #   2. Traverse stations while maintaining a running fuel balance (tank).
        #   3. If tank becomes negative at station i, then:
        #       - No station between the previous start and i can be a valid start.
        #       - We reset the start to i + 1 and restart the tank.
        #   4. If a solution exists, it is guaranteed to be unique.

        # number of stations
        # tc: O(1)
        n = len(gas)

        # Direct Boundary Check:
        # If total gas is less than total cost, it's impossible to complete the loop
        # tc: O(n)
        if sum(gas) < sum(cost):
            return -1

        # Rolling Variable:
        # tank -> current gas balance while traversing
        # sc: O(1)
        tank = 0

        # Candidate starting station
        start = 0

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


            # Build From Previous:
            # Update current gas balance after traveling from station i
            # tc: O(1)
            tank += gas[i] - cost[i]

            # Explore Choices:
            # If tank < 0, we cannot reach station i+1 from current start
            # Implies:
            #   - Any station between 'start' and i is also invalid as a start
            #   - Reset start to i + 1 and reset tank
            # tc: O(1)
            if tank < 0:
                tank = 0
                start = i + 1

        # Result:
        # Since total gas >= total cost, the final 'start' is guaranteed to work

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

    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        
        # Note:
        # Greedy with HashMap
        # total cards must be divisible by groupSize
        # sort cards
        # group cards from low to high
        # for each group start, grab all cards needed in group
        # Result -> return True if all groups formed

        n = len(hand)

        # total cards must be divisible by groupSize
        if n % groupSize != 0:
            return False

        # frequency of each card
        count = Counter(hand)

        # process cards in ascending order
        for runStartCard in sorted(count):

            # attempt to form group starting at card
            while count[runStartCard] > 0:

                # attempt to grab all cards for current run starting from card
                for nextCard in range(runStartCard, runStartCard + groupSize):

                    # no run is possible 
                    if count[nextCard] == 0:
                        return False

                    # decrease count
                    count[nextCard] -= 1

        # overall: time complexity 
        # overall: space complexity
        return True

    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        # Note:
        # Greedy using min heap and frequency map
        # 0. Direct Boundary -> total cards must be divisible by groupSize
        # 1. Process root -> build frequency map and min-heap of unique cards
        # 2. Build From Previous -> repeatedly form groups starting from smallest card
        # 3. Explore Choices -> check consecutive cards and update frequencies
        # Result -> return True if all groups can be formed

        n = len(hand)

        # check if total cards can be divided into complete groups
        if n % groupSize != 0:
            return False

        # frequency map of cards
        counter = {}
        for h in hand:
            counter[h] = 1 + counter.get(h, 0)

        # min heap of unique cards
        heap = list(counter.keys())
        heapq.heapify(heap)

        # repeatedly form groups
        while heap:

            first = heap[0]  # smallest available card

            # try to form a consecutive run starting from first
            for h in range(first, first + groupSize):

                # cannot form run if card missing
                if h not in counter:
                    return False

                # decrement frequency
                counter[h] -= 1

                # remove from heap if no cards left
                if counter[h] == 0:

                    # ensure heap order is maintained
                    if h != heap[0]:
                        return False
                    heapq.heappop(heap)

        # all runs successfully formed

        # overall: time complexity
        # overall: space complexity
        return True

    def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:

        # Note:
        # Greedy validation

        # instead of simulating all operations, you just need to 
        # ensure that for each coordinate of the target, there is at least 
        # one triplet that contributes the required value without exceeding it.

        # grab target values
        x, y, z = target

        # coverage of each target index
        good = [False, False, False]

        for a, b, c in triplets:

            # skip if triplet exceeds target in any dimension as 
            # merging triplet would overshoot the target since we use max()
            if a > x or b > y or c > z:
                continue

            # mark contribution toward target dimensions
            if a == x:
                good[0] = True
            if b == y:
                good[1] = True
            if c == z:
                good[2] = True

            # early exit -> all dimensions matched
            if all(good):
                return True

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

    def partitionLabels(self, s: str) -> List[int]:

        # Note:
        # Greedy partitioning
        # 0. Direct Length -> empty string boundary covered implicitly
        # 1. Precompute last occurrence of each character
        # 2. Process root -> scan through string with two pointers
        # 3. Expand window -> current partition must at least reach the furthest last occurrence seen so far
        # 4. Build Partition -> when current index == window end, cut partition
        # 5. Result -> return lengths of all partitions

        # effectively gives the last occurrence of each character in the string,
        # as last occurrence of char will overwrite index previous 
        last_index = {char: i for i, char in enumerate(s)}

        partitions = []

        # starting index of current partition
        start = 0 

        # Furthest index that the current partition must reach to 
        # include all characters seen so far
        # Thus, when the iteration index i reaches end, it means the 
        # current partition contains all occurrences of the characters seen 
        # in this window, so you can "cut" the partition:
        end = 0

        # iterate left to right
        for i, char in enumerate(s):

            # As we go left to right, if a character appears multiple times, 
            # the dictionary keeps updating its value to the latest index

            # ensures the current partition extends at least until the 
            # last occurrence of every character seen so far.
            end = max(end, last_index[char])

            # reached the last occurrence of every character seen so far,
            # safe to cut
            if i == end:
                partitions.append(end - start + 1)
                start = i + 1

        # overall: time complexity
        # overall: space complexity
        return partitions   

    def checkValidString(self, s: str) -> bool:
        # Note:
        # Greedy balance with range tracking
        # empty string is valid (covered implicitly)
        # maintain lower and upper bound of open '(' count
        # Bounds:
        #    '(' increases both lower and upper
        #    ')' decreases both (but lower cannot go below 0)
        #    '*' can be '(', ')' or empty
        #         -> lower decreases by 1 (min 0), upper increases by 1
        # if upper < 0 at any point, invalid
        # Result -> valid if lower == 0 at the end

        # parenthesis count
        lower = 0 
        upper = 0

        # iterate
        for char in s:

            # '(' increases both lower and upper
            if char == "(":
                lower += 1
                upper += 1

            # ')' decreases both (but lower cannot go below 0)
            elif char == ")":
                lower = max(lower - 1, 0)
                upper -= 1

            # '*' can be '(', ')' or empty
            # lower decreases by 1 (min 0), upper increases by 1
            else:
                lower = max(lower - 1, 0)  # treat as ')'
                upper += 1                 # treat as '('

            # if upper < 0 at any point, invalid
            if upper < 0:
                return False

        # lower == 0 means all opens can be matched

        # overall: time complexity
        # overall: space complexity
        return lower == 0