1def majorityElement(nums: list[int]) -> int:
 2    # Boyer-Moore Voting Algorithm - O(n) time, O(1) space
 3    candidate = None
 4    count = 0
 5
 6    for num in nums:
 7        if count == 0:
 8            candidate = num
 9        count += 1 if num == candidate else -1
10
11    return candidate

 1def majorityElement(nums: list[int]) -> list[int]:
 2    # Boyer-Moore extended - O(n) time, O(1) space
 3    candidate1, candidate2 = None, None
 4    count1, count2 = 0, 0
 5
 6    for num in nums:
 7        if num == candidate1:
 8            count1 += 1
 9        elif num == candidate2:
10            count2 += 1
11        elif count1 == 0:
12            candidate1, count1 = num, 1
13        elif count2 == 0:
14            candidate2, count2 = num, 1
15        else:
16            count1 -= 1
17            count2 -= 1
18
19    # Verify candidates
20    result = []
21    for c in [candidate1, candidate2]:
22        if nums.count(c) > len(nums) // 3:
23            result.append(c)
24    return result

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

 1def findDuplicates(nums: list[int]) -> list[int]:
 2    # Mark visited by negating - O(n) time, O(1) space
 3    result = []
 4
 5    for num in nums:
 6        idx = abs(num) - 1
 7        if nums[idx] < 0:
 8            result.append(abs(num))
 9        else:
10            nums[idx] = -nums[idx]
11
12    return result

1def findDisappearedNumbers(nums: list[int]) -> list[int]:
2    # Mark visited by negating - O(n) time, O(1) space
3    for num in nums:
4        idx = abs(num) - 1
5        nums[idx] = -abs(nums[idx])
6
7    return [i + 1 for i in range(len(nums)) if nums[i] > 0]

 1def findErrorNums(nums: list[int]) -> list[int]:
 2    # Math approach - O(n) time, O(1) space
 3    n = len(nums)
 4    actual_sum = sum(nums)
 5    actual_sq_sum = sum(x * x for x in nums)
 6    expected_sum = n * (n + 1) // 2
 7    expected_sq_sum = n * (n + 1) * (2 * n + 1) // 6
 8
 9    diff = expected_sum - actual_sum  # missing - duplicate
10    sq_diff = expected_sq_sum - actual_sq_sum  # missing^2 - duplicate^2
11
12    sum_both = sq_diff // diff  # missing + duplicate
13    missing = (diff + sum_both) // 2
14    duplicate = sum_both - missing
15
16    return [duplicate, missing]

 1def hIndex(citations: list[int]) -> int:
 2    # Counting sort - O(n) time, O(n) space
 3    n = len(citations)
 4    counts = [0] * (n + 1)
 5
 6    for c in citations:
 7        counts[min(c, n)] += 1
 8
 9    total = 0
10    for i in range(n, -1, -1):
11        total += counts[i]
12        if total >= i:
13            return i
14
15    return 0

 1import random
 2
 3class RandomizedSet:
 4    def __init__(self):
 5        self.val_to_idx = {}
 6        self.vals = []
 7
 8    def insert(self, val: int) -> bool:
 9        if val in self.val_to_idx:
10            return False
11        self.val_to_idx[val] = len(self.vals)
12        self.vals.append(val)
13        return True
14
15    def remove(self, val: int) -> bool:
16        if val not in self.val_to_idx:
17            return False
18        idx = self.val_to_idx[val]
19        last_val = self.vals[-1]
20        self.vals[idx] = last_val
21        self.val_to_idx[last_val] = idx
22        self.vals.pop()
23        del self.val_to_idx[val]
24        return True
25
26    def getRandom(self) -> int:
27        return random.choice(self.vals)

1def fourSumCount(nums1: list[int], nums2: list[int], nums3: list[int], nums4: list[int]) -> int:
2    # Hash map - O(n^2) time, O(n^2) space
3    from collections import Counter
4
5    sum_ab = Counter(a + b for a in nums1 for b in nums2)
6    return sum(sum_ab[-(c + d)] for c in nums3 for d in nums4)

 1def increasingTriplet(nums: list[int]) -> bool:
 2    # Track two smallest - O(n) time, O(1) space
 3    first = second = float('inf')
 4
 5    for num in nums:
 6        if num <= first:
 7            first = num
 8        elif num <= second:
 9            second = num
10        else:
11            return True
12
13    return False

 1def isSubsequence(s: str, t: str) -> bool:
 2    # Two pointers - O(n) time, O(1) space
 3    i, j = 0, 0
 4
 5    while i < len(s) and j < len(t):
 6        if s[i] == t[j]:
 7            i += 1
 8        j += 1
 9
10    return i == len(s)

 1def validPalindrome(s: str) -> bool:
 2    # Two pointers with one skip - O(n) time, O(1) space
 3    def is_palindrome(left, right):
 4        while left < right:
 5            if s[left] != s[right]:
 6                return False
 7            left += 1
 8            right -= 1
 9        return True
