from typing import List


class Solution:
    """
    ## 135. Candy

    There are n children standing in a line. Each child is assigned a rating value.
    You must give each child at least one candy. Children with a higher rating than
    their adjacent neighbor must receive more candies. Return the minimum total candies.

    ### Example
    ```text
    Input:  ratings = [1, 0, 2]
    Output: 5  (give [2, 1, 2] candies)

    Input:  ratings = [1, 2, 2]
    Output: 4  (give [1, 2, 1] candies)
    ```

    ### Constraints
    - 1 <= ratings.length <= 2 * 10^4
    - 0 <= ratings[i] <= 2 * 10^4
    """

    def candy(self, ratings: List[int]) -> int:
        # Two passes: left-to-right ensures higher-rated child gets more than left neighbor
        # Right-to-left ensures higher-rated child gets more than right neighbor
        # Take max of both passes at each position
        # O(n) time, O(n) space — two-pass left-right then right-left
        n = len(ratings)
        candies = [1] * n
        # Left pass: ensure right neighbor with higher rating gets more
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                candies[i] = candies[i - 1] + 1
        # Right pass: ensure left neighbor with higher rating gets more
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                candies[i] = max(candies[i], candies[i + 1] + 1)
        return sum(candies)


if __name__ == '__main__':
    s = Solution()
    assert s.candy([1, 0, 2]) == 5
    assert s.candy([1, 2, 2]) == 4
    assert s.candy([1]) == 1
    assert s.candy([1, 3, 2, 2, 1]) == 7
    print("All tests passed.")

from collections import deque


class Solution:
    """
    ## 649. Dota2 Senate

    In the Dota2 world, the senate consists of senators from two parties: Radiant (R) and Dire (D).
    Each senator can either ban another senator's right or announce victory if all remaining senators
    are from their party. Both sides act optimally. Return the winning party.

    ### Example
    ```text
    Input:  senate = "RD"
    Output: "Radiant"

    Input:  senate = "RDD"
    Output: "Dire"
    ```

    ### Constraints
    - 1 <= senate.length <= 10^4
    - senate[i] is either 'R' or 'D'
    """

    def predictPartyVictory(self, senate: str) -> str:
        # Two queues of indices; smaller index bans the other party's next senator
        # Re-enqueue the winner with index += n to maintain relative order
        # O(n) time, O(n) space — queue simulation
        radiant = deque()
        dire = deque()
        n = len(senate)
        for i, c in enumerate(senate):
            if c == 'R':
                radiant.append(i)
            else:
                dire.append(i)
        while radiant and dire:
            r, d = radiant.popleft(), dire.popleft()
            # Whoever has the lower index acts first and bans the other
            if r < d:
                radiant.append(r + n)
            else:
                dire.append(d + n)
        return "Radiant" if radiant else "Dire"


if __name__ == '__main__':
    s = Solution()
    assert s.predictPartyVictory("RD") == "Radiant"
    assert s.predictPartyVictory("RDD") == "Dire"
    assert s.predictPartyVictory("R") == "Radiant"
    assert s.predictPartyVictory("DDRRR") == "Dire"
    print("All tests passed.")

from typing import List


class Solution:
    """
    ## 134. Gas Station

    There are n gas stations in a circle. You are given two integer arrays gas and cost.
    Return the starting station's index if you can travel around the circuit once in the
    clockwise direction, otherwise return -1. If a solution exists, it is guaranteed to be unique.

    ### Example
    ```text
    Input:  gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
    Output: 3

    Input:  gas = [2, 3, 4], cost = [3, 4, 3]
    Output: -1
    ```

    ### Constraints
    - n == gas.length == cost.length
    - 1 <= n <= 10^5
    - 0 <= gas[i], cost[i] <= 10^4
    """

    def canCompleteCircuit_brute(self, gas: List[int], cost: List[int]) -> int:
        # O(n^2) time, O(1) space
        n = len(gas)
        for start in range(n):
            tank = 0
            for i in range(n):
                idx = (start + i) % n
                tank += gas[idx] - cost[idx]
                if tank < 0:
                    break
            else:
                return start
        return -1

    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        # If total gas >= total cost, a solution exists
        # Start from the index after any point where running sum goes negative
        # O(n) time, O(1) space — single pass
        total = tank = start = 0
        for i, (g, c) in enumerate(zip(gas, cost)):
            diff = g - c
            total += diff
            tank += diff
            if tank < 0:
                start = i + 1
                tank = 0
        return start if total >= 0 else -1


