def two_sum(nums: List[int], target: int) -> List[int]:
    """
    Hash map pattern for O(1) complement lookup.
    Time: O(n), Space: O(n)
    """
    seen = {}  # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

def subarray_sum(nums: List[int], k: int) -> int:
    """
    Prefix sum + hash map for subarray sums.
    Time: O(n), Space: O(n)
    """
    prefix_sum = {0: 1}  # sum -> count
    curr_sum = count = 0
    
    for num in nums:
        curr_sum += num
        if curr_sum - k in prefix_sum:
            count += prefix_sum[curr_sum - k]
        prefix_sum[curr_sum] = prefix_sum.get(curr_sum, 0) + 1
    
    return count

def valid_palindrome(s: str) -> bool:
    """
    Opposite direction pointers.
    Time: O(n), Space: O(1)
    """
    left, right = 0, len(s) - 1
    
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    
    return True

def remove_duplicates(nums: List[int]) -> int:
    """
    Same direction pointers (fast/slow).
    Time: O(n), Space: O(1)
    """
    if not nums:
        return 0
    
    slow = 0  # position to write
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    
    return slow + 1

def three_sum(nums: List[int]) -> List[List[int]]:
    """
    Sort + two pointers for triplets.
    Time: O(n²), Space: O(1)
    """
    nums.sort()
    result = []
    
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue  # skip duplicates
        
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                result.append([nums[i], nums[left], nums[right]])
                # Skip duplicates
                while left < right and nums[left] == nums[left+1]:
                    left += 1
                while left < right and nums[right] == nums[right-1]:
                    right -= 1
                left += 1
                right -= 1
    
    return result

def max_consecutive_ones(nums: List[int], k: int) -> int:
    """
    Variable size sliding window.
    Time: O(n), Space: O(1)
    """
    left = max_len = zeros = 0
    
    for right in range(len(nums)):
        if nums[right] == 0:
            zeros += 1
        
        # Shrink window if invalid
        while zeros > k:
            if nums[left] == 0:
                zeros -= 1
            left += 1
        
        max_len = max(max_len, right - left + 1)
    
    return max_len

def min_window_substring(s: str, t: str) -> str:
    """
    Variable window with hash map tracking.
    Time: O(m+n), Space: O(k) where k = unique chars in t
    """
    if not s or not t:
        return ""
    
    target = Counter(t)
    required = len(target)  # unique chars needed
    formed = 0  # unique chars satisfied
    
    window_counts = {}
    left = 0
    min_len = float('inf')
    min_window = (0, 0)
    
    for right in range(len(s)):
        # Expand window
        char = s[right]
        window_counts[char] = window_counts.get(char, 0) + 1
        
        if char in target and window_counts[char] == target[char]:
            formed += 1
        
        # Contract window
        while left <= right and formed == required:
            # Update result
            if right - left + 1 < min_len:
                min_len = right - left + 1
                min_window = (left, right)
            
            # Remove left char
            char = s[left]
            window_counts[char] -= 1
            if char in target and window_counts[char] < target[char]:
                formed -= 1
            left += 1
    
    return "" if min_len == float('inf') else s[min_window[0]:min_window[1]+1]

def valid_parentheses(s: str) -> bool:
    """
    Stack for matching pairs.
    Time: O(n), Space: O(n)
    """
    stack = []
    pairs = {'(': ')', '{': '}', '[': ']'}
    
    for char in s:
        if char in pairs:  # opening bracket
            stack.append(char)
        elif not stack or pairs[stack.pop()] != char:
            return False
    
    return len(stack) == 0

def basic_calculator(s: str) -> int:
    """
    Stack for operators and operands.
    Time: O(n), Space: O(n)
    """
    stack = []
    num = 0
    operator = '+'
    
    for i, char in enumerate(s):
        if char.isdigit():
            num = num * 10 + int(char)
        
        if char in '+-*/' or i == len(s) - 1:
            if operator == '+':
                stack.append(num)
            elif operator == '-':
                stack.append(-num)
            elif operator == '*':
                stack.append(stack.pop() * num)
            elif operator == '/':
                stack.append(int(stack.pop() / num))
            
            operator = char
            num = 0
    
    return sum(stack)

def next_greater_element(nums: List[int]) -> List[int]:
    """
    Monotonic decreasing stack.
    Time: O(n), Space: O(n)
    """
    result = [-1] * len(nums)
    stack = []  # indices
    
    for i in range(len(nums)):
        while stack and nums[stack[-1]] < nums[i]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)
    
    return result

def binary_search(nums: List[int], target: int) -> int:
    """
    Classic binary search.
    Time: O(log n), Space: O(1)
    """
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