10
11    left, right = 0, len(s) - 1
12    while left < right:
13        if s[left] != s[right]:
14            return is_palindrome(left + 1, right) or is_palindrome(left, right - 1)
15        left += 1
16        right -= 1
17
18    return True

 1def threeSumClosest(nums: list[int], target: int) -> int:
 2    # Sort + Two pointers - O(n^2) time, O(1) space
 3    nums.sort()
 4    closest = float('inf')
 5
 6    for i in range(len(nums) - 2):
 7        left, right = i + 1, len(nums) - 1
 8
 9        while left < right:
10            total = nums[i] + nums[left] + nums[right]
11
12            if abs(total - target) < abs(closest - target):
13                closest = total
14
15            if total < target:
16                left += 1
17            elif total > target:
18                right -= 1
19            else:
20                return target
21
22    return closest

 1def fourSum(nums: list[int], target: int) -> list[list[int]]:
 2    # Sort + Two pointers - O(n^3) time, O(1) space
 3    nums.sort()
 4    result = []
 5    n = len(nums)
 6
 7    for i in range(n - 3):
 8        if i > 0 and nums[i] == nums[i - 1]:
 9            continue
10        for j in range(i + 1, n - 2):
11            if j > i + 1 and nums[j] == nums[j - 1]:
12                continue
13
14            left, right = j + 1, n - 1
15            while left < right:
16                total = nums[i] + nums[j] + nums[left] + nums[right]
17                if total == target:
18                    result.append([nums[i], nums[j], nums[left], nums[right]])
19                    while left < right and nums[left] == nums[left + 1]:
20                        left += 1
21                    while left < right and nums[right] == nums[right - 1]:
22                        right -= 1
23                    left += 1
24                    right -= 1
25                elif total < target:
26                    left += 1
27                else:
28                    right -= 1
29
30    return result

 1def sortColors(nums: list[int]) -> None:
 2    # Dutch National Flag - O(n) time, O(1) space
 3    low, mid, high = 0, 0, len(nums) - 1
 4
 5    while mid <= high:
 6        if nums[mid] == 0:
 7            nums[low], nums[mid] = nums[mid], nums[low]
 8            low += 1
 9            mid += 1
10        elif nums[mid] == 1:
11            mid += 1
12        else:
13            nums[mid], nums[high] = nums[high], nums[mid]
14            high -= 1

 1def backspaceCompare(s: str, t: str) -> bool:
 2    # Two pointers from end - O(n) time, O(1) space
 3    def next_valid_char(string, idx):
 4        skip = 0
 5        while idx >= 0:
 6            if string[idx] == '#':
 7                skip += 1
 8            elif skip > 0:
 9                skip -= 1
10            else:
11                break
12            idx -= 1
13        return idx
14
15    i, j = len(s) - 1, len(t) - 1
16
17    while i >= 0 or j >= 0:
18        i = next_valid_char(s, i)
19        j = next_valid_char(t, j)
20
21        if i >= 0 and j >= 0 and s[i] != t[j]:
22            return False
23        if (i >= 0) != (j >= 0):
24            return False
25
26        i -= 1
27        j -= 1
28
29    return True

 1def intervalIntersection(firstList: list[list[int]], secondList: list[list[int]]) -> list[list[int]]:
 2    # Two pointers - O(m+n) time, O(1) space
 3    result = []
 4    i, j = 0, 0
 5
 6    while i < len(firstList) and j < len(secondList):
 7        start = max(firstList[i][0], secondList[j][0])
 8        end = min(firstList[i][1], secondList[j][1])
 9
10        if start <= end:
11            result.append([start, end])
12
13        if firstList[i][1] < secondList[j][1]:
14            i += 1
15        else:
16            j += 1
17
18    return result

 1def judgeSquareSum(c: int) -> bool:
 2    # Two pointers - O(sqrt(c)) time, O(1) space
 3    import math
 4
 5    left, right = 0, int(math.sqrt(c))
 6
 7    while left <= right:
 8        total = left * left + right * right
 9        if total == c:
10            return True
11        elif total < c:
12            left += 1
13        else:
14            right -= 1
15
16    return False

 1def containsNearbyDuplicate(nums: list[int], k: int) -> bool:
 2    # Sliding window with set - O(n) time, O(k) space
 3    window = set()
 4
 5    for i, num in enumerate(nums):
 6        if num in window:
 7            return True
 8        window.add(num)
 9        if len(window) > k:
10            window.remove(nums[i - k])
11
12    return False

 1def findMaxAverage(nums: list[int], k: int) -> float:
 2    # Sliding window - O(n) time, O(1) space
 3    window_sum = sum(nums[:k])
 4    max_sum = window_sum
 5
 6    for i in range(k, len(nums)):
 7        window_sum += nums[i] - nums[i - k]
 8        max_sum = max(max_sum, window_sum)
 9
10    return max_sum / k

 1def longestOnes(nums: list[int], k: int) -> int:
 2    # Sliding window - O(n) time, O(1) space
 3    left = 0
 4    zeros = 0
 5    max_len = 0
 6
 7    for right in range(len(nums)):
 8        if nums[right] == 0:
 9            zeros += 1
10
11        while zeros > k:
12            if nums[left] == 0:
13                zeros -= 1
14            left += 1
15
16        max_len = max(max_len, right - left + 1)
17
18    return max_len

 1def equalSubstring(s: str, t: str, maxCost: int) -> int:
 2    # Sliding window - O(n) time, O(1) space
 3    left = 0
 4    current_cost = 0
 5    max_len = 0
 6
 7    for right in range(len(s)):
 8        current_cost += abs(ord(s[right]) - ord(t[right]))
 9