if __name__ == '__main__':
    s = Solution()
    assert s.canCompleteCircuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]) == 3
    assert s.canCompleteCircuit([2, 3, 4], [3, 4, 3]) == -1
    assert s.canCompleteCircuit_brute([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]) == 3
    print("All tests passed.")

from typing import List
from collections import Counter


class Solution:
    """
    ## 846. Hand of Straights

    Given an integer array hand and an integer groupSize, return true if the cards can be
    rearranged into groups of groupSize consecutive cards.

    ### Example
    ```text
    Input:  hand = [1, 2, 3, 6, 2, 3, 4, 7, 8], groupSize = 3
    Output: true  (groups: [1,2,3], [2,3,4], [6,7,8])

    Input:  hand = [1, 2, 3, 4, 5], groupSize = 4
    Output: false
    ```

    ### Constraints
    - 1 <= hand.length <= 10^4
    - 0 <= hand[i] <= 10^9
    - 1 <= groupSize <= hand.length
    """

    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        # Sort cards; greedily form groups starting from the smallest card
        # Use a counter; for each group start, consume groupSize consecutive values
        # O(n log n) time, O(n) space — sort + greedy with counter
        if len(hand) % groupSize:
            return False
        count = Counter(hand)
        for card in sorted(count):
            if count[card] > 0:
                need = count[card]
                for i in range(groupSize):
                    if count[card + i] < need:
                        return False
                    count[card + i] -= need
        return True


if __name__ == '__main__':
    s = Solution()
    assert s.isNStraightHand([1, 2, 3, 6, 2, 3, 4, 7, 8], 3) == True
    assert s.isNStraightHand([1, 2, 3, 4, 5], 4) == False
    assert s.isNStraightHand([1, 2, 3], 3) == True
    assert s.isNStraightHand([1], 1) == True
    print("All tests passed.")

from typing import List


class Solution:
    """
    ## 55. Jump Game

    Given an integer array nums where nums[i] is the maximum jump length from index i,
    return true if you can reach the last index starting from index 0.

    ### Example
    ```text
    Input:  nums = [2, 3, 1, 1, 4]
    Output: true

    Input:  nums = [3, 2, 1, 0, 4]
    Output: false
    ```

    ### Constraints
    - 1 <= nums.length <= 10^4
    - 0 <= nums[i] <= 10^5
    """

    def canJump_dp(self, nums: List[int]) -> bool:
        # O(n^2) time, O(n) space — DP
        n = len(nums)
        dp = [False] * n
        dp[0] = True
        for i in range(1, n):
            for j in range(i):
                if dp[j] and j + nums[j] >= i:
                    dp[i] = True
                    break
        return dp[-1]

    def canJump(self, nums: List[int]) -> bool:
        # Track the farthest index reachable; if current index exceeds it, can't proceed
        # Update farthest at each step; return True if we reach or pass last index
        # O(n) time, O(1) space — track farthest reachable index
        farthest = 0
        for i, jump in enumerate(nums):
            if i > farthest:
                return False
            farthest = max(farthest, i + jump)
        return True


if __name__ == '__main__':
    s = Solution()
    assert s.canJump([2, 3, 1, 1, 4]) == True
    assert s.canJump([3, 2, 1, 0, 4]) == False
    assert s.canJump([0]) == True
    assert s.canJump_dp([2, 3, 1, 1, 4]) == True
    assert s.canJump_dp([3, 2, 1, 0, 4]) == False
    print("All tests passed.")