def find_first_occurrence(nums: List[int], target: int) -> int:
    """
    Binary search for leftmost occurrence.
    Time: O(log n), Space: O(1)
    """
    left, right = 0, len(nums) - 1
    result = -1
    
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            result = mid
            right = mid - 1  # continue searching left
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

def min_days_to_ship(weights: List[int], days: int) -> int:
    """
    Binary search on answer space.
    Time: O(n log(sum)), Space: O(1)
    """
    def can_ship(capacity):
        """Check if we can ship in 'days' with 'capacity'"""
        day_count = 1
        curr_weight = 0
        
        for weight in weights:
            if curr_weight + weight > capacity:
                day_count += 1
                curr_weight = weight
            else:
                curr_weight += weight
        
        return day_count <= days
    
    left, right = max(weights), sum(weights)
    
    while left < right:
        mid = left + (right - left) // 2
        if can_ship(mid):
            right = mid  # try smaller capacity
        else:
            left = mid + 1
    
    return left

def reverse_list(head: ListNode) -> ListNode:
    """
    In-place reversal.
    Time: O(n), Space: O(1)
    """
    prev = None
    curr = head
    
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    
    return prev

def detect_cycle(head: ListNode) -> ListNode:
    """
    Fast/slow pointers for cycle detection.
    Time: O(n), Space: O(1)
    """
    slow = fast = head
    
    # Detect if cycle exists
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # no cycle
    
    # Find cycle start
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    return slow

def merge_two_lists(l1: ListNode, l2: ListNode) -> ListNode:
    """
    Dummy node for clean merging.
    Time: O(n+m), Space: O(1)
    """
    dummy = ListNode(0)
    curr = dummy
    
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    
    curr.next = l1 or l2
    return dummy.next

def inorder_traversal(root: TreeNode) -> List[int]:
    """
    Recursive inorder (left, root, right).
    Time: O(n), Space: O(h) for recursion
    """
    result = []
    
    def dfs(node):
        if not node:
            return
        dfs(node.left)
        result.append(node.val)
        dfs(node.right)
    
    dfs(root)
    return result

def level_order(root: TreeNode) -> List[List[int]]:
    """
    BFS level-order traversal.
    Time: O(n), Space: O(w) where w = max width
    """
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    
    return result

def max_depth(root: TreeNode) -> int:
    """
    Bottom-up DFS.
    Time: O(n), Space: O(h)
    """
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

def path_sum(root: TreeNode, target: int) -> int:
    """
    Top-down DFS with accumulated state.
    Time: O(n), Space: O(h)
    """
    def dfs(node, curr_sum):
        if not node:
            return 0
        
        curr_sum += node.val
        count = 1 if curr_sum == target else 0
        count += dfs(node.left, curr_sum)
        count += dfs(node.right, curr_sum)
        return count
    
    return dfs(root, 0)

def search_bst(root: TreeNode, val: int) -> TreeNode:
    """
    BST search using property.
    Time: O(h), Space: O(1) iterative
    """
    while root:
        if val == root.val:
            return root
        elif val < root.val:
            root = root.left
        else:
            root = root.right
    return None

def kth_smallest(root: TreeNode, k: int) -> int:
    """
    Inorder traversal with counter.
    Time: O(k + h), Space: O(h)
    """
    stack = []
    curr = root
    
    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
        
        curr = stack.pop()
        k -= 1
        if k == 0:
            return curr.val
        curr = curr.right
    
    return -1

def range_sum_bst(root: TreeNode, low: int, high: int) -> int:
    """
    BST pruning for range queries.
    Time: O(n), Space: O(h)
    """
    if not root:
        return 0
    
    total = 0
    if low <= root.val <= high:
        total += root.val
    
    if root.val > low:
        total += range_sum_bst(root.left, low, high)
    if root.val < high:
        total += range_sum_bst(root.right, low, high)
    
    return total

import heapq

def kth_largest(nums: List[int], k: int) -> int:
    """
    Min heap of size k for kth largest.
    Time: O(n log k), Space: O(k)
    """
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

def merge_k_lists(lists: List[ListNode]) -> ListNode:
    """
    Min heap for merging k sorted lists.
    Time: O(n log k), Space: O(k)
    """
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst.val, i, lst))
    
    dummy = ListNode(0)
    curr = dummy
    
    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    
    return dummy.next

class MedianFinder:
    """
    Dual heap for dynamic median.
    Time: O(log n) insert, O(1) median
    """
    def __init__(self):
        self.small = []  # max heap (negate values)
        self.large = []  # min heap
    
    def addNum(self, num: int) -> None:
        heapq.heappush(self.small, -num)
        
        # Balance: small's max <= large's min
        if self.small and self.large and -self.small[0] > self.large[0]:
            val = -heapq.heappop(self.small)
            heapq.heappush(self.large, val)
        
        # Balance sizes
        if len(self.small) > len(self.large) + 1:
            val = -heapq.heappop(self.small)
            heapq.heappush(self.large, val)
        if len(self.large) > len(self.small):
            val = heapq.heappop(self.large)
            heapq.heappush(self.small, -val)
    
    def findMedian(self) -> float:
        if len(self.small) > len(self.large):
            return -self.small[0]
        return (-self.small[0] + self.large[0]) / 2