10        while current_cost > maxCost:
11            current_cost -= abs(ord(s[left]) - ord(t[left]))
12            left += 1
13
14        max_len = max(max_len, right - left + 1)
15
16    return max_len

 1def totalFruit(fruits: list[int]) -> int:
 2    # Sliding window with at most 2 types - O(n) time, O(1) space
 3    from collections import defaultdict
 4
 5    count = defaultdict(int)
 6    left = 0
 7    max_len = 0
 8
 9    for right in range(len(fruits)):
10        count[fruits[right]] += 1
11
12        while len(count) > 2:
13            count[fruits[left]] -= 1
14            if count[fruits[left]] == 0:
15                del count[fruits[left]]
16            left += 1
17
18        max_len = max(max_len, right - left + 1)
19
20    return max_len

 1def maxSatisfied(customers: list[int], grumpy: list[int], minutes: int) -> int:
 2    # Sliding window - O(n) time, O(1) space
 3    base_satisfaction = sum(c for c, g in zip(customers, grumpy) if g == 0)
 4
 5    # Find max additional satisfaction in window
 6    window_extra = sum(customers[i] * grumpy[i] for i in range(minutes))
 7    max_extra = window_extra
 8
 9    for i in range(minutes, len(customers)):
10        window_extra += customers[i] * grumpy[i]
11        window_extra -= customers[i - minutes] * grumpy[i - minutes]
12        max_extra = max(max_extra, window_extra)
13
14    return base_satisfaction + max_extra

 1def maxScore(cardPoints: list[int], k: int) -> int:
 2    # Sliding window (min subarray) - O(n) time, O(1) space
 3    n = len(cardPoints)
 4    window_size = n - k
 5    total = sum(cardPoints)
 6
 7    if window_size == 0:
 8        return total
 9
10    window_sum = sum(cardPoints[:window_size])
11    min_sum = window_sum
12
13    for i in range(window_size, n):
14        window_sum += cardPoints[i] - cardPoints[i - window_size]
15        min_sum = min(min_sum, window_sum)
16
17    return total - min_sum

 1def nextGreaterElement(nums1: list[int], nums2: list[int]) -> list[int]:
 2    # Monotonic stack - O(n) time, O(n) space
 3    next_greater = {}
 4    stack = []
 5
 6    for num in nums2:
 7        while stack and stack[-1] < num:
 8            next_greater[stack.pop()] = num
 9        stack.append(num)
10
11    return [next_greater.get(num, -1) for num in nums1]

 1def nextGreaterElements(nums: list[int]) -> list[int]:
 2    # Monotonic stack with circular - O(n) time, O(n) space
 3    n = len(nums)
 4    result = [-1] * n
 5    stack = []
 6
 7    for i in range(2 * n):
 8        while stack and nums[stack[-1]] < nums[i % n]:
 9            result[stack.pop()] = nums[i % n]
10        if i < n:
11            stack.append(i)
12
13    return result

 1def largestRectangleArea(heights: list[int]) -> int:
 2    # Monotonic stack - O(n) time, O(n) space
 3    stack = [-1]
 4    max_area = 0
 5
 6    for i, h in enumerate(heights):
 7        while stack[-1] != -1 and heights[stack[-1]] >= h:
 8            height = heights[stack.pop()]
 9            width = i - stack[-1] - 1
10            max_area = max(max_area, height * width)
11        stack.append(i)
12
13    while stack[-1] != -1:
14        height = heights[stack.pop()]
15        width = len(heights) - stack[-1] - 1
16        max_area = max(max_area, height * width)
17
18    return max_area

 1def removeKdigits(num: str, k: int) -> str:
 2    # Monotonic stack - O(n) time, O(n) space
 3    stack = []
 4
 5    for digit in num:
 6        while k and stack and stack[-1] > digit:
 7            stack.pop()
 8            k -= 1
 9        stack.append(digit)
10
11    # Remove remaining k digits from end
12    stack = stack[:-k] if k else stack
13
14    return ''.join(stack).lstrip('0') or '0'

 1def find132pattern(nums: list[int]) -> bool:
 2    # Monotonic stack from right - O(n) time, O(n) space
 3    stack = []
 4    s3 = float('-inf')  # The middle element (s2 > s3)
 5
 6    for i in range(len(nums) - 1, -1, -1):
 7        if nums[i] < s3:
 8            return True
 9        while stack and stack[-1] < nums[i]:
10            s3 = stack.pop()
11        stack.append(nums[i])
12
13    return False

 1def validateStackSequences(pushed: list[int], popped: list[int]) -> bool:
 2    # Simulate stack - O(n) time, O(n) space
 3    stack = []
 4    j = 0
 5
 6    for num in pushed:
 7        stack.append(num)
 8        while stack and stack[-1] == popped[j]:
 9            stack.pop()
10            j += 1
11
12    return len(stack) == 0

 1def minRemoveToMakeValid(s: str) -> str:
 2    # Stack for indices - O(n) time, O(n) space
 3    to_remove = set()
 4    stack = []
 5
 6    for i, char in enumerate(s):
 7        if char == '(':
 8            stack.append(i)
 9        elif char == ')':
