class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        left = 0
        right = len(height) - 1
        left_max = right_max = 0
        total = 0
        while left < right:
            if height[left] < height[right]:
                if height[left] >= left_max:
                    left_max = height[left]
                else:
                    total += left_max - height[left]
                left += 1
            else:
                if height[right] >= right_max:
                    right_max = height[right]
                else:
                    total += right_max - height[right]
                right -= 1
        return total

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        r = len(nums)-1
        while r>=1:
            if nums[r] >nums[r-1]:
                if r+1<len(nums) and nums[r+1] >nums[r-1]:
                    k = 2
                    while (r+k<len(nums) and  nums[r+k] >nums[r-1]):
                        k+=1
                    k-=1
                    nums[r+k],nums[r-1]=nums[r-1],nums[r+k]
                else:
                    nums[r],nums[r-1]=nums[r-1],nums[r]
                break
            else:
                r -= 1
        l = len(nums)-1
        while l>r:
            if nums[l] <nums[r]:
                nums[l],nums[r] = nums[r],nums[l]
            l-=1
            r+=1

def threeSum(nums):
    res = []
    nums.sort()
    n = len(nums)
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # Skip duplicate elements for the first element of the triplet
        left, right = i + 1, n - 1
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            if current_sum == 0:
                res.append([nums[i], nums[left], nums[right]])
                # Skip duplicates for the second element
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                # Skip duplicates for the third element
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
            elif current_sum < 0:
                left += 1
            else:
                right -= 1
    return res 

Input: nums = [2, 7, 11, 15], target = 9  
Output: [0, 1]  
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].  

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]  
Output: 6  
Explanation: The subarray [4, -1, 2, 1] has the largest sum = 6.  

Input: s = "()[]{}"  
Output: true  

Input: s = "(]"  
Output: false  

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
}