from typing import List


class Solution:
    """
    ## 45. Jump Game II

    Given a 0-indexed integer array nums, return the minimum number of jumps to reach
    the last index. You can always reach the last index.

    ### Example
    ```text
    Input:  nums = [2, 3, 1, 1, 4]
    Output: 2  (jump 1 step from index 0 to 1, then 3 steps to last index)

    Input:  nums = [2, 3, 0, 1, 4]
    Output: 2
    ```

    ### Constraints
    - 1 <= nums.length <= 10^4
    - 0 <= nums[i] <= 1000
    - The answer is guaranteed to exist.
    """

    def jump_dp(self, nums: List[int]) -> int:
        # O(n^2) time, O(n) space — DP
        n = len(nums)
        dp = [float('inf')] * n
        dp[0] = 0
        for i in range(n):
            for j in range(1, nums[i] + 1):
                if i + j < n:
                    dp[i + j] = min(dp[i + j], dp[i] + 1)
        return dp[-1]

    def jump(self, nums: List[int]) -> int:
        # Greedy BFS levels: at each jump, find the farthest reachable position
        # Increment jumps when we exhaust the current level's range
        # O(n) time, O(1) space — BFS-like level tracking
        jumps = cur_end = farthest = 0
        for i in range(len(nums) - 1):
            farthest = max(farthest, i + nums[i])
            if i == cur_end:
                jumps += 1
                cur_end = farthest
        return jumps


if __name__ == '__main__':
    s = Solution()
    assert s.jump([2, 3, 1, 1, 4]) == 2
    assert s.jump([2, 3, 0, 1, 4]) == 2
    assert s.jump([1]) == 0
    assert s.jump_dp([2, 3, 1, 1, 4]) == 2
    print("All tests passed.")

class Solution:
    """
    ## 1871. Jump Game VII

    Given a binary string s and integers minJump and maxJump, you start at index 0
    (which is '0'). Return true if you can reach the last index, where you can jump
    from index i to any index j such that i + minJump <= j <= i + maxJump and s[j] == '0'.

    ### Example
    ```text
    Input:  s = "011010", minJump = 2, maxJump = 3
    Output: true  (0 -> 3 -> 5)

    Input:  s = "01101110", minJump = 2, maxJump = 3
    Output: false
    ```

    ### Constraints
    - 2 <= s.length <= 10^5
    - s[i] is either '0' or '1'
    - s[0] == '0'
    - 1 <= minJump <= maxJump < s.length
    """

    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
        # BFS/sliding window: track reachable positions; from each, jump [minJump, maxJump]
        # Use a pointer to avoid re-processing already-covered positions
        # O(n) time, O(n) space — DP with prefix sum sliding window
        n = len(s)
        reach = [False] * n
        reach[0] = True
        prefix = 0  # count of reachable positions in current window
        for i in range(1, n):
            if i >= minJump:
                prefix += reach[i - minJump]
            if i > maxJump:
                prefix -= reach[i - maxJump - 1]
            reach[i] = prefix > 0 and s[i] == '0'
        return reach[-1]


if __name__ == '__main__':
    s = Solution()
    assert s.canReach("011010", 2, 3) == True
    assert s.canReach("01101110", 2, 3) == False
    assert s.canReach("00", 1, 1) == True
    print("All tests passed.")

from typing import List