10            if stack:
11                stack.pop()
12            else:
13                to_remove.add(i)
14
15    to_remove.update(stack)
16    return ''.join(c for i, c in enumerate(s) if i not in to_remove)

 1def removeDuplicates(s: str) -> str:
 2    # Stack - O(n) time, O(n) space
 3    stack = []
 4
 5    for char in s:
 6        if stack and stack[-1] == char:
 7            stack.pop()
 8        else:
 9            stack.append(char)
10
11    return ''.join(stack)

 1def searchRange(nums: list[int], target: int) -> list[int]:
 2    # Two binary searches - O(log n) time, O(1) space
 3    def find_left():
 4        left, right = 0, len(nums) - 1
 5        while left <= right:
 6            mid = (left + right) // 2
 7            if nums[mid] < target:
 8                left = mid + 1
 9            else:
10                right = mid - 1
11        return left
12
13    def find_right():
14        left, right = 0, len(nums) - 1
15        while left <= right:
16            mid = (left + right) // 2
17            if nums[mid] <= target:
18                left = mid + 1
19            else:
20                right = mid - 1
21        return right
22
23    left_idx = find_left()
24    right_idx = find_right()
25
26    if left_idx <= right_idx:
27        return [left_idx, right_idx]
28    return [-1, -1]

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

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

 1def mySqrt(x: int) -> int:
 2    # Binary search - O(log x) time, O(1) space
 3    if x < 2:
 4        return x
 5
 6    left, right = 1, x // 2
 7
 8    while left <= right:
 9        mid = (left + right) // 2
10        if mid * mid == x:
11            return mid
12        elif mid * mid < x:
13            left = mid + 1
14        else:
15            right = mid - 1
16
17    return right

 1def isPerfectSquare(num: int) -> bool:
 2    # Binary search - O(log n) time, O(1) space
 3    left, right = 1, num
 4
 5    while left <= right:
 6        mid = (left + right) // 2
 7        square = mid * mid
 8        if square == num:
 9            return True
10        elif square < num:
11            left = mid + 1
12        else:
13            right = mid - 1
14
15    return False

 1def singleNonDuplicate(nums: list[int]) -> int:
 2    # Binary search - O(log n) time, O(1) space
 3    left, right = 0, len(nums) - 1
 4
 5    while left < right:
 6        mid = (left + right) // 2
 7        # Ensure mid is even for pair comparison
 8        if mid % 2 == 1:
 9            mid -= 1
10
11        if nums[mid] == nums[mid + 1]:
12            left = mid + 2
13        else:
14            right = mid
15
16    return nums[left]

 1def shipWithinDays(weights: list[int], days: int) -> int:
 2    # Binary search on capacity - O(n log sum) time, O(1) space
 3    def can_ship(capacity):
 4        current = 0
 5        required_days = 1
 6        for w in weights:
 7            if current + w > capacity:
 8                required_days += 1
 9                current = 0
10            current += w
11        return required_days <= days
12
13    left, right = max(weights), sum(weights)
14
15    while left < right:
16        mid = (left + right) // 2
17        if can_ship(mid):
18            right = mid
19        else:
20            left = mid + 1
21
22    return left

 1def findClosestElements(arr: list[int], k: int, x: int) -> list[int]:
 2    # Binary search for window start - O(log(n-k) + k) time
 3    left, right = 0, len(arr) - k
 4
 5    while left < right:
 6        mid = (left + right) // 2
 7        if x - arr[mid] > arr[mid + k] - x:
 8            left = mid + 1
 9        else:
10            right = mid
11
12    return arr[left:left + k]

 1def removeElements(head: ListNode, val: int) -> ListNode:
 2    # Dummy head - O(n) time, O(1) space
 3    dummy = ListNode(0, head)
 4    curr = dummy
 5
 6    while curr.next:
 7        if curr.next.val == val:
 8            curr.next = curr.next.next
 9        else:
10            curr = curr.next
11
12    return dummy.next

 1def deleteDuplicates(head: ListNode) -> ListNode:
 2    # Single pass - O(n) time, O(1) space
 3    curr = head
 4
 5    while curr and curr.next:
 6        if curr.val == curr.next.val:
 7            curr.next = curr.next.next
 8        else:
 9            curr = curr.next
10
11    return head

 1def deleteDuplicates(head: ListNode) -> ListNode:
 2    # Dummy head with prev pointer - O(n) time, O(1) space
 3    dummy = ListNode(0, head)
 4    prev = dummy
 5
 6    while head:
 7        if head.next and head.val == head.next.val:
 8            while head.next and head.val == head.next.val:
 9                head = head.next
10            prev.next = head.next
11        else:
12            prev = prev.next
13        head = head.next
14
15    return dummy.next

 1def swapPairs(head: ListNode) -> ListNode:
 2    # Iterative - O(n) time, O(1) space
 3    dummy = ListNode(0, head)
 4    prev = dummy
 5
 6    while prev.next and prev.next.next:
 7        first = prev.next
 8        second = prev.next.next
 9
