HashMap Pattern

# Skeleton 1: Complement lookup (Two Sum, Pair with Difference, etc.)
def complement_lookup(nums, target):
    seen = {}                          # value -> index (or count)
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i                  # Store AFTER check to avoid using same element
    return []

# Skeleton 2: Frequency counter (Anagram, Top K, First Unique, etc.)
from collections import Counter, defaultdict
def frequency_pattern(arr):
    freq = Counter(arr)                # one-liner build
    # ...query freq[x] in O(1) afterwards
    return freq

# Skeleton 3: Prefix sum plus map (Subarray Sum K, Continuous Subarray, etc.)
def prefix_sum_map(nums, k):
    count, prefix = 0, 0
    sum_count = {0: 1}                 # CRITICAL: handles subarrays starting at index 0
    for num in nums:
        prefix += num
        count += sum_count.get(prefix - k, 0)
        sum_count[prefix] = sum_count.get(prefix, 0) + 1
    return count

def two_sum(nums, target):
    """Find indices of two numbers that sum to target"""
    seen = {}  # value -> index mapping
    
    for i, num in enumerate(nums):
        complement = target - num       # What value do we need?
        if complement in seen:          # Have we seen it before?
            return [seen[complement], i]
        seen[num] = i                   # Store current number for future lookups
    
    return []  # No pair found

from collections import Counter

def top_k_frequent(nums, k):
    """Return k most frequent elements"""
    count = Counter(nums)
    return [num for num, _ in count.most_common(k)]

def is_anagram(s, t):
    """Check if t is anagram of s"""
    return Counter(s) == Counter(t)

from collections import defaultdict

def group_anagrams(strs):
    """Group strings that are anagrams of each other"""
    groups = defaultdict(list)
    
    for s in strs:
        key = tuple(sorted(s))  # or count-based key
        groups[key].append(s)
    
    return list(groups.values())

def subarray_sum_equals_k(nums, k):
    """Count subarrays with sum exactly k"""
    count = 0
    prefix_sum = 0
    sum_count = {0: 1}  # prefix_sum -> frequency (0 appears once: empty prefix)
    
    for num in nums:
        prefix_sum += num
        
        # How many previous prefix sums equal (prefix_sum - k)?
        # Each one defines a subarray ending here with sum exactly k
        if prefix_sum - k in sum_count:
            count += sum_count[prefix_sum - k]
        
        # Record this prefix sum for future subarrays to reference
        sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1
    
    return count

def longest_consecutive(nums):
    """Find length of longest consecutive sequence in O(n)"""
    num_set = set(nums)      # O(1) lookups
    max_length = 0
    
    for num in num_set:
        # KEY INSIGHT: only start counting from the beginning of a sequence
        if num - 1 not in num_set:   # num is a sequence start
            current = num
            length = 1
            
            while current + 1 in num_set:  # Extend the sequence
                current += 1
                length += 1
            
            max_length = max(max_length, length)
    
    return max_length

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity
    
    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]
    
    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)