1def removeElement(nums: list[int], val: int) -> int:
2    # Two pointers - O(n) time, O(1) space
3    k = 0
4    for i in range(len(nums)):
5        if nums[i] != val:
6            nums[k] = nums[i]
7            k += 1
8    return k

1def generate(numRows: int) -> list[list[int]]:
2    # Build row by row - O(n^2) time, O(n^2) space
3    result = []
4    for i in range(numRows):
5        row = [1] * (i + 1)
6        for j in range(1, i):
7            row[j] = result[i - 1][j - 1] + result[i - 1][j]
8        result.append(row)
9    return result

1def getRow(rowIndex: int) -> list[int]:
2    # Build in place - O(n) time, O(n) space
3    row = [1] * (rowIndex + 1)
4    for i in range(2, rowIndex + 1):
5        for j in range(i - 1, 0, -1):
6            row[j] += row[j - 1]
7    return row

 1def rotate(nums: list[int], k: int) -> None:
 2    # Reverse approach - O(n) time, O(1) space
 3    n = len(nums)
 4    k = k % n
 5
 6    def reverse(start, end):
 7        while start < end:
 8            nums[start], nums[end] = nums[end], nums[start]
 9            start += 1
10            end -= 1
11
12    reverse(0, n - 1)
13    reverse(0, k - 1)
14    reverse(k, n - 1)

1def intersection(nums1: list[int], nums2: list[int]) -> list[int]:
2    # Set intersection - O(n + m) time, O(n + m) space
3    return list(set(nums1) & set(nums2))

 1def intersect(nums1: list[int], nums2: list[int]) -> list[int]:
 2    # Counter approach - O(n + m) time, O(min(n, m)) space
 3    from collections import Counter
 4
 5    count1 = Counter(nums1)
 6    result = []
 7
 8    for num in nums2:
 9        if count1[num] > 0:
10            result.append(num)
11            count1[num] -= 1
12
13    return result

 1def thirdMax(nums: list[int]) -> int:
 2    # Track top 3 - O(n) time, O(1) space
 3    first = second = third = float('-inf')
 4
 5    for num in nums:
 6        if num in (first, second, third):
 7            continue
 8        if num > first:
 9            first, second, third = num, first, second
10        elif num > second:
11            second, third = num, second
12        elif num > third:
13            third = num
14
15    return third if third != float('-inf') else first

 1def findMaxConsecutiveOnes(nums: list[int]) -> int:
 2    # Single pass - O(n) time, O(1) space
 3    max_count = 0
 4    current = 0
 5
 6    for num in nums:
 7        if num == 1:
 8            current += 1
 9            max_count = max(max_count, current)