10        prev.next = second
11        first.next = second.next
12        second.next = first
13
14        prev = first
15
16    return dummy.next

 1def rotateRight(head: ListNode, k: int) -> ListNode:
 2    # Find length and connect to circle - O(n) time, O(1) space
 3    if not head or not head.next or k == 0:
 4        return head
 5
 6    # Find length and last node
 7    length = 1
 8    tail = head
 9    while tail.next:
10        tail = tail.next
11        length += 1
12
13    k = k % length
14    if k == 0:
15        return head
16
17    # Find new tail (length - k - 1 steps from head)
18    new_tail = head
19    for _ in range(length - k - 1):
20        new_tail = new_tail.next
21
22    new_head = new_tail.next
23    new_tail.next = None
24    tail.next = head
25
26    return new_head

 1def partition(head: ListNode, x: int) -> ListNode:
 2    # Two dummy heads - O(n) time, O(1) space
 3    before = before_head = ListNode(0)
 4    after = after_head = ListNode(0)
 5
 6    while head:
 7        if head.val < x:
 8            before.next = head
 9            before = before.next
10        else:
11            after.next = head
12            after = after.next
13        head = head.next
14
15    after.next = None
16    before.next = after_head.next
17
18    return before_head.next

 1def reverseBetween(head: ListNode, left: int, right: int) -> ListNode:
 2    # Single pass - O(n) time, O(1) space
 3    if not head or left == right:
 4        return head
 5
 6    dummy = ListNode(0, head)
 7    prev = dummy
 8
 9    for _ in range(left - 1):
10        prev = prev.next
11
12    curr = prev.next
13    for _ in range(right - left):
14        next_node = curr.next
15        curr.next = next_node.next
16        next_node.next = prev.next
17        prev.next = next_node
18
19    return dummy.next

 1def oddEvenList(head: ListNode) -> ListNode:
 2    # Rearrange in place - O(n) time, O(1) space
 3    if not head:
 4        return head
 5
 6    odd = head
 7    even = head.next
 8    even_head = even
 9
10    while even and even.next:
11        odd.next = even.next
12        odd = odd.next
13        even.next = odd.next
14        even = even.next
15
16    odd.next = even_head
17    return head

 1def inorderTraversal(root: TreeNode) -> list[int]:
 2    # Iterative with stack - O(n) time, O(n) space
 3    result = []
 4    stack = []
 5    curr = root
 6
 7    while stack or curr:
 8        while curr:
 9            stack.append(curr)
10            curr = curr.left
11        curr = stack.pop()
12        result.append(curr.val)
13        curr = curr.right
14
15    return result

 1def preorderTraversal(root: TreeNode) -> list[int]:
 2    # Iterative with stack - O(n) time, O(n) space
 3    if not root:
 4        return []
 5
 6    result = []
 7    stack = [root]
 8
 9    while stack:
10        node = stack.pop()
11        result.append(node.val)
12        if node.right:
13            stack.append(node.right)
14        if node.left:
15            stack.append(node.left)
16
17    return result

 1def postorderTraversal(root: TreeNode) -> list[int]:
 2    # Iterative with two stacks - O(n) time, O(n) space
 3    if not root:
 4        return []
 5
 6    result = []
 7    stack = [root]
 8
 9    while stack:
10        node = stack.pop()
11        result.append(node.val)
12        if node.left:
13            stack.append(node.left)
14        if node.right:
15            stack.append(node.right)
16
17    return result[::-1]

 1def isSymmetric(root: TreeNode) -> bool:
 2    # Recursive - O(n) time, O(h) space
 3    def is_mirror(left, right):
 4        if not left and not right:
 5            return True
 6        if not left or not right:
 7            return False
 8        return (left.val == right.val and
 9                is_mirror(left.left, right.right) and
10                is_mirror(left.right, right.left))
11
12    return is_mirror(root, root)

 1def minDepth(root: TreeNode) -> int:
 2    # BFS - O(n) time, O(n) space
 3    if not root:
 4        return 0
 5
 6    from collections import deque
 7    queue = deque([(root, 1)])
 8
 9    while queue:
10        node, depth = queue.popleft()
11        if not node.left and not node.right:
12            return depth
13        if node.left:
14            queue.append((node.left, depth + 1))
15        if node.right:
16            queue.append((node.right, depth + 1))

 1def hasPathSum(root: TreeNode, targetSum: int) -> bool:
 2    # DFS - O(n) time, O(h) space
 3    if not root:
 4        return False
 5
 6    if not root.left and not root.right:
 7        return root.val == targetSum
 8
 9    remaining = targetSum - root.val
10    return hasPathSum(root.left, remaining) or hasPathSum(root.right, remaining)

 1def pathSum(root: TreeNode, targetSum: int) -> list[list[int]]:
 2    # DFS with backtracking - O(n^2) time, O(n) space
 3    result = []
 4
 5    def dfs(node, remaining, path):
 6        if not node:
 7            return
 8
 9        path.append(node.val)
10
11        if not node.left and not node.right and node.val == remaining:
12            result.append(path[:])
13        else:
14            dfs(node.left, remaining - node.val, path)
15            dfs(node.right, remaining - node.val, path)
16
17        path.pop()
18
19    dfs(root, targetSum, [])
20    return result

 1def sumNumbers(root: TreeNode) -> int:
 2    # DFS - O(n) time, O(h) space
 3    def dfs(node, current_sum):
 4        if not node:
 5            return 0
 6
 7        current_sum = current_sum * 10 + node.val
 8
 9        if not node.left and not node.right:
10            return current_sum
11
12        return dfs(node.left, current_sum) + dfs(node.right, current_sum)
13
14    return dfs(root, 0)

 1def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
 2    # Recursive - O(n) time, O(h) space
 3    if not root or root == p or root == q:
 4        return root
 5
 6    left = lowestCommonAncestor(root.left, p, q)
 7    right = lowestCommonAncestor(root.right, p, q)
 8
 9    if left and right:
10        return root
11    return left or right

 1def pathSum(root: TreeNode, targetSum: int) -> int:
 2    # Prefix sum with hash map - O(n) time, O(n) space
 3    from collections import defaultdict
 4
 5    def dfs(node, curr_sum):
 6        if not node:
 7            return 0
 8
 9        curr_sum += node.val
10        count = prefix_sums[curr_sum - targetSum]
11
12        prefix_sums[curr_sum] += 1
13        count += dfs(node.left, curr_sum)
14        count += dfs(node.right, curr_sum)
15        prefix_sums[curr_sum] -= 1
16
17        return count
18
19    prefix_sums = defaultdict(int)
20    prefix_sums[0] = 1
21    return dfs(root, 0)

1def topKFrequent(nums: list[int], k: int) -> list[int]:
2    # Heap - O(n log k) time, O(n) space
3    import heapq
4    from collections import Counter
5
6    count = Counter(nums)
7    return heapq.nlargest(k, count.keys(), key=count.get)

 1def topKFrequent(words: list[str], k: int) -> list[str]:
 2    # Heap with custom comparator - O(n log k) time
 3    import heapq
 4    from collections import Counter
 5
 6    count = Counter(words)
 7    # Use negative count for max heap, word for alphabetical order
 8    heap = [(-freq, word) for word, freq in count.items()]
 9    heapq.heapify(heap)
10
11    return [heapq.heappop(heap)[1] for _ in range(k)]

 1def kthSmallest(matrix: list[list[int]], k: int) -> int:
 2    # Min heap - O(k log n) time, O(n) space
 3    import heapq
 4
 5    n = len(matrix)
 6    heap = [(matrix[0][j], 0, j) for j in range(n)]
 7    heapq.heapify(heap)
 8
 9    for _ in range(k):
10        val, row, col = heapq.heappop(heap)
11        if row + 1 < n:
12            heapq.heappush(heap, (matrix[row + 1][col], row + 1, col))
13
14    return val

 1def reorganizeString(s: str) -> str:
 2    # Max heap - O(n log 26) time, O(26) space
 3    import heapq
 4    from collections import Counter
 5
 6    count = Counter(s)
 7    max_heap = [(-freq, char) for char, freq in count.items()]
 8    heapq.heapify(max_heap)
 9
10    result = []
11    prev_freq, prev_char = 0, ''
12
13    while max_heap:
14        freq, char = heapq.heappop(max_heap)
15        result.append(char)
16
17        if prev_freq < 0:
18            heapq.heappush(max_heap, (prev_freq, prev_char))
19
20        prev_freq, prev_char = freq + 1, char
21
22    return ''.join(result) if len(result) == len(s) else ''

 1def topKFrequent(nums: list[int], k: int) -> list[int]:
 2    # Quick select - O(n) average time, O(n) space
 3    from collections import Counter
 4
 5    count = Counter(nums)
 6    unique = list(count.keys())
 7
 8    def partition(left, right, pivot_idx):
 9        pivot_freq = count[unique[pivot_idx]]
10        unique[pivot_idx], unique[right] = unique[right], unique[pivot_idx]
11        store_idx = left
12
13        for i in range(left, right):
14            if count[unique[i]] < pivot_freq:
15                unique[store_idx], unique[i] = unique[i], unique[store_idx]
16                store_idx += 1
17
18        unique[right], unique[store_idx] = unique[store_idx], unique[right]
19        return store_idx
20
21    def quickselect(left, right, k_smallest):
22        if left == right:
23            return
24
25        import random
26        pivot_idx = random.randint(left, right)
27        pivot_idx = partition(left, right, pivot_idx)
28
29        if k_smallest == pivot_idx:
30            return
31        elif k_smallest < pivot_idx:
32            quickselect(left, pivot_idx - 1, k_smallest)
33        else:
34            quickselect(pivot_idx + 1, right, k_smallest)
35
36    n = len(unique)
37    quickselect(0, n - 1, n - k)
38    return unique[n - k:]

 1import heapq
 2
 3class MedianFinder:
 4    def __init__(self):
 5        self.small = []  # Max heap (negated)
 6        self.large = []  # Min heap
 7
 8    def addNum(self, num: int) -> None:
 9        # O(log n) time
