Hash, Stack & Queue

stack = []
stack.append(item)    # push  - O(1)
stack.pop()           # pop   - O(1)
stack[-1]             # peek  - O(1)
len(stack) == 0       # empty check

from collections import deque

queue = deque()
queue.append(item)     # enqueue (right) - O(1)
queue.popleft()        # dequeue (left)  - O(1)
queue[0]               # peek front      - O(1)
len(queue) == 0        # empty check

def two_sum(nums, target):
    """Find two indices whose values sum to target."""
    seen = {}                           # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:          # O(1) lookup
            return [seen[complement], i]
        seen[num] = i                   # store for future lookups
    return []

def is_valid(s):
    """Check if brackets are properly matched and nested."""
    stack = []
    match = {')': '(', ']': '[', '}': '{'}  # closing -> opening

    for char in s:
        if char in match:               # closing bracket
            if not stack or stack[-1] != match[char]:
                return False            # nothing to match, or mismatch
            stack.pop()                 # matched -- remove opening
        else:
            stack.append(char)          # opening bracket -- push

    return len(stack) == 0              # all brackets must be matched

from collections import defaultdict

def group_anagrams(strs):
    """Group strings that are anagrams of each other."""
    groups = defaultdict(list)
    for s in strs:
        # Sorted characters form a canonical key for anagrams
        # "eat" -> "aet", "tea" -> "aet", "ate" -> "aet"
        key = tuple(sorted(s))
        groups[key].append(s)
    return list(groups.values())

def longest_consecutive(nums):
    """Find length of longest consecutive element sequence. O(n)."""
    num_set = set(nums)
    best = 0

    for num in num_set:
        # Only start counting from the BEGINNING of a sequence.
        # This check ensures each sequence is counted exactly once.
        if num - 1 not in num_set:      # <-- the key insight
            length = 1
            while num + length in num_set:
                length += 1
            best = max(best, length)

    return best

class MinStack:
    """Stack that supports O(1) push, pop, top, and getMin."""

    def __init__(self):
        self.stack = []
        self.min_stack = []             # tracks minimum at each level

    def push(self, val):
        self.stack.append(val)
        # Push the new minimum (compare with current min)
        min_val = min(val, self.min_stack[-1] if self.min_stack else val)
        self.min_stack.append(min_val)

    def pop(self):
        self.stack.pop()
        self.min_stack.pop()            # min_stack stays in sync

    def top(self):
        return self.stack[-1]

    def getMin(self):
        return self.min_stack[-1]

#  stack:     [5, 3, 7, 2]     min_stack: [5, 3, 3, 2]
#  After pop: [5, 3, 7]        min_stack: [5, 3, 3]
#  getMin() = 3  (correct!)

from collections import OrderedDict

class LRUCache:
    """Least Recently Used cache with O(1) get and put."""

    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)      # mark as recently used
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)  # mark as recently used
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # evict LEAST recent (front)

def eval_rpn(tokens):
    """Evaluate Reverse Polish Notation using a stack."""
    stack = []
    ops = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: int(a / b),   # truncate toward zero
    }
    for token in tokens:
        if token in ops:
            b = stack.pop()             # second operand (top)
            a = stack.pop()             # first operand
            stack.append(ops[token](a, b))
        else:
            stack.append(int(token))
    return stack[0]

# WRONG for "find two distinct indices":
seen[num] = i
if complement in seen: ...   # might find itself

# RIGHT:
if complement in seen: ...   # check first
seen[num] = i                # store after