import random

class RandomizedSet:
    def __init__(self):
        self.array = []  # For O(1) random access
        self.indices = {}  # Maps elements to their indices

    def insert(self, val: int) -> bool:
        if val in self.indices:
            return False  # Element already exists
        self.indices[val] = len(self.array)
        self.array.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.indices:
            return False  # Element does not exist
        index = self.indices[val]
        last_element = self.array[-1]
        
        # Swap and remove
        self.array[index] = last_element
        self.indices[last_element] = index
        self.array.pop()
        del self.indices[val]
        return True

    def getRandom(self) -> int:
        return random.choice(self.array)

randomizedSet = RandomizedSet()
print(randomizedSet.insert(1))  # True
print(randomizedSet.remove(2))  # False
print(randomizedSet.insert(2))  # True
print(randomizedSet.getRandom())  # Either 1 or 2
print(randomizedSet.remove(1))  # True
print(randomizedSet.insert(2))  # False
print(randomizedSet.getRandom())  # 2

def findWinners(matches):
    loss_counts = {}
    players = set()

    for winner, loser in matches:
        players.add(winner)
        players.add(loser)
        loss_counts[loser] = loss_counts.get(loser, 0) + 1

    zero_losses = sorted([player for player in players if loss_counts.get(player, 0) == 0])
    one_loss = sorted([player for player in players if loss_counts.get(player, 0) == 1])

    return [zero_losses, one_loss]

matches = [[1, 3], [2, 1], [4, 2], [5, 2]]
result = findWinners(matches)
print(result)  # Output: [[4, 5], [1, 3]]

def restoreString(s, indices):
    result = [''] * len(s)
    for i, idx in enumerate(indices):
        result[idx] = s[i]
    return ''.join(result)

s = "codeleet"
indices = [4, 5, 6, 7, 0, 2, 1, 3]
result = restoreString(s, indices)
print(result)  # Output: "leetcode"

def threeSum(nums):
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
    return result

people = {
    'Alice': 30,
    'Bob': 25,
    'Charlie': 35,
    'David': 20,
    'Eve': 28
}

{
    'David': 20,
    'Bob': 25,
    'Eve': 28,
    'Alice': 30,
    'Charlie': 35
}

def intToRoman(num: int) -> str:
    val_sym = [
        (1000, 'M'), (900, 'CM'), (500, 'D'), (400, 'CD'),
        (100, 'C'), (90, 'XC'), (50, 'L'), (40, 'XL'),
        (10, 'X'), (9, 'IX'), (5, 'V'), (4, 'IV'), (1, 'I')
    ]
    res = []
    for value, symbol in val_sym:
        while num >= value:
            res.append(symbol)
            num -= value
        if num == 0:
            break
    return ''.join(res)

def minWindow(s: str, t: str) -> str:
    if not t or not s:
        return ""

    dict_t = {}
    for char in t:
        dict_t[char] = dict_t.get(char, 0) + 1

    required = len(dict_t)
    formed = 0
    window_counts = {}

    left, right = 0, 0
    ans = float('inf'), None, None

    while right < len(s):
        character = s[right]
        window_counts[character] = window_counts.get(character, 0) + 1

        if character in dict_t and window_counts[character] == dict_t[character]:
            formed += 1

        while left <= right and formed == required:
            character = s[left]

            if right - left + 1 < ans[0]:
                ans = (right - left + 1, left, right)

            window_counts[character] -= 1
            if character in dict_t and window_counts[character] < dict_t[character]:
                formed -= 1

            left += 1

        right += 1

    return "" if ans[0] == float('inf') else s[ans[1]: ans[2] + 1]

def minimumAverageDifference(nums):
    n = len(nums)
    total_sum = sum(nums)  # Calculate the total sum of the array
    left_sum = 0           # Initialize left sum
    min_diff = float('inf')  # Initialize minimum difference to infinity
    min_index = -1         # Initialize minimum index

    for i in range(n):
        left_sum += nums[i]  # Update left sum with the current element
        
        # Calculate left average
        left_avg = left_sum // (i + 1)
        
        # Calculate right average
        if i < n - 1:
            right_avg = (total_sum - left_sum) // (n - i - 1)
        else:
            right_avg = 0  # If it's the last element, right average is 0
        
        # Calculate absolute difference
        diff = abs(left_avg - right_avg)

        # Update minimum difference and index if a new minimum is found
        if diff < min_diff:
            min_diff = diff
            min_index = i

    return min_index

# Example usage:
print(minimumAverageDifference([2, 5, 3, 9, 5, 3]))  # Output: 3
print(minimumAverageDifference([0]))                  # Output: 0

from collections import defaultdict

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        prefix_counts = defaultdict(int)
        prefix_counts[0] = 1  # Initialize with prefix sum 0 having remainder 0
        current_sum = 0
        result = 0
        
        for num in nums:
            current_sum += num
            mod = current_sum % k
            result += prefix_counts[mod]
            prefix_counts[mod] += 1
        
        return result

def minSubArrayLen(target, nums):
    n = len(nums)
    left = 0
    curr_sum = 0
    min_len = float('inf')
    
    for right in range(n):
        curr_sum += nums[right]
        while curr_sum >= target:
            min_len = min(min_len, right - left + 1)
            curr_sum -= nums[left]
            left += 1
    
    return min_len if min_len != float('inf') else 0

# Testing the sliding window approach:
print(minSubArrayLen(7, [2, 3, 1, 2, 4, 3]))  # Expected Output: 2
print(minSubArrayLen(4, [1, 4, 4]))           # Expected Output: 1
print(minSubArrayLen(11, [1, 1, 1, 1, 1, 1, 1, 1]))  # Expected Output: 0

def minSubArrayLenBinarySearch(target, nums):
    n = len(nums)
    # Build prefix sum array
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    
    min_len = float('inf')
    # Iterate over prefix sum array
    for i in range(n):
        bound = prefix[i] + target
        # Find the minimal j such that prefix[j] >= bound
        j = bisect.bisect_left(prefix, bound)
        if j <= n:
            min_len = min(min_len, j - i)
    
    return min_len if min_len != float('inf') else 0

# Testing the O(n log n) approach:
print(minSubArrayLenBinarySearch(7, [2, 3, 1, 2, 4, 3]))  # Expected Output: 2
print(minSubArrayLenBinarySearch(4, [1, 4, 4]))           # Expected Output: 1
print(minSubArrayLenBinarySearch(11, [1, 1, 1, 1, 1, 1, 1, 1]))  # Expected Output: 0

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        left = 0
        p = [0 for i in range(len(arr)+1)]
        p[1] = arr[0]
        for i in range(1,len(arr)):
            p[i+1] = p[i] +arr[i]
        total = 0
        for i in range(1,len(p)):
            l = 0
            while l<i:
                if (i-l)%2:
                    total +=  p[i]-p[l]
                l+=1
        return total

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        total = 0
        n = len(arr)
        for i, val in enumerate(arr):
            left = i + 1          # ways to choose start position
            right = n - i         # ways to choose end position
            # Count of odd-length subarrays that include arr[i]
            odd_count = ((left + 1) // 2) * ((right + 1) // 2) + (left // 2) * (right // 2)
            total += val * odd_count
        return total

solution = Solution()
print(solution.sumOddLengthSubarrays([1, 4, 2, 5, 3]))  # Output: 58
print(solution.sumOddLengthSubarrays([1, 2]))            # Output: 3