10        heapq.heappush(self.small, -num)
11        heapq.heappush(self.large, -heapq.heappop(self.small))
12
13        if len(self.large) > len(self.small):
14            heapq.heappush(self.small, -heapq.heappop(self.large))
15
16    def findMedian(self) -> float:
17        # O(1) time
18        if len(self.small) > len(self.large):
19            return -self.small[0]
20        return (-self.small[0] + self.large[0]) / 2

 1def combine(n: int, k: int) -> list[list[int]]:
 2    # Backtracking - O(C(n,k) * k) time
 3    result = []
 4
 5    def backtrack(start, current):
 6        if len(current) == k:
 7            result.append(current[:])
 8            return
 9
10        for i in range(start, n + 1):
11            current.append(i)
12            backtrack(i + 1, current)
13            current.pop()
14
15    backtrack(1, [])
16    return result

 1def permuteUnique(nums: list[int]) -> list[list[int]]:
 2    # Backtracking with used array - O(n! * n) time
 3    nums.sort()
 4    result = []
 5    used = [False] * len(nums)
 6
 7    def backtrack(current):
 8        if len(current) == len(nums):
 9            result.append(current[:])
10            return
11
12        for i in range(len(nums)):
13            if used[i]:
14                continue
15            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
16                continue
17
18            used[i] = True
19            current.append(nums[i])
20            backtrack(current)
21            current.pop()
22            used[i] = False
23
24    backtrack([])
25    return result

 1def restoreIpAddresses(s: str) -> list[str]:
 2    # Backtracking - O(3^4) time
 3    result = []
 4
 5    def backtrack(start, parts):
 6        if len(parts) == 4:
 7            if start == len(s):
 8                result.append('.'.join(parts))
 9            return
10
11        for length in range(1, 4):
12            if start + length > len(s):
13                break
14
15            segment = s[start:start + length]
16            if (segment[0] == '0' and length > 1) or int(segment) > 255:
17                continue
18
19            backtrack(start + length, parts + [segment])
20
21    backtrack(0, [])
22    return result

 1def combinationSum3(k: int, n: int) -> list[list[int]]:
 2    # Backtracking - O(C(9,k) * k) time
 3    result = []
 4
 5    def backtrack(start, current, remaining):
 6        if len(current) == k:
 7            if remaining == 0:
 8                result.append(current[:])
 9            return
10
11        for i in range(start, 10):
12            if i > remaining:
13                break
14            current.append(i)
15            backtrack(i + 1, current, remaining - i)
16            current.pop()
17
18    backtrack(1, [], n)
19    return result

 1def letterCasePermutation(s: str) -> list[str]:
 2    # Backtracking - O(2^n * n) time
 3    result = []
 4
 5    def backtrack(idx, current):
 6        if idx == len(s):
 7            result.append(''.join(current))
 8            return
 9
10        if s[idx].isalpha():
11            current.append(s[idx].lower())
12            backtrack(idx + 1, current)
13            current.pop()
14
15            current.append(s[idx].upper())
16            backtrack(idx + 1, current)
17            current.pop()
18        else:
19            current.append(s[idx])
20            backtrack(idx + 1, current)
21            current.pop()
22
23    backtrack(0, [])
24    return result

 1def maxLength(arr: list[str]) -> int:
 2    # Backtracking with bitmask - O(2^n * m) time
 3    def has_unique(s):
 4        return len(s) == len(set(s))
 5
 6    result = [0]
 7
 8    def backtrack(idx, current):
 9        if has_unique(current):
10            result[0] = max(result[0], len(current))
11        else:
12            return
13
14        for i in range(idx, len(arr)):
15            backtrack(i + 1, current + arr[i])
16
17    backtrack(0, '')
18    return result[0]

 1def allPathsSourceTarget(graph: list[list[int]]) -> list[list[int]]:
 2    # DFS - O(2^n * n) time
 3    target = len(graph) - 1
 4    result = []
 5
 6    def dfs(node, path):
 7        if node == target:
 8            result.append(path[:])
 9            return
10
11        for neighbor in graph[node]:
12            path.append(neighbor)
13            dfs(neighbor, path)
14            path.pop()
15
16    dfs(0, [0])
17    return result

 1def canVisitAllRooms(rooms: list[list[int]]) -> bool:
 2    # DFS - O(n + e) time, O(n) space
 3    visited = set()
 4
 5    def dfs(room):
 6        visited.add(room)
 7        for key in rooms[room]:
 8            if key not in visited:
 9                dfs(key)
10
11    dfs(0)
12    return len(visited) == len(rooms)

 1def findCircleNum(isConnected: list[list[int]]) -> int:
 2    # Union-Find - O(n^2 * α(n)) time
 3    n = len(isConnected)
 4    parent = list(range(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            return True
16        return False
17
18    provinces = n
19    for i in range(n):
20        for j in range(i + 1, n):
21            if isConnected[i][j] == 1 and union(i, j):
22                provinces -= 1
23
24    return provinces

 1def eventualSafeNodes(graph: list[list[int]]) -> list[int]:
 2    # DFS with coloring - O(V + E) time
 3    n = len(graph)
 4    color = [0] * n  # 0: unvisited, 1: visiting, 2: safe
 5
 6    def dfs(node):
 7        if color[node] > 0:
 8            return color[node] == 2
 9
10        color[node] = 1
11        for neighbor in graph[node]:
12            if not dfs(neighbor):
13                return False
14
15        color[node] = 2
16        return True
17
18    return [i for i in range(n) if dfs(i)]

 1def criticalConnections(n: int, connections: list[list[int]]) -> list[list[int]]:
 2    # Tarjan's algorithm - O(V + E) time
 3    from collections import defaultdict
 4
 5    graph = defaultdict(list)
 6    for u, v in connections:
 7        graph[u].append(v)
 8        graph[v].append(u)
 9
10    disc = [0] * n
11    low = [0] * n
12    result = []
13    time = [1]
14
15    def dfs(node, parent):
16        disc[node] = low[node] = time[0]
17        time[0] += 1
18
19        for neighbor in graph[node]:
20            if neighbor == parent:
21                continue
22            if disc[neighbor] == 0:
23                dfs(neighbor, node)
24                low[node] = min(low[node], low[neighbor])
25                if low[neighbor] > disc[node]:
26                    result.append([node, neighbor])
27            else:
28                low[node] = min(low[node], disc[neighbor])
29
30    dfs(0, -1)
31    return result

 1def isBipartite(graph: list[list[int]]) -> bool:
 2    # BFS coloring - O(V + E) time
 3    from collections import deque
 4
 5    n = len(graph)
 6    color = [0] * n
 7
 8    for start in range(n):
 9        if color[start] != 0:
10            continue
11
12        queue = deque([start])
13        color[start] = 1
14
15        while queue:
16            node = queue.popleft()
17            for neighbor in graph[node]:
18                if color[neighbor] == 0:
19                    color[neighbor] = -color[node]
20                    queue.append(neighbor)
21                elif color[neighbor] == color[node]:
22                    return False
23
24    return True

 1def closedIsland(grid: list[list[int]]) -> int:
 2    # DFS - O(m*n) time
 3    rows, cols = len(grid), len(grid[0])
 4
 5    def dfs(r, c):
 6        if r < 0 or r >= rows or c < 0 or c >= cols:
 7            return False
 8        if grid[r][c] == 1:
 9            return True
10
11        grid[r][c] = 1
12        left = dfs(r, c - 1)
13        right = dfs(r, c + 1)
14        up = dfs(r - 1, c)
15        down = dfs(r + 1, c)
16
17        return left and right and up and down
18
19    count = 0
20    for r in range(rows):
21        for c in range(cols):
22            if grid[r][c] == 0 and dfs(r, c):
23                count += 1
24
25    return count

 1def minimumEffortPath(heights: list[list[int]]) -> int:
 2    # Dijkstra's algorithm - O(m*n log(m*n)) time
 3    import heapq
 4
 5    rows, cols = len(heights), len(heights[0])
 6    dist = [[float('inf')] * cols for _ in range(rows)]
 7    dist[0][0] = 0
 8    heap = [(0, 0, 0)]  # (effort, row, col)
 9
10    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
11
12    while heap:
13        effort, r, c = heapq.heappop(heap)
14
15        if r == rows - 1 and c == cols - 1:
16            return effort
17
18        if effort > dist[r][c]:
19            continue
20
21        for dr, dc in directions:
22            nr, nc = r + dr, c + dc
23            if 0 <= nr < rows and 0 <= nc < cols:
24                new_effort = max(effort, abs(heights[nr][nc] - heights[r][c]))
25                if new_effort < dist[nr][nc]:
26                    dist[nr][nc] = new_effort
27                    heapq.heappush(heap, (new_effort, nr, nc))
28
29    return 0

 1def fib(n: int) -> int:
 2    # DP - O(n) time, O(1) space
 3    if n <= 1:
 4        return n
 5
 6    prev2, prev1 = 0, 1
 7    for _ in range(2, n + 1):
 8        curr = prev1 + prev2
 9        prev2, prev1 = prev1, curr
10
11    return prev1

 1def tribonacci(n: int) -> int:
 2    # DP - O(n) time, O(1) space
 3    if n == 0:
 4        return 0
 5    if n <= 2:
 6        return 1
 7
 8    t0, t1, t2 = 0, 1, 1
 9    for _ in range(3, n + 1):
10        t0, t1, t2 = t1, t2, t0 + t1 + t2
11
12    return t2

 1def minPathSum(grid: list[list[int]]) -> int:
 2    # DP - O(m*n) time, O(n) space
 3    m, n = len(grid), len(grid[0])
 4    dp = [float('inf')] * (n + 1)
 5    dp[1] = 0
 6
 7    for i in range(m):
 8        for j in range(n):
 9            dp[j + 1] = min(dp[j], dp[j + 1]) + grid[i][j]
10
11    return dp[n]

1def minimumTotal(triangle: list[list[int]]) -> int:
2    # DP bottom-up - O(n^2) time, O(n) space
3    dp = triangle[-1][:]
4
5    for i in range(len(triangle) - 2, -1, -1):
6        for j in range(len(triangle[i])):
7            dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
8
9    return dp[0]

 1def numSquares(n: int) -> int:
 2    # DP - O(n * sqrt(n)) time, O(n) space
 3    dp = [float('inf')] * (n + 1)
 4    dp[0] = 0
 5
 6    for i in range(1, n + 1):
 7        j = 1
 8        while j * j <= i:
 9            dp[i] = min(dp[i], dp[i - j * j] + 1)
10            j += 1
11
12    return dp[n]