class Solution:
    """
    ## 860. Lemonade Change

    At a lemonade stand, each lemonade costs $5. Customers pay with $5, $10, or $20 bills.
    You start with no change. Return true if you can provide every customer with correct change.

    ### Example
    ```text
    Input:  bills = [5, 5, 5, 10, 20]
    Output: true

    Input:  bills = [5, 5, 10, 10, 20]
    Output: false
    ```

    ### Constraints
    - 1 <= bills.length <= 10^5
    - bills[i] is either 5, 10, or 20
    """

    def lemonadeChange(self, bills: List[int]) -> bool:
        # Track $5 and $10 bills; greedily use $10 before $5 when making $15 change
        # O(n) time, O(1) space
        five = ten = 0
        for bill in bills:
            if bill == 5:
                five += 1
            elif bill == 10:
                if not five:
                    return False
                five -= 1
                ten += 1
            else:  # bill == 20
                if ten and five:
                    ten -= 1
                    five -= 1
                elif five >= 3:
                    five -= 3
                else:
                    return False
        return True


if __name__ == '__main__':
    s = Solution()
    assert s.lemonadeChange([5, 5, 5, 10, 20]) == True
    assert s.lemonadeChange([5, 5, 10, 10, 20]) == False
    assert s.lemonadeChange([5]) == True
    assert s.lemonadeChange([10]) == False
    print("All tests passed.")

from typing import List


class Solution:
    """
    ## 978. Longest Turbulent Subarray

    A subarray is turbulent if the comparison sign alternates between each adjacent pair.
    Return the length of the longest turbulent subarray.

    ### Example
    ```text
    Input:  arr = [9, 4, 2, 10, 7, 8, 8, 1, 9]
    Output: 5  (subarray [4, 2, 10, 7, 8])

    Input:  arr = [4, 8, 12, 16]
    Output: 2

    Input:  arr = [100]
    Output: 1
    ```

    ### Constraints
    - 1 <= arr.length <= 4 * 10^4
    - 0 <= arr[i] <= 10^9
    """

    def maxTurbulenceSize_window(self, arr: List[int]) -> int:
        # O(n) time, O(1) space — sliding window, reset on equal or non-alternating
        n = len(arr)
        if n == 1:
            return 1
        best = cur = 1
        for i in range(1, n):
            cmp = (arr[i] > arr[i-1]) - (arr[i] < arr[i-1])  # -1, 0, or 1
            if cmp == 0:
                cur = 1
            elif i == 1 or cmp == ((arr[i-1] > arr[i-2]) - (arr[i-1] < arr[i-2])):
                cur = 2
            else:
                cur += 1
            best = max(best, cur)
        return best

    def maxTurbulenceSize(self, arr: List[int]) -> int:
        # Sliding window: extend if alternating comparison sign, else reset to 2 or 1
        # Track current turbulent length and update global max
        # O(n) time, O(n) space — DP with inc/dec arrays
        n = len(arr)
        if n == 1:
            return 1
        inc = [1] * n  # length of turbulent subarray ending here with arr[i-1] < arr[i]
        dec = [1] * n  # length of turbulent subarray ending here with arr[i-1] > arr[i]
        best = 1
        for i in range(1, n):
            if arr[i] > arr[i-1]:
                inc[i] = dec[i-1] + 1
            elif arr[i] < arr[i-1]:
                dec[i] = inc[i-1] + 1
            best = max(best, inc[i], dec[i])
        return best


if __name__ == '__main__':
    s = Solution()
    assert s.maxTurbulenceSize([9, 4, 2, 10, 7, 8, 8, 1, 9]) == 5
    assert s.maxTurbulenceSize([4, 8, 12, 16]) == 2
    assert s.maxTurbulenceSize([100]) == 1
    assert s.maxTurbulenceSize([9, 9]) == 1
    assert s.maxTurbulenceSize_window([9, 4, 2, 10, 7, 8, 8, 1, 9]) == 5
    assert s.maxTurbulenceSize_window([4, 8, 12, 16]) == 2
    assert s.maxTurbulenceSize_window([100]) == 1
    print("All tests passed.")

from typing import List


