Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true] 
Explanation: If you give all extraCandies to:
- Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids.
- Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
- Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids.
- Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids.
- Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids.

class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
        maxCandies = max(candies)
        return [candy + extraCandies >= maxCandies for candy in candies]

Input: nums = [1,4,2,5,3]
Output: 11
Explanation: There are 11 valid subarrays: [1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3].

class Solution:
    def validSubarrays(self, nums: List[int]) -> int:
        ans = 0
        st = []
        
        for i in range(len(nums)):
            while st and nums[i] < nums[st[-1]]:
                ans += (i - st.pop())
            st.append(i)
        
        while st:
            ans += (len(nums) - st.pop())
        
        return ans

Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: The cell (1, 1) is as far as possible from all the land with distance 2.

from collections import deque

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        visited = [row[:] for row in grid]
        q = deque()
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    q.append((i, j))
        
        distance = -1
        while q:
            qSize = len(q)
            for _ in range(qSize):
                landCell = q.popleft()
                for dir in directions:
                    x, y = landCell[0] + dir[0], landCell[1] + dir[1]
                    if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and visited[x][y] == 0:
                        visited[x][y] = 1
                        q.append((x, y))
            distance += 1
        
        return -1 if distance == 0 else distance

Input: s = "0.(52)", t = "0.5(25)"
Output: true
Explanation: Because "0.(52)" represents 0.52525252..., and "0.5(25)" represents 0.52525252525..... , the strings represent the same number.

from math import gcd

class Fraction:
    def __init__(self, n, d):
        g = gcd(n, d)
        self.n = n // g
        self.d = d // g

    def iadd(self, other):
        numerator = self.n * other.d + self.d * other.n
        denominator = self.d * other.d
        g = gcd(numerator, denominator)
        self.n = numerator // g
        self.d = denominator // g

class Solution:
    def isRationalEqual(self, S: str, T: str) -> bool:
        f1 = self.convert(S)
        f2 = self.convert(T)
        return f1.n == f2.n and f1.d == f2.d

    def convert(self, S: str) -> Fraction:
        state = 0
        ans = Fraction(0, 1)
        decimal_size = 0

        for part in S.split('.'):
            state += 1
            if not part:
                continue
            x = int(part)
            sz = len(part)

            if state == 1:
                ans.iadd(Fraction(x, 1))
            elif state == 2:
                ans.iadd(Fraction(x, 10 ** sz))
                decimal_size = sz
            else:
                denom = 10 ** decimal_size
                denom *= 10 ** sz - 1
                ans.iadd(Fraction(x, denom))
        return ans

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

class Solution:
    def countElements(self, arr: List[int]) -> int:
        def integerInArray(arr, target):
            for x in arr:
                if x == target:
                    return True
            return False
        
        count = 0
        for x in arr:
            if integerInArray(arr, x + 1):
                count += 1
        return count

Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def widthOfBinaryTree(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        max_width = 0
        queue = deque([(root, 0)])
        
        while queue:
            level_length = len(queue)
            _, first_pos = queue[0]
            for i in range(level_length):
                node, pos = queue.popleft()
                if node.left:
                    queue.append((node.left, 2 * pos))
                if node.right:
                    queue.append((node.right, 2 * pos + 1))
            max_width = max(max_width, pos - first_pos + 1)
        
        return max_width

Input: left = 10, right = 15
Output: 5

def countPrimeSetBits(left, right):
    def countBits(x):
        return bin(x).count('1')
    
    def isPrime(x):
        if x < 2:
            return False
        for i in range(2, int(x ** 0.5) + 1):
            if x % i == 0:
                return False
        return True
    
    count = 0
    for num in range(left, right + 1):
        if isPrime(countBits(num)):
            count += 1

Input: n = 3, k = 1
Output: [1,2,3]
Explanation: The [1,2,3] has three different positive integers ranging from 1 to 3, and the [1,1] has exactly 1 distinct integer: 1

def constructArray(n, k):
    answer = []
    left, right = 1, n
    
    for i in range(k + 1):
        if i % 2 == 0:
            answer.append(left)
            left += 1
        else:
            answer.append(right)
            right -= 1
    
    if k % 2 == 0:
        answer.extend(range(left, right + 1))
    else:
        answer.extend(range(right, left - 1, -1))
    
    return answer

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height) == 0:
            return 0
        ans = 0
        size = len(height)
        left_max, right_max = [0] * size, [0] * size
        left_max[0] = height[0]
        for i in range(1, size):
            left_max[i] = max(height[i], left_max[i - 1])
        right_max[size - 1] = height[size - 1]
        for i in range(size - 2, -1, -1):
            right_max[i] = max(height[i], right_max[i + 1])
        for i in range(1, size - 1):
            ans += min(left_max[i], right_max[i]) - height[i]
        return ans

Input: fruits = [1,2,1]
Output: 3

def totalFruit(fruits):
    from collections import defaultdict
    basket = defaultdict(int)
    left = 0
    max_fruits = 0

    for right in range(len(fruits)):
        basket[fruits[right]] += 1
        while len(basket) > 2:
            basket[fruits[left]] -= 1
            if basket[fruits[left]] == 0:
                del basket[fruits[left]]
            left += 1
        max_fruits = max(max_fruits, right - left + 1)

    return max_fruits

Input: n = 3, k = 2, row = 0, column = 0
Output: 0.06250
Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board.
From each of those positions, there are also two moves that will keep the knight on the board.
The total probability the knight stays on the board is 0.0625.

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        directions = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]
        dp = [[[0] * n for _ in range(n)] for _ in range(k + 1)]
        dp[0][row][column] = 1

        for moves in range(1, k + 1):
            for i in range(n):
                for j in range(n):
                    for direction in directions:
                        prevI, prevJ = i - direction[0], j - direction[1]
                        if 0 <= prevI < n and 0 <= prevJ < n:
                            dp[moves][i][j] += dp[moves - 1][prevI][prevJ] / 8

        return sum(map(sum, dp[k]))

Input: s = "adceb", p = "*a*b"  
Output: true  

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True
        
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 1]
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == s[i - 1] or p[j - 1] == '?':
                    dp[i][j] = dp[i - 1][j - 1]
                elif p[j - 1] == '*':
                    dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
        
        return dp[m][n]

Input: 
["Leaderboard","addScore","addScore","addScore","addScore","addScore","top","reset","reset","addScore","top"]
[[],[1,73],[2,56],[3,39],[4,51],[5,4],[1],[1],[2],[2,51],[3]]
Output: 
[null,null,null,null,null,null,73,null,null,null,141]

from collections import defaultdict

class Leaderboard:

    def __init__(self):
        self.scores = defaultdict(int)

    def addScore(self, playerId, score):
        self.scores[playerId] += score

    def top(self, K):
        return sum(sorted(self.scores.values(), reverse=True)[:K])

    def reset(self, playerId):
        self.scores[playerId] = 0

Input: list1 = [1,2,4], list2 = [1,3,4]  
Output: [1,1,2,3,4,4]  

class Solution:
    def mergeTwoLists(self, l1, l2):
        dummy = ListNode(0)
        cur = dummy
        
        while l1 and l2:
            if l1.val <= l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        
        cur.next = l1 or l2
        return dummy.next

Input: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Output: [8,12,6,10,10,10]
Explanation: The tree is shown above.
We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
equals 1 + 1 + 2 + 2 + 2 = 8.
Hence, answer[0] = 8, and so on.

class Solution:
    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
        import collections
        graph = collections.defaultdict(set)
        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)

        ans = [0] * N
        count = [1] * N

        def dfs(node=0, parent=None):
            for neighbor in graph[node]:
                if neighbor != parent:
                    dfs(neighbor, node)
                    count[node] += count[neighbor]
                    ans[node] += ans[neighbor] + count[neighbor]

        def dfs2(node=0, parent=None):
            for neighbor in graph[node]:
                if neighbor != parent:
                    ans[neighbor] = ans[node] - count[neighbor] + N - count[neighbor]
                    dfs2(neighbor, node)

        dfs()
        dfs2()

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        prefixMod = 0
        result = 0
        modGroups = [0] * k
        modGroups[0] = 1

        for num in nums:
            prefixMod = (prefixMod + num % k + k) % k
            result += modGroups[prefixMod]
            modGroups[prefixMod] += 1

        return result