10        else:
11            current = 0
12
13    return max_count

 1def matrixReshape(mat: list[list[int]], r: int, c: int) -> list[list[int]]:
 2    # Flatten and reshape - O(m*n) time, O(1) extra space
 3    m, n = len(mat), len(mat[0])
 4    if m * n != r * c:
 5        return mat
 6
 7    result = [[0] * c for _ in range(r)]
 8    for i in range(m * n):
 9        result[i // c][i % c] = mat[i // n][i % n]
10
11    return result

1def relativeSortArray(arr1: list[int], arr2: list[int]) -> list[int]:
2    # Custom sort - O(n log n) time, O(n) space
3    order = {num: i for i, num in enumerate(arr2)}
4    return sorted(arr1, key=lambda x: (order.get(x, len(arr2)), x))

1def reverseString(s: list[str]) -> None:
2    # Two pointers - O(n) time, O(1) space
3    left, right = 0, len(s) - 1
4    while left < right:
5        s[left], s[right] = s[right], s[left]
6        left += 1
7        right -= 1

 1def reverseVowels(s: str) -> str:
 2    # Two pointers - O(n) time, O(n) space
 3    vowels = set('aeiouAEIOU')
 4    s = list(s)
 5    left, right = 0, len(s) - 1
 6
 7    while left < right:
 8        while left < right and s[left] not in vowels:
 9            left += 1
10        while left < right and s[right] not in vowels:
11            right -= 1
12        s[left], s[right] = s[right], s[left]
13        left += 1
14        right -= 1
15
16    return ''.join(s)

1def reverseWords(s: str) -> str:
2    # Reverse each word - O(n) time, O(n) space
3    return ' '.join(word[::-1] for word in s.split())

 1def isLongPressedName(name: str, typed: str) -> bool:
 2    # Two pointers - O(n + m) time, O(1) space
 3    i = j = 0
 4
 5    while j < len(typed):
 6        if i < len(name) and name[i] == typed[j]:
 7            i += 1
 8        elif j > 0 and typed[j] == typed[j - 1]:
 9            pass
10        else:
11            return False
12        j += 1
13
14    return i == len(name)

 1def sortArrayByParity(nums: list[int]) -> list[int]:
 2    # Two pointers - O(n) time, O(1) space
 3    left, right = 0, len(nums) - 1
 4
 5    while left < right:
 6        if nums[left] % 2 > nums[right] % 2:
 7            nums[left], nums[right] = nums[right], nums[left]
 8        if nums[left] % 2 == 0:
 9            left += 1
10        if nums[right] % 2 == 1:
11            right -= 1
12
13    return nums

 1def sortArrayByParityII(nums: list[int]) -> list[int]:
 2    # Two pointers - O(n) time, O(1) space
 3    even, odd = 0, 1
 4    n = len(nums)
 5
 6    while even < n and odd < n:
 7        while even < n and nums[even] % 2 == 0:
 8            even += 2
 9        while odd < n and nums[odd] % 2 == 1:
10            odd += 2
11        if even < n and odd < n:
12            nums[even], nums[odd] = nums[odd], nums[even]
13
14    return nums

 1def reverseOnlyLetters(s: str) -> str:
 2    # Two pointers - O(n) time, O(n) space
 3    s = list(s)
 4    left, right = 0, len(s) - 1
 5
 6    while left < right:
 7        while left < right and not s[left].isalpha():
 8            left += 1
 9        while left < right and not s[right].isalpha():
10            right -= 1
11        s[left], s[right] = s[right], s[left]
12        left += 1
13        right -= 1
14
15    return ''.join(s)

 1def removeDuplicates(nums: list[int]) -> int:
 2    # Two pointers - O(n) time, O(1) space
 3    if len(nums) <= 2:
 4        return len(nums)
 5
 6    k = 2
 7    for i in range(2, len(nums)):
 8        if nums[i] != nums[k - 2]:
 9            nums[k] = nums[i]
10            k += 1
11
12    return k

 1def numOfSubarrays(arr: list[int], k: int, threshold: int) -> int:
 2    # Sliding window - O(n) time, O(1) space
 3    target = threshold * k
 4    window_sum = sum(arr[:k])
 5    count = 1 if window_sum >= target else 0
 6
 7    for i in range(k, len(arr)):
 8        window_sum += arr[i] - arr[i - k]
 9        if window_sum >= target:
10            count += 1
11
12    return count

 1def numKLenSubstrNoRepeats(s: str, k: int) -> int:
 2    # Sliding window - O(n) time, O(k) space
 3    if k > 26 or k > len(s):
 4        return 0
 5
 6    count = 0
 7    char_count = {}
 8
 9    for i in range(len(s)):
10        char_count[s[i]] = char_count.get(s[i], 0) + 1
11
12        if i >= k:
13            left_char = s[i - k]
14            char_count[left_char] -= 1
15            if char_count[left_char] == 0:
16                del char_count[left_char]
17
18        if i >= k - 1 and len(char_count) == k:
19            count += 1
20
21    return count

 1def minSwaps(data: list[int]) -> int:
 2    # Sliding window - O(n) time, O(1) space
 3    total_ones = sum(data)
 4    if total_ones == 0:
 5        return 0
 6
 7    window_ones = sum(data[:total_ones])
 8    max_ones = window_ones
 9
10    for i in range(total_ones, len(data)):
11        window_ones += data[i] - data[i - total_ones]
12        max_ones = max(max_ones, window_ones)
13
14    return total_ones - max_ones

 1def dietPlanPerformance(calories: list[int], k: int, lower: int, upper: int) -> int:
 2    # Sliding window - O(n) time, O(1) space
 3    points = 0
 4    window_sum = sum(calories[:k])
 5
 6    if window_sum < lower:
 7        points -= 1
 8    elif window_sum > upper:
 9        points += 1
10
11    for i in range(k, len(calories)):
12        window_sum += calories[i] - calories[i - k]
13        if window_sum < lower:
14            points -= 1
15        elif window_sum > upper:
16            points += 1
17
18    return points

 1def decrypt(code: list[int], k: int) -> list[int]:
 2    # Sliding window - O(n) time, O(n) space
 3    n = len(code)
 4    result = [0] * n
 5
 6    if k == 0:
 7        return result
 8
 9    start = 1 if k > 0 else n + k
10    end = k if k > 0 else n - 1
11
12    window_sum = sum(code[start:end + 1])
13
14    for i in range(n):
15        result[i] = window_sum
16        window_sum -= code[start % n]
17        start += 1
18        end += 1
19        window_sum += code[end % n]
20
21    return result

 1def minimumDifference(nums: list[int], k: int) -> int:
 2    # Sort + Sliding window - O(n log n) time, O(1) space
 3    if k == 1:
 4        return 0
 5
 6    nums.sort()
 7    min_diff = float('inf')
 8
 9    for i in range(len(nums) - k + 1):
10        min_diff = min(min_diff, nums[i + k - 1] - nums[i])
11
12    return min_diff

 1def divisorSubstrings(num: int, k: int) -> int:
 2    # Sliding window on string - O(n) time, O(n) space
 3    s = str(num)
 4    count = 0
 5
 6    for i in range(len(s) - k + 1):
 7        sub = int(s[i:i + k])
 8        if sub != 0 and num % sub == 0:
 9            count += 1
10
11    return count

 1from collections import deque
 2
 3class MyStack:
 4    def __init__(self):
 5        self.queue = deque()
 6
 7    def push(self, x: int) -> None:
 8        # O(n) push
 9        self.queue.append(x)
10        for _ in range(len(self.queue) - 1):
11            self.queue.append(self.queue.popleft())
12
13    def pop(self) -> int:
14        return self.queue.popleft()
15
16    def top(self) -> int:
17        return self.queue[0]
18
19    def empty(self) -> bool:
20        return len(self.queue) == 0

 1class MyQueue:
 2    def __init__(self):
 3        self.in_stack = []
 4        self.out_stack = []
 5
 6    def push(self, x: int) -> None:
 7        self.in_stack.append(x)
 8
 9    def pop(self) -> int:
10        self._transfer()
11        return self.out_stack.pop()
12
13    def peek(self) -> int:
14        self._transfer()
15        return self.out_stack[-1]
16
17    def empty(self) -> bool:
18        return not self.in_stack and not self.out_stack
19
20    def _transfer(self):
21        if not self.out_stack:
22            while self.in_stack:
23                self.out_stack.append(self.in_stack.pop())

 1def calPoints(operations: list[str]) -> int:
 2    # Stack - O(n) time, O(n) space
 3    stack = []
 4
 5    for op in operations:
 6        if op == '+':
 7            stack.append(stack[-1] + stack[-2])
 8        elif op == 'D':
 9            stack.append(stack[-1] * 2)
10        elif op == 'C':
11            stack.pop()
12        else:
13            stack.append(int(op))
14
15    return sum(stack)

 1def removeOuterParentheses(s: str) -> str:
 2    # Counter approach - O(n) time, O(n) space
 3    result = []
 4    depth = 0
 5
 6    for char in s:
 7        if char == '(':
 8            if depth > 0:
 9                result.append(char)
10            depth += 1
11        else:
12            depth -= 1
13            if depth > 0:
14                result.append(char)
15
16    return ''.join(result)

 1def buildArray(target: list[int], n: int) -> list[str]:
 2    # Simulation - O(n) time, O(n) space
 3    result = []
 4    target_set = set(target)
 5    max_val = target[-1]
 6
 7    for i in range(1, max_val + 1):
 8        result.append("Push")
 9        if i not in target_set:
10            result.append("Pop")
11
12    return result

 1def finalPrices(prices: list[int]) -> list[int]:
 2    # Monotonic stack - O(n) time, O(n) space
 3    result = prices[:]
 4    stack = []
 5
 6    for i, price in enumerate(prices):
 7        while stack and prices[stack[-1]] >= price:
 8            result[stack.pop()] -= price
 9        stack.append(i)
10
11    return result

 1def maxDepth(s: str) -> int:
 2    # Counter - O(n) time, O(1) space
 3    max_depth = 0
 4    current = 0
 5
 6    for char in s:
 7        if char == '(':
 8            current += 1
 9            max_depth = max(max_depth, current)
10        elif char == ')':
11            current -= 1
12
13    return max_depth

 1def minLength(s: str) -> int:
 2    # Stack - O(n) time, O(n) space
 3    stack = []
 4
 5    for char in s:
 6        if stack and ((stack[-1] == 'A' and char == 'B') or
 7                      (stack[-1] == 'C' and char == 'D')):
 8            stack.pop()
 9        else:
10            stack.append(char)
11
12    return len(stack)

 1def guessNumber(n: int) -> int:
 2    # Binary search - O(log n) time, O(1) space
 3    # guess(num) API returns: -1 if my number is lower, 1 if higher, 0 if correct
 4    left, right = 1, n
 5
 6    while left <= right:
 7        mid = (left + right) // 2
 8        result = guess(mid)
 9        if result == 0:
10            return mid
11        elif result == -1:
12            right = mid - 1
13        else:
14            left = mid + 1
15
16    return -1

 1def nextGreatestLetter(letters: list[str], target: str) -> str:
 2    # Binary search - O(log n) time, O(1) space
 3    left, right = 0, len(letters)
 4
 5    while left < right:
 6        mid = (left + right) // 2
 7        if letters[mid] <= target:
 8            left = mid + 1
 9        else:
10            right = mid
11
12    return letters[left % len(letters)]

 1def findKthPositive(arr: list[int], k: int) -> int:
 2    # Binary search - O(log n) time, O(1) space
 3    left, right = 0, len(arr)
 4
 5    while left < right:
 6        mid = (left + right) // 2
 7        # Missing count at index mid = arr[mid] - (mid + 1)
 8        if arr[mid] - mid - 1 < k:
 9            left = mid + 1
10        else:
11            right = mid
12
13    return left + k

 1def countNegatives(grid: list[list[int]]) -> int:
 2    # Staircase approach - O(m + n) time, O(1) space
 3    m, n = len(grid), len(grid[0])
 4    count = 0
 5    row, col = 0, n - 1
 6
 7    while row < m and col >= 0:
 8        if grid[row][col] < 0:
 9            count += m - row
10            col -= 1
11        else:
12            row += 1
13
14    return count

1def targetIndices(nums: list[int], target: int) -> list[int]:
2    # Count approach - O(n) time, O(1) space
3    less_than = sum(1 for x in nums if x < target)
4    equal = sum(1 for x in nums if x == target)
5    return list(range(less_than, less_than + equal))

1def maximumCount(nums: list[int]) -> int:
2    # Binary search - O(log n) time, O(1) space
3    from bisect import bisect_left, bisect_right
4
5    neg_count = bisect_left(nums, 0)
6    pos_count = len(nums) - bisect_right(nums, 0)
7
8    return max(neg_count, pos_count)

 1def splitArray(nums: list[int], k: int) -> int:
 2    # Binary search on answer - O(n log sum) time, O(1) space
 3    def can_split(max_sum):
 4        count = 1
 5        current = 0
 6        for num in nums:
 7            if current + num > max_sum:
 8                count += 1
 9                current = num
10            else:
11                current += num
12        return count <= k
13
14    left, right = max(nums), sum(nums)
15
16    while left < right:
17        mid = (left + right) // 2
18        if can_split(mid):
19            right = mid
20        else:
21            left = mid + 1
22
23    return left

 1def smallestDivisor(nums: list[int], threshold: int) -> int:
 2    # Binary search on answer - O(n log max) time, O(1) space
 3    import math
 4
 5    def compute_sum(divisor):
 6        return sum(math.ceil(num / divisor) for num in nums)
 7
 8    left, right = 1, max(nums)
 9
10    while left < right:
11        mid = (left + right) // 2
12        if compute_sum(mid) <= threshold:
13            right = mid
14        else:
15            left = mid + 1
16
17    return left

1def deleteNode(node):
2    # Copy next value and skip - O(1) time, O(1) space
3    node.val = node.next.val
4    node.next = node.next.next

1def middleNode(head: ListNode) -> ListNode:
2    # Slow and fast pointers - O(n) time, O(1) space
3    slow = fast = head
4
5    while fast and fast.next:
6        slow = slow.next
7        fast = fast.next.next
8
9    return slow

1def getDecimalValue(head: ListNode) -> int:
2    # Bit manipulation - O(n) time, O(1) space
3    result = 0
4    while head:
5        result = (result << 1) | head.val
6        head = head.next
7    return result

 1def splitListToParts(head: ListNode, k: int) -> list[ListNode]:
 2    # Calculate sizes - O(n) time, O(k) space
 3    length = 0
 4    curr = head
 5    while curr:
 6        length += 1
 7        curr = curr.next
 8
 9    base_size = length // k
10    extra = length % k
11    result = []
12    curr = head
13
14    for i in range(k):
15        result.append(curr)
16        size = base_size + (1 if i < extra else 0)
17        for _ in range(size - 1):
18            if curr:
19                curr = curr.next
20        if curr:
21            next_head = curr.next
22            curr.next = None
23            curr = next_head
24
25    return result

 1def numComponents(head: ListNode, nums: list[int]) -> int:
 2    # Set lookup - O(n) time, O(n) space
 3    nums_set = set(nums)
 4    count = 0
 5    in_component = False
 6
 7    while head:
 8        if head.val in nums_set:
 9            if not in_component:
10                count += 1
11                in_component = True
12        else:
13            in_component = False
14        head = head.next
15
16    return count

 1def nextLargerNodes(head: ListNode) -> list[int]:
 2    # Monotonic stack - O(n) time, O(n) space
 3    values = []
 4    while head:
 5        values.append(head.val)
 6        head = head.next
 7
 8    result = [0] * len(values)
 9    stack = []
10
11    for i, val in enumerate(values):
12        while stack and values[stack[-1]] < val:
13            result[stack.pop()] = val
14        stack.append(i)
15
16    return result

 1def deleteMiddle(head: ListNode) -> ListNode:
 2    # Slow and fast pointers - O(n) time, O(1) space
 3    if not head.next:
 4        return None
 5
 6    slow = fast = head
 7    prev = None
 8
 9    while fast and fast.next:
10        prev = slow
11        slow = slow.next
12        fast = fast.next.next
13
14    prev.next = slow.next
15    return head

 1def pairSum(head: ListNode) -> int:
 2    # Find middle, reverse, compare - O(n) time, O(1) space
 3    # Find middle
 4    slow = fast = head
 5    while fast and fast.next:
 6        slow = slow.next
 7        fast = fast.next.next
 8
 9    # Reverse second half
10    prev = None
11    while slow:
12        next_node = slow.next
13        slow.next = prev
14        prev = slow
15        slow = next_node
16
17    # Compare pairs
18    max_sum = 0
19    first, second = head, prev
20    while second:
21        max_sum = max(max_sum, first.val + second.val)
22        first = first.next
23        second = second.next
24
25    return max_sum

 1def sortedArrayToBST(nums: list[int]) -> TreeNode:
 2    # Recursive - O(n) time, O(log n) space
 3    def build(left, right):
 4        if left > right:
 5            return None
 6        mid = (left + right) // 2
 7        node = TreeNode(nums[mid])
 8        node.left = build(left, mid - 1)
 9        node.right = build(mid + 1, right)
10        return node
11
12    return build(0, len(nums) - 1)

 1def binaryTreePaths(root: TreeNode) -> list[str]:
 2    # DFS - O(n) time, O(n) space
 3    result = []
 4
 5    def dfs(node, path):
 6        if not node:
 7            return
 8        path += str(node.val)
 9        if not node.left and not node.right:
10            result.append(path)
11        else:
12            dfs(node.left, path + "->")
13            dfs(node.right, path + "->")
14
15    dfs(root, "")
16    return result

 1def sumOfLeftLeaves(root: TreeNode) -> int:
 2    # DFS - O(n) time, O(h) space
 3    def dfs(node, is_left):
 4        if not node:
 5            return 0
 6        if not node.left and not node.right:
 7            return node.val if is_left else 0
 8        return dfs(node.left, True) + dfs(node.right, False)
 9
10    return dfs(root, False)

 1def findMode(root: TreeNode) -> list[int]:
 2    # Inorder traversal - O(n) time, O(n) space
 3    modes = []
 4    max_count = 0
 5    current_count = 0
 6    current_val = None
 7
 8    def inorder(node):
 9        nonlocal max_count, current_count, current_val, modes
10        if not node:
11            return
12
13        inorder(node.left)
14
15        if node.val == current_val:
16            current_count += 1
17        else:
18            current_val = node.val
19            current_count = 1
20
21        if current_count > max_count:
22            max_count = current_count
23            modes = [current_val]
24        elif current_count == max_count:
25            modes.append(current_val)
26
27        inorder(node.right)
28
29    inorder(root)
30    return modes

 1def getMinimumDifference(root: TreeNode) -> int:
 2    # Inorder traversal - O(n) time, O(h) space
 3    prev = None
 4    min_diff = float('inf')
 5
 6    def inorder(node):
 7        nonlocal prev, min_diff
 8        if not node:
 9            return
10
11        inorder(node.left)
12
13        if prev is not None:
14            min_diff = min(min_diff, node.val - prev)
15        prev = node.val
16
17        inorder(node.right)
18
19    inorder(root)
20    return min_diff

 1def mergeTrees(root1: TreeNode, root2: TreeNode) -> TreeNode:
 2    # Recursive merge - O(n) time, O(h) space
 3    if not root1:
 4        return root2
 5    if not root2:
 6        return root1
 7
 8    root1.val += root2.val
 9    root1.left = mergeTrees(root1.left, root2.left)
10    root1.right = mergeTrees(root1.right, root2.right)
11
12    return root1

 1def averageOfLevels(root: TreeNode) -> list[float]:
 2    # BFS - O(n) time, O(n) space
 3    from collections import deque
 4
 5    result = []
 6    queue = deque([root])
 7
 8    while queue:
 9        level_sum = 0
10        level_size = len(queue)
11
12        for _ in range(level_size):
13            node = queue.popleft()
14            level_sum += node.val
15            if node.left:
16                queue.append(node.left)
17            if node.right:
18                queue.append(node.right)
19
20        result.append(level_sum / level_size)
21
22    return result

 1def findTarget(root: TreeNode, k: int) -> bool:
 2    # HashSet - O(n) time, O(n) space
 3    seen = set()
 4
 5    def dfs(node):
 6        if not node:
 7            return False
 8        if k - node.val in seen:
 9            return True
10        seen.add(node.val)
11        return dfs(node.left) or dfs(node.right)
12
13    return dfs(root)

1def searchBST(root: TreeNode, val: int) -> TreeNode:
2    # Iterative - O(h) time, O(1) space
3    while root:
4        if root.val == val:
5            return root
6        root = root.left if val < root.val else root.right
7    return None

 1def leafSimilar(root1: TreeNode, root2: TreeNode) -> bool:
 2    # DFS - O(n + m) time, O(n + m) space
 3    def get_leaves(node):
 4        if not node:
 5            return []
 6        if not node.left and not node.right:
 7            return [node.val]
 8        return get_leaves(node.left) + get_leaves(node.right)
 9
10    return get_leaves(root1) == get_leaves(root2)

1def kWeakestRows(mat: list[list[int]], k: int) -> list[int]:
2    # Min heap - O(m log m) time, O(m) space
3    import heapq
4
5    strength = [(sum(row), i) for i, row in enumerate(mat)]
6    heapq.heapify(strength)
7
8    return [heapq.heappop(strength)[1] for _ in range(k)]

 1def findRelativeRanks(score: list[int]) -> list[str]:
 2    # Sort with indices - O(n log n) time, O(n) space
 3    sorted_indices = sorted(range(len(score)), key=lambda i: -score[i])
 4    result = [""] * len(score)
 5
 6    medals = ["Gold Medal", "Silver Medal", "Bronze Medal"]
 7
 8    for rank, idx in enumerate(sorted_indices):
 9        if rank < 3:
10            result[idx] = medals[rank]
11        else:
12            result[idx] = str(rank + 1)
13
14    return result

 1def minStoneSum(piles: list[int], k: int) -> int:
 2    # Max heap - O((n + k) log n) time, O(n) space
 3    import heapq
 4
 5    # Negate for max heap
 6    max_heap = [-p for p in piles]
 7    heapq.heapify(max_heap)
 8
 9    for _ in range(k):
10        largest = -heapq.heappop(max_heap)
11        heapq.heappush(max_heap, -(largest - largest // 2))
12
13    return -sum(max_heap)

 1def halveArray(nums: list[int]) -> int:
 2    # Max heap - O(n log n) time, O(n) space
 3    import heapq
 4
 5    total = sum(nums)
 6    target = total / 2
 7    max_heap = [-num for num in nums]
 8    heapq.heapify(max_heap)
 9
10    operations = 0
11    current_sum = total
12
13    while current_sum > target:
14        largest = -heapq.heappop(max_heap)
15        half = largest / 2
16        current_sum -= half
17        heapq.heappush(max_heap, -half)
18        operations += 1
19
20    return operations

 1def totalCost(costs: list[int], k: int, candidates: int) -> int:
 2    # Two heaps - O(k log candidates) time
 3    import heapq
 4
 5    n = len(costs)
 6    left_heap = []
 7    right_heap = []
 8    left = 0
 9    right = n - 1
10    total = 0
11
12    # Initialize heaps
13    for _ in range(candidates):
14        if left <= right:
15            heapq.heappush(left_heap, (costs[left], left))
16            left += 1
17    for _ in range(candidates):
18        if left <= right:
19            heapq.heappush(right_heap, (costs[right], right))
20            right -= 1
21
22    for _ in range(k):
23        if not right_heap or (left_heap and left_heap[0] <= right_heap[0]):
24            cost, _ = heapq.heappop(left_heap)
25            total += cost
26            if left <= right:
27                heapq.heappush(left_heap, (costs[left], left))
28                left += 1
29        else:
30            cost, _ = heapq.heappop(right_heap)
31            total += cost
32            if left <= right:
33                heapq.heappush(right_heap, (costs[right], right))
34                right -= 1
35
36    return total

 1import heapq
 2
 3class SmallestInfiniteSet:
 4    def __init__(self):
 5        self.min_heap = []
 6        self.added_back = set()
 7        self.current = 1
 8
 9    def popSmallest(self) -> int:
10        if self.min_heap:
11            smallest = heapq.heappop(self.min_heap)
12            self.added_back.remove(smallest)
13            return smallest
14        smallest = self.current
15        self.current += 1
16        return smallest
17
18    def addBack(self, num: int) -> None:
19        if num < self.current and num not in self.added_back:
20            heapq.heappush(self.min_heap, num)
21            self.added_back.add(num)

 1def readBinaryWatch(turnedOn: int) -> list[str]:
 2    # Bit counting - O(12 * 60) time, O(1) space
 3    result = []
 4
 5    for h in range(12):
 6        for m in range(60):
 7            if bin(h).count('1') + bin(m).count('1') == turnedOn:
 8                result.append(f"{h}:{m:02d}")
 9
10    return result

 1class CombinationIterator:
 2    def __init__(self, characters: str, combinationLength: int):
 3        self.combinations = []
 4        self._generate(characters, combinationLength, 0, [])
 5        self.index = 0
 6
 7    def _generate(self, chars, length, start, current):
 8        if len(current) == length:
 9            self.combinations.append(''.join(current))
10            return
11        for i in range(start, len(chars)):
12            current.append(chars[i])
13            self._generate(chars, length, i + 1, current)
14            current.pop()
15
16    def next(self) -> str:
17        result = self.combinations[self.index]
18        self.index += 1
19        return result
20
21    def hasNext(self) -> bool:
22        return self.index < len(self.combinations)

1def findDifferentBinaryString(nums: list[str]) -> str:
2    # Cantor's diagonal - O(n) time, O(n) space
3    result = []
4    for i, num in enumerate(nums):
5        # Flip the i-th bit of the i-th number
6        result.append('0' if num[i] == '1' else '1')
7    return ''.join(result)

 1def getHappyString(n: int, k: int) -> str:
 2    # Backtracking - O(3 * 2^(n-1)) time
 3    result = []
 4
 5    def backtrack(current):
 6        if len(result) == k:
 7            return
 8        if len(current) == n:
 9            result.append(current)
10            return
11        for c in 'abc':
12            if not current or current[-1] != c:
13                backtrack(current + c)
14
15    backtrack('')
16    return result[k - 1] if len(result) >= k else ''

 1def countGoodNumbers(n: int) -> int:
 2    # Fast exponentiation - O(log n) time, O(1) space
 3    MOD = 10**9 + 7
 4
 5    def power(base, exp):
 6        result = 1
 7        while exp > 0:
 8            if exp % 2 == 1:
 9                result = (result * base) % MOD
10            base = (base * base) % MOD
11            exp //= 2
12        return result
13
14    even_positions = (n + 1) // 2  # 0, 2, 4, ...
15    odd_positions = n // 2  # 1, 3, 5, ...
16
17    return (power(5, even_positions) * power(4, odd_positions)) % MOD

 1def countMaxOrSubsets(nums: list[int]) -> int:
 2    # Backtracking - O(2^n) time, O(n) space
 3    max_or = 0
 4    for num in nums:
 5        max_or |= num
 6
 7    count = 0
 8
 9    def backtrack(idx, current_or):
10        nonlocal count
11        if idx == len(nums):
12            if current_or == max_or:
13                count += 1
14            return
15        # Include nums[idx]
16        backtrack(idx + 1, current_or | nums[idx])
17        # Exclude nums[idx]
18        backtrack(idx + 1, current_or)
19
20    backtrack(0, 0)
21    return count

 1def islandPerimeter(grid: list[list[int]]) -> int:
 2    # Count edges - O(m*n) time, O(1) space
 3    rows, cols = len(grid), len(grid[0])
 4    perimeter = 0
 5
 6    for r in range(rows):
 7        for c in range(cols):
 8            if grid[r][c] == 1:
 9                perimeter += 4
10                if r > 0 and grid[r - 1][c] == 1:
11                    perimeter -= 2
12                if c > 0 and grid[r][c - 1] == 1:
13                    perimeter -= 2
14
15    return perimeter

 1def floodFill(image: list[list[int]], sr: int, sc: int, color: int) -> list[list[int]]:
 2    # DFS - O(m*n) time, O(m*n) space
 3    if image[sr][sc] == color:
 4        return image
 5
 6    original = image[sr][sc]
 7    rows, cols = len(image), len(image[0])
 8
 9    def dfs(r, c):
10        if r < 0 or r >= rows or c < 0 or c >= cols:
11            return
12        if image[r][c] != original:
13            return
14        image[r][c] = color
15        dfs(r + 1, c)
16        dfs(r - 1, c)
17        dfs(r, c + 1)
18        dfs(r, c - 1)
19
20    dfs(sr, sc)
21    return image

 1def findJudge(n: int, trust: list[list[int]]) -> int:
 2    # In-degree and out-degree - O(n + e) time, O(n) space
 3    if n == 1 and not trust:
 4        return 1
 5
 6    trust_count = [0] * (n + 1)
 7
 8    for a, b in trust:
 9        trust_count[a] -= 1  # a trusts someone
10        trust_count[b] += 1  # b is trusted
11
12    for i in range(1, n + 1):
13        if trust_count[i] == n - 1:
14            return i
15
16    return -1

 1def shortestPathBinaryMatrix(grid: list[list[int]]) -> int:
 2    # BFS - O(n^2) time, O(n^2) space
 3    from collections import deque
 4
 5    n = len(grid)
 6    if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:
 7        return -1
 8
 9    directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1),
10                  (0, 1), (1, -1), (1, 0), (1, 1)]
11
12    queue = deque([(0, 0, 1)])
13    grid[0][0] = 1
14
15    while queue:
16        r, c, dist = queue.popleft()
17
18        if r == n - 1 and c == n - 1:
19            return dist
20
21        for dr, dc in directions:
22            nr, nc = r + dr, c + dc
23            if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
24                grid[nr][nc] = 1
25                queue.append((nr, nc, dist + 1))
26
27    return -1

 1def maxDistance(grid: list[list[int]]) -> int:
 2    # Multi-source BFS - O(n^2) time, O(n^2) space
 3    from collections import deque
 4
 5    n = len(grid)
 6    queue = deque()
 7
 8    for r in range(n):
 9        for c in range(n):
10            if grid[r][c] == 1:
11                queue.append((r, c))
12
13    if len(queue) == 0 or len(queue) == n * n:
14        return -1
15
16    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
17    distance = -1
18
19    while queue:
20        distance += 1
21        for _ in range(len(queue)):
22            r, c = queue.popleft()
23            for dr, dc in directions:
24                nr, nc = r + dr, c + dc
25                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
26                    grid[nr][nc] = 1
27                    queue.append((nr, nc))
28
29    return distance

 1def validPath(n: int, edges: list[list[int]], source: int, destination: int) -> bool:
 2    # Union-Find - O(n + e * α(n)) time, O(n) space
 3    parent = list(range(n))
 4
 5    def find(x):
 6        if parent[x] != x:
 7            parent[x] = find(parent[x])
 8        return parent[x]
 9
10    def union(x, y):
11        px, py = find(x), find(y)
12        if px != py:
13            parent[px] = py
14
15    for u, v in edges:
16        union(u, v)
17
18    return find(source) == find(destination)

 1def countPairs(n: int, edges: list[list[int]]) -> int:
 2    # Union-Find with sizes - O(n + e * α(n)) time, O(n) space
 3    parent = list(range(n))
 4    size = [1] * n
 5
 6    def find(x):
 7        if parent[x] != x:
 8            parent[x] = find(parent[x])
 9        return parent[x]
10
11    def union(x, y):
12        px, py = find(x), find(y)
13        if px != py:
14            parent[px] = py
15            size[py] += size[px]
16
17    for u, v in edges:
18        union(u, v)
19
20    # Count unreachable pairs
21    components = []
22    for i in range(n):
23        if find(i) == i:
24            components.append(size[i])
25
26    total = 0
27    running_sum = 0
28    for s in components:
29        total += running_sum * s
30        running_sum += s
31
32    return total

 1def maximumDetonation(bombs: list[list[int]]) -> int:
 2    # Build graph + DFS - O(n^2) time, O(n^2) space
 3    from collections import defaultdict
 4
 5    n = len(bombs)
 6    graph = defaultdict(list)
 7
 8    for i in range(n):
 9        for j in range(n):
10            if i != j:
11                xi, yi, ri = bombs[i]
12                xj, yj, _ = bombs[j]
13                dist_sq = (xi - xj) ** 2 + (yi - yj) ** 2
14                if dist_sq <= ri ** 2:
15                    graph[i].append(j)
16
17    def dfs(node, visited):
18        visited.add(node)
19        for neighbor in graph[node]:
20            if neighbor not in visited:
21                dfs(neighbor, visited)
22        return len(visited)
23
24    max_detonated = 0
25    for i in range(n):
26        max_detonated = max(max_detonated, dfs(i, set()))
27
28    return max_detonated

 1class NumArray:
 2    def __init__(self, nums: list[int]):
 3        # Prefix sum - O(n) time, O(n) space
 4        self.prefix = [0]
 5        for num in nums:
 6            self.prefix.append(self.prefix[-1] + num)
 7
 8    def sumRange(self, left: int, right: int) -> int:
 9        # O(1) time
10        return self.prefix[right + 1] - self.prefix[left]

 1def countSquares(matrix: list[list[int]]) -> int:
 2    # DP - O(m*n) time, O(1) space
 3    m, n = len(matrix), len(matrix[0])
 4    count = 0
 5
 6    for i in range(m):
 7        for j in range(n):
 8            if matrix[i][j] == 1:
 9                if i > 0 and j > 0:
10                    matrix[i][j] = min(matrix[i-1][j], matrix[i][j-1],
11                                       matrix[i-1][j-1]) + 1
12                count += matrix[i][j]
13
14    return count

 1def minFallingPathSum(matrix: list[list[int]]) -> int:
 2    # DP - O(n^2) time, O(1) space
 3    n = len(matrix)
 4
 5    for i in range(1, n):
 6        for j in range(n):
 7            left = matrix[i-1][j-1] if j > 0 else float('inf')
 8            mid = matrix[i-1][j]
 9            right = matrix[i-1][j+1] if j < n - 1 else float('inf')
10            matrix[i][j] += min(left, mid, right)
11
12    return min(matrix[n-1])

 1def mincostTickets(days: list[int], costs: list[int]) -> int:
 2    # DP - O(n) time, O(n) space
 3    day_set = set(days)
 4    last_day = days[-1]
 5    dp = [0] * (last_day + 1)
 6
 7    for i in range(1, last_day + 1):
 8        if i not in day_set:
 9            dp[i] = dp[i - 1]
10        else:
11            dp[i] = min(
12                dp[i - 1] + costs[0],
13                dp[max(0, i - 7)] + costs[1],
14                dp[max(0, i - 30)] + costs[2]
15            )
16
17    return dp[last_day]

 1def maxScoreSightseeingPair(values: list[int]) -> int:
 2    # DP - O(n) time, O(1) space
 3    max_score = 0
 4    max_i = values[0]  # values[i] + i
 5
 6    for j in range(1, len(values)):
 7        max_score = max(max_score, max_i + values[j] - j)
 8        max_i = max(max_i, values[j] + j)
 9
10    return max_score

 1def maxUncrossedLines(nums1: list[int], nums2: list[int]) -> int:
 2    # DP (LCS) - O(m*n) time, O(n) space
 3    m, n = len(nums1), len(nums2)
 4    dp = [0] * (n + 1)
 5
 6    for i in range(1, m + 1):
 7        prev = 0
 8        for j in range(1, n + 1):
 9            temp = dp[j]
10            if nums1[i-1] == nums2[j-1]:
11                dp[j] = prev + 1
12            else:
13                dp[j] = max(dp[j], dp[j-1])
14            prev = temp
15
16    return dp[n]

 1def lastStoneWeightII(stones: list[int]) -> int:
 2    # DP (subset sum) - O(n * sum) time, O(sum) space
 3    total = sum(stones)
 4    target = total // 2
 5    dp = [False] * (target + 1)
 6    dp[0] = True
 7
 8    for stone in stones:
 9        for j in range(target, stone - 1, -1):
10            dp[j] = dp[j] or dp[j - stone]
11
12    for j in range(target, -1, -1):
13        if dp[j]:
14            return total - 2 * j
15
16    return total

 1def countGoodStrings(low: int, high: int, zero: int, one: int) -> int:
 2    # DP - O(high) time, O(high) space
 3    MOD = 10**9 + 7
 4    dp = [0] * (high + 1)
 5    dp[0] = 1
 6
 7    for i in range(1, high + 1):
 8        if i >= zero:
 9            dp[i] = (dp[i] + dp[i - zero]) % MOD
10        if i >= one:
11            dp[i] = (dp[i] + dp[i - one]) % MOD
12
13    return sum(dp[low:high + 1]) % MOD

 1def canPlaceFlowers(flowerbed: list[int], n: int) -> bool:
 2    # Greedy - O(m) time, O(1) space
 3    count = 0
 4    length = len(flowerbed)
 5
 6    for i in range(length):
 7        if flowerbed[i] == 0:
 8            empty_left = (i == 0) or (flowerbed[i - 1] == 0)
 9            empty_right = (i == length - 1) or (flowerbed[i + 1] == 0)
10
11            if empty_left and empty_right:
12                flowerbed[i] = 1
13                count += 1
14                if count >= n:
15                    return True
16
17    return count >= n

 1def diStringMatch(s: str) -> list[int]:
 2    # Two pointers - O(n) time, O(n) space
 3    low, high = 0, len(s)
 4    result = []
 5
 6    for char in s:
 7        if char == 'I':
 8            result.append(low)
 9            low += 1
10        else:
11            result.append(high)
12            high -= 1
13
14    result.append(low)
15    return result

1def minCostToMoveChips(position: list[int]) -> int:
2    # Count odd and even - O(n) time, O(1) space
3    odd = sum(1 for p in position if p % 2 == 1)
4    even = len(position) - odd
5    return min(odd, even)

1def maximum69Number(num: int) -> int:
2    # Find first 6 and change - O(log n) time, O(log n) space
3    s = list(str(num))
4    for i in range(len(s)):
5        if s[i] == '6':
6            s[i] = '9'
7            break
8    return int(''.join(s))