class Solution:
    """
    ## 53. Maximum Subarray

    Given an integer array nums, find the subarray with the largest sum and return its sum.

    ### Example
    ```text
    Input:  nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    Output: 6  (subarray [4, -1, 2, 1])

    Input:  nums = [1]
    Output: 1

    Input:  nums = [5, 4, -1, 7, 8]
    Output: 23
    ```

    ### Constraints
    - 1 <= nums.length <= 10^5
    - -10^4 <= nums[i] <= 10^4
    """

    def maxSubArray_brute(self, nums: List[int]) -> int:
        # O(n^2) time, O(1) space
        n, best = len(nums), nums[0]
        for i in range(n):
            curr = 0
            for j in range(i, n):
                curr += nums[j]
                best = max(best, curr)
        return best

    def maxSubArray(self, nums: List[int]) -> int:
        # Kadane's: extend current subarray or start fresh if current sum goes negative
        # Track global max throughout
        # O(n) time, O(1) space — Kadane's algorithm
        best = curr = nums[0]
        for x in nums[1:]:
            curr = max(x, curr + x)
            best = max(best, curr)
        return best


if __name__ == '__main__':
    s = Solution()
    assert s.maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
    assert s.maxSubArray([1]) == 1
    assert s.maxSubArray([5, 4, -1, 7, 8]) == 23
    assert s.maxSubArray_brute([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
    print("All tests passed.")

from typing import List


class Solution:
    """
    ## 918. Maximum Sum Circular Subarray

    Given a circular integer array nums, return the maximum possible sum of a non-empty subarray.
    A circular array means the end of the array connects to the beginning.

    ### Example
    ```text
    Input:  nums = [1, -2, 3, -2]
    Output: 3  (subarray [3])

    Input:  nums = [5, -3, 5]
    Output: 10  (subarray [5, 5] wrapping around)

    Input:  nums = [-3, -2, -3]
    Output: -2
    ```

    ### Constraints
    - 1 <= nums.length <= 3 * 10^4
    - -3 * 10^4 <= nums[i] <= 3 * 10^4
    """

    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        # Case 1: max subarray is non-wrapping — standard Kadane's
        # Case 2: max subarray wraps — equals total_sum - min_subarray_sum
        # Edge case: if all elements negative, return max (min subarray = whole array)
        # O(n) time, O(1) space — Kadane's for both max and min subarray
        total = sum(nums)
        max_sum = cur_max = nums[0]
        min_sum = cur_min = nums[0]
        for x in nums[1:]:
            cur_max = max(x, cur_max + x)
            max_sum = max(max_sum, cur_max)
            cur_min = min(x, cur_min + x)
            min_sum = min(min_sum, cur_min)
        # If all negative, max_sum is the answer (total - min_sum would be 0)
        return max(max_sum, total - min_sum) if max_sum > 0 else max_sum


if __name__ == '__main__':
    s = Solution()
    assert s.maxSubarraySumCircular([1, -2, 3, -2]) == 3
    assert s.maxSubarraySumCircular([5, -3, 5]) == 10
    assert s.maxSubarraySumCircular([-3, -2, -3]) == -2
    print("All tests passed.")

from typing import List


class Solution:
    """
    ## 1899. Merge Triplets to Form Target Triplet

    A triplet is an array of three integers. You are given a 2D array triplets and a target triplet.
    You may choose any two triplets and update one of them to [max(a,x), max(b,y), max(c,z)].
    Return true if it is possible to obtain the target triplet as an element of triplets.

    ### Example
    ```text
    Input:  triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]
    Output: true  (merge [2,5,3] and [1,7,5] -> [2,7,5])

    Input:  triplets = [[3,4,5],[4,5,6]], target = [3,2,5]
    Output: false
    ```

    ### Constraints
    - 1 <= triplets.length <= 10^5
    - triplets[i].length == target.length == 3
    - 1 <= triplets[i][j], target[j] <= 1000
    """

    def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
        # Only consider triplets where no element exceeds the target
        # Check if the union (element-wise max) of valid triplets equals target
        # O(n) time, O(1) space — filter valid triplets and accumulate max
        result = [0, 0, 0]
        for t in triplets:
            # Skip triplets that exceed any target component
            if t[0] <= target[0] and t[1] <= target[1] and t[2] <= target[2]:
                result = [max(result[i], t[i]) for i in range(3)]
        return result == target


if __name__ == '__main__':
    s = Solution()
    assert s.mergeTriplets([[2, 5, 3], [1, 8, 4], [1, 7, 5]], [2, 7, 5]) == True
    assert s.mergeTriplets([[3, 4, 5], [4, 5, 6]], [3, 2, 5]) == False
    assert s.mergeTriplets([[2, 5, 3], [2, 3, 4], [1, 2, 5]], [2, 5, 5]) == True
    print("All tests passed.")

from typing import List


class Solution:
    """
    ## 763. Partition Labels

    You are given a string s. Partition it into as many parts as possible so that each letter
    appears in at most one part. Return a list of integers representing the size of each part.

    ### Example
    ```text
    Input:  s = "ababcbacadefegdehijhklij"
    Output: [9, 7, 8]
    (parts: "ababcbaca", "defegde", "hijhklij")

    Input:  s = "eccbbbbdec"
    Output: [10]
    ```

    ### Constraints
    - 1 <= s.length <= 500
    - s consists of lowercase English letters
    """

    def partitionLabels(self, s: str) -> List[int]:
        # Record last occurrence of each character
        # Extend current partition end to the last occurrence of each char seen
        # When current index reaches partition end, record partition size and start new one
        # O(n) time, O(1) space — record last occurrence of each character
        last = {c: i for i, c in enumerate(s)}
        result = []
        start = end = 0
        for i, c in enumerate(s):
            end = max(end, last[c])
            if i == end:
                result.append(end - start + 1)
                start = i + 1
        return result


if __name__ == '__main__':
    s = Solution()
    assert s.partitionLabels("ababcbacadefegdehijhklij") == [9, 7, 8]
    assert s.partitionLabels("eccbbbbdec") == [10]
    assert s.partitionLabels("a") == [1]
    print("All tests passed.")

class Solution:
    """
    ## 678. Valid Parenthesis String

    Given a string s containing '(', ')', and '*', return true if s is valid.
    '*' can be treated as '(', ')', or an empty string.

    ### Example
    ```text
    Input:  s = "(*)"
    Output: true

    Input:  s = "(*))"
    Output: true

    Input:  s = "(*())"
    Output: true
    ```

    ### Constraints
    - 1 <= s.length <= 100
    - s[i] is '(', ')' or '*'
    """

    def checkValidString_two_pass(self, s: str) -> bool:
        # O(n) time, O(1) space — two-pass left-to-right and right-to-left
        # Left pass: treat '*' as '('
        opens = 0
        for c in s:
            opens += 1 if c != ')' else -1
            if opens < 0:
                return False
        # Right pass: treat '*' as ')'
        closes = 0
        for c in reversed(s):
            closes += 1 if c != '(' else -1
            if closes < 0:
                return False
        return True

    def checkValidString(self, s: str) -> bool:
        # Track range [lo, hi] of possible open-paren counts
        # '(' increases both, ')' decreases both, '*' widens range by ±1
        # Valid if hi >= 0 throughout and lo == 0 at end
        # O(n) time, O(1) space — track range [lo, hi] of possible open counts
        lo = hi = 0
        for c in s:
            if c == '(':
                lo += 1; hi += 1
            elif c == ')':
                lo -= 1; hi -= 1
            else:  # '*'
                lo -= 1; hi += 1
            if hi < 0:
                return False
            lo = max(lo, 0)
        return lo == 0


if __name__ == '__main__':
    s = Solution()
    assert s.checkValidString("(*)") == True
    assert s.checkValidString("(*))") == True
    assert s.checkValidString("(*()") == True
    assert s.checkValidString(")(") == False
    assert s.checkValidString_two_pass("(*)") == True
    assert s.checkValidString_two_pass("(*))") == True
    print("All tests passed.")