def dfs_iterative(graph: Dict[int, List[int]], start: int) -> List[int]:
    """
    Iterative DFS using stack.
    Time: O(V+E), Space: O(V)
    """
    visited = set()
    stack = [start]
    result = []
    
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        
        visited.add(node)
        result.append(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)
    
    return result

def has_cycle(graph: Dict[int, List[int]], n: int) -> bool:
    """
    DFS cycle detection (directed graph).
    Time: O(V+E), Space: O(V)
    """
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
    
    def dfs(node):
        if color[node] == GRAY:
            return True  # back edge found
        if color[node] == BLACK:
            return False
        
        color[node] = GRAY
        for neighbor in graph[node]:
            if dfs(neighbor):
                return True
        color[node] = BLACK
        return False
    
    for i in range(n):
        if color[i] == WHITE and dfs(i):
            return True
    return False

def clone_graph(node: 'Node') -> 'Node':
    """
    DFS with mapping for graph cloning.
    Time: O(V+E), Space: O(V)
    """
    if not node:
        return None
    
    clones = {}  # original -> clone
    
    def dfs(original):
        if original in clones:
            return clones[original]
        
        clone = Node(original.val)
        clones[original] = clone
        
        for neighbor in original.neighbors:
            clone.neighbors.append(dfs(neighbor))
        
        return clone
    
    return dfs(node)

from collections import deque

def bfs_shortest_path(graph: Dict[int, List[int]], start: int, end: int) -> int:
    """
    BFS for shortest path.
    Time: O(V+E), Space: O(V)
    """
    queue = deque([(start, 0)])  # (node, distance)
    visited = {start}
    
    while queue:
        node, dist = queue.popleft()
        if node == end:
            return dist
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    
    return -1  # no path found

def shortest_path_grid(grid: List[List[int]]) -> int:
    """
    BFS on grid (4-directional).
    Time: O(m*n), Space: O(m*n)
    """
    if not grid or grid[0][0] == 1:
        return -1
    
    m, n = len(grid), len(grid[0])
    queue = deque([(0, 0, 1)])  # (row, col, steps)
    visited = {(0, 0)}
    directions = [(0,1), (1,0), (0,-1), (-1,0)]
    
    while queue:
        row, col, steps = queue.popleft()
        
        if row == m-1 and col == n-1:
            return steps
        
        for dr, dc in directions:
            r, c = row + dr, col + dc
            if 0 <= r < m and 0 <= c < n and (r,c) not in visited and grid[r][c] == 0:
                visited.add((r, c))
                queue.append((r, c, steps + 1))
    
    return -1

def word_ladder(begin: str, end: str, wordList: List[str]) -> int:
    """
    BFS for transformation sequence.
    Time: O(M² * N) where M=word length, N=wordList size
    Space: O(M * N)
    """
    wordSet = set(wordList)
    if end not in wordSet:
        return 0
    
    queue = deque([(begin, 1)])
    
    while queue:
        word, level = queue.popleft()
        if word == end:
            return level
        
        # Try all possible transformations
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                next_word = word[:i] + c + word[i+1:]
                if next_word in wordSet:
                    wordSet.remove(next_word)
                    queue.append((next_word, level + 1))
    
    return 0

def fib_memoization(n: int) -> int:
    """
    Top-down DP with memoization.
    Time: O(n), Space: O(n)
    """
    memo = {}
    
    def dp(i):
        if i <= 1:
            return i
        if i in memo:
            return memo[i]
        memo[i] = dp(i-1) + dp(i-2)
        return memo[i]
    
    return dp(n)

def fib_tabulation(n: int) -> int:
    """
    Bottom-up DP with table.
    Time: O(n), Space: O(n)
    """
    if n <= 1:
        return n
    
    dp = [0] * (n + 1)
    dp[1] = 1
    
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

def fib_optimized(n: int) -> int:
    """
    Space-optimized DP.
    Time: O(n), Space: O(1)
    """
    if n <= 1:
        return n
    
    prev2, prev1 = 0, 1
    for i in range(2, n + 1):
        curr = prev1 + prev2
        prev2, prev1 = prev1, curr
    
    return prev1

def longest_common_subsequence(s1: str, s2: str) -> int:
    """
    2D DP for sequence alignment.
    Time: O(m*n), Space: O(m*n)
    """
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = 1 + dp[i-1][j-1]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[m][n]