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

        return n+1

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

        # Note:
        # Kadane's Algorithm (Greedy / DP)
        # iterate over array
        # at every step either extend subarray or start new subarray
        # Result -> max sum

        n = len(nums)

        local_max = nums[0]
        global_max = nums[0]

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

            # nums[i]: start new subarray at i
            # local_max + nums[i]: extend previous subarray
            local_max = max(nums[i], local_max + nums[i])

            # compare to global max
            global_max = max(global_max, local_max)

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

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

        # Note:
        # Greedy (Kadane’s Algorithm)
        # iterate over array
        # at every step either extend subarray or start new subarray
        # Result -> max sum

        max_sum = nums[0]
        current_sum = 0

        # iterate over array
        for num in nums:


            # extend subarray: current_sum + num
            current_sum += num

            # start new subarray at i
            if current_sum < 0:
                current_sum = 0

            # compare to global max
            if current_sum > max_sum:
                max_sum = current_sum

        # overall: time complexity
        # overall: space complexity
        return max_sum

    def maxSubArray(self, nums: List[int]) -> int:
        # Note:
        # Divide & Conquer approach
        # 1. Process root -> split array into halves
        # 2. Explore Choices -> max subarray is:
        #    entirely in left half
        #    entirely in right half
        #    crosses the midpoint (ending at mid and starting at mid+1)
        # 3. Build -> recursively compute left, right, cross sums
        # Result -> max sum of array

        def helper(left, right):
            
            # single element, return element
            if left == right:
                return nums[left]

            # midpoint for split and cross_max
            mid = (left + right) // 2

            # check left and right subarray
            left_max = helper(left, mid)
            right_max = helper(mid + 1, right)

            # maximum suffix sum of the left half: best sum ending at mid
            left_sum = float('-inf')
            curr = 0
            for i in range(mid, left - 1, -1):
                curr += nums[i]
                left_sum = max(left_sum, curr)

            # maximum prefix sum of the right half: best sum starting at mid+1
            right_sum = float('-inf')
            curr = 0
            for i in range(mid + 1, right + 1):
                curr += nums[i]
                right_sum = max(right_sum, curr)

            # maximum subarray sum that spans across the midpoint.
            cross_max = left_sum + right_sum

            # pass max from left, right, and cross section to parent
            return max(left_max, right_max, cross_max)

        res = helper(0, len(nums) - 1)

        # overall: time complexity O(n log n)
        # overall: space complexity O(log n) recursion depth
        return res

    def canJump(self, nums: List[int]) -> bool:
        
        # Note:
        # 
        # Rolling Variable -> tracks farthest possible index we can reach
        # Iterate over array -> 
        # 2. Build From Previous -> maintain farthest reachable index so far
        # 3. Explore Choices -> if current index > farthest, return False (stuck)
        # 4. Result -> if iteration completes, last index is reachable

        n = len(nums)

        # rolling variable
        farthest = 0

        # iterate array
        for i in range(n):

            # reached an unreachable index, cannot reach end
            if i > farthest:
                return False

            # Build From Previous -> update farthest reachable
            farthest = max(farthest, i + nums[i])

            # Early exit -> can already reach or surpass last index
            if farthest >= n - 1:
                return True

        # last index is not reachable

        # overall: time complexity
        # overall: space complexity
        return False

    def jump(self, nums: List[int]) -> int:
        
        # Note:
        # Greedy (layer expansion like BFS)

        # A layer in this context is a BFS level of the array.
        # Each level contains all indices you can reach with the same number
        # of jumps. 
        
        n = len(nums)

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

        # Each level contains all indices you can reach with the same number
        # of jumps. 
        jumps = 0

        # current_end marks the rightmost index in the current layer. 
        # So when we reach current_end, it means we have finished exploring the
        # current layer, and current_end holds the best next move for this layer.
        current_end = 0

        # keeps track of the furthest index we can reach in this layer.
        farthest = 0

        # iterate -> 0 to n-2
        # problem guarantees we can always reach the last index,
        # so we don't need to check for unreachable branches
        for i in range(n-1):

            # update farthest reachable index for index
            farthest = max(farthest, i + nums[i])

            # reach end of current layer, go to next layer
            if i == current_end:
                jumps += 1          # need to jump
                current_end = farthest  # move to next layer

        # Result -> total jumps

        # overall: time complexity
        # overall: space complexity
        return jumps

    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        
        # Note:
        # Greedy Linear Scan
        # 0. Direct Boundary -> if total gas < total cost, impossible (-1)
        # 1. Process root -> traverse stations
        # 2. Build From Previous -> track current tank balance
        # 3. Explore Choices -> if tank < 0, reset start to next station
        # 4. Result -> return start index (guaranteed unique if feasible)

        n = len(gas)

        # not enough total gas to cover total cost
        if sum(gas) < sum(cost):
            return -1

        # current gas
        tank = 0
        # candidate starting station
        start = 0

        # try each starting station
        for i in range(n):

            # Question guarantees solution to be unique, so:
            # you don't need to try every starting point individually.
            # As you iterate, you maintain a running tank balance.
            # You never actually traverse every “branch”, but the greedy 
            # reset logic ensures the feasible branch is picked.

            # update tank balance
            tank += gas[i] - cost[i]

            # reset start if tank is negative
            # try next start candidate
            if tank < 0:
                tank = 0
                start = i + 1

        # Result -> guaranteed unique if feasible

        # overall: time complexity 
        # overall: space complexity
        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