DSA Data Structures - Code Library

Runnable Python implementations of the data structures worth knowing by heart. Source lives in DSA/data-structures/.

Use the copy button on any block to grab the code. These embed the real source files, so they always match the repo.

Design

Lru Cache

# DATA STRUCTURE: LRU Cache (Hash Map + Doubly Linked List)
# DIFFICULTY: Medium | FREQUENCY: Very High (top SDE-2 design question at Google/Meta/Amazon)

# Least Recently Used (LRU) Cache - one of the most common SDE-2 interview questions.
# Supports get and put in O(1) time using a Hash Map + Doubly Linked List.

# Time Complexity:
# - get: O(1)
# - put: O(1)
# Space: O(capacity)

# When to use:
# - Cache with fixed capacity that evicts least recently used items
# - Any problem requiring O(1) access + O(1) eviction of oldest entry
# - System design: caching layer, browser history, page replacement

# NOTE: Python's collections.OrderedDict (or a plain dict in 3.7+, using move_to_end) gives an
# LRU cache in a few lines, and functools.lru_cache decorates functions directly. This explicit
# Hash Map + DLL implementation is what interviewers usually expect you to build from scratch.

from typing import Optional

# COMMON MISTAKES:
# - Forgetting to move a node to the front on GET (not just PUT).
# - Not using dummy head/tail sentinels, leading to null-pointer edge cases.
# - Evicting before checking capacity, or evicting the wrong end (LRU is next to tail).
# - Forgetting to delete the evicted key from the map.

# RELATED PROBLEMS:
# - LRU Cache (LC 146)
# - LFU Cache (LC 460)
# - Design Browser History (LC 1472)


class DLLNode:
    def __init__(self, key: int = 0, val: int = 0) -> None:
        self.key = key
        self.val = val
        self.prev: Optional["DLLNode"] = None
        self.next: Optional["DLLNode"] = None


class LRUCache:
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.map: dict[int, DLLNode] = {}  # key -> DLLNode

        # Dummy head and tail to avoid None checks
        self.head = DLLNode()
        self.tail = DLLNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    # Move node to front (most recently used)
    def _add_to_front(self, node: DLLNode) -> None:
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    # Remove node from its current position
    def _remove_node(self, node: DLLNode) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    # Move existing node to front
    def _move_to_front(self, node: DLLNode) -> None:
        self._remove_node(node)
        self._add_to_front(node)

    # Remove and return the least recently used node (before tail)
    def _remove_lru(self) -> DLLNode:
        lru = self.tail.prev
        self._remove_node(lru)
        return lru

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1

        node = self.map[key]
        self._move_to_front(node)  # mark as recently used
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            # Update existing
            node = self.map[key]
            node.val = value
            self._move_to_front(node)
        else:
            # Add new
            if len(self.map) == self.capacity:
                # Evict LRU
                lru = self._remove_lru()
                del self.map[lru.key]

            new_node = DLLNode(key, value)
            self._add_to_front(new_node)
            self.map[key] = new_node


# Examples (only run when executed directly)
if __name__ == "__main__":
    cache = LRUCache(2)
    cache.put(1, 1)
    cache.put(2, 2)
    print(cache.get(1))    # 1
    cache.put(3, 3)        # evicts key 2
    print(cache.get(2))    # -1 (evicted)
    cache.put(4, 4)        # evicts key 1
    print(cache.get(1))    # -1 (evicted)
    print(cache.get(3))    # 3
    print(cache.get(4))    # 4

Graph

Graph

# DATA STRUCTURE: Graph (adjacency list / matrix / edge list + builders)
# DIFFICULTY: Medium | FREQUENCY: Very High (graph representation underpins most graph problems)

# A graph is a collection of nodes (vertices) connected by edges.
# This file provides adjacency list and adjacency matrix representations,
# plus common helper utilities used across graph problems.

# Time Complexity:
# - Add vertex: O(1)
# - Add edge: O(1)
# - Remove edge: O(E) for adjacency list
# - Has edge: O(degree) for list, O(1) for matrix
# - Get neighbors: O(1) for list, O(V) for matrix
# - Space: O(V + E) for list, O(V^2) for matrix

# When to use:
# - Adjacency List: sparse graphs, most interview problems
# - Adjacency Matrix: dense graphs, Floyd-Warshall, quick edge lookup
# - Edge List: Kruskal's MST, Bellman-Ford

from collections import defaultdict

# COMMON MISTAKES:
# - Forgetting to add the reverse edge for undirected graphs.
# - Assuming a matrix value of 0 means "no edge" when 0 could be a valid weight.
# - Not initializing missing vertices (KeyError on lookup) - defaultdict avoids this.
# - Confusing neighbor tuples (node, weight) ordering across functions.

# RELATED PROBLEMS:
# - Number of Islands (LC 200)
# - Course Schedule (LC 207)
# - Clone Graph (LC 133)
# - Network Delay Time (LC 743)


# === ADJACENCY LIST (most common for interviews) ===

class Graph:
    def __init__(self, directed: bool = False) -> None:
        self.adj: dict[int, list[tuple[int, int]]] = defaultdict(list)
        self.directed = directed

    def add_vertex(self, v: int) -> None:
        # defaultdict creates the entry on first access; touch it to register isolated vertices.
        _ = self.adj[v]

    def add_edge(self, u: int, v: int, weight: int = 1) -> None:
        self.add_vertex(u)
        self.add_vertex(v)
        self.adj[u].append((v, weight))
        if not self.directed:
            self.adj[v].append((u, weight))

    def get_neighbors(self, v: int) -> list[tuple[int, int]]:
        return self.adj.get(v, [])

    def has_edge(self, u: int, v: int) -> bool:
        if u not in self.adj:
            return False
        return any(node == v for node, _ in self.adj[u])

    def get_vertices(self) -> list[int]:
        return list(self.adj.keys())

    @property
    def size(self) -> int:
        return len(self.adj)


# === BUILD FROM COMMON INPUT FORMATS ===

# From edge list: [[0, 1], [1, 2], [2, 0]]
def build_adj_list(n: int, edges: list[list[int]], directed: bool = False) -> list[list[int]]:
    graph: list[list[int]] = [[] for _ in range(n)]

    for u, v in edges:
        graph[u].append(v)
        if not directed:
            graph[v].append(u)

    return graph


# From weighted edge list: [[0, 1, 5], [1, 2, 3]]
def build_weighted_adj_list(n: int, edges: list[list[int]], directed: bool = False) -> list[list[tuple[int, int]]]:
    graph: list[list[tuple[int, int]]] = [[] for _ in range(n)]

    for u, v, w in edges:
        graph[u].append((v, w))
        if not directed:
            graph[v].append((u, w))

    return graph


# From adjacency matrix to adjacency list
def matrix_to_adj_list(matrix: list[list[float]]) -> list[list[int]]:
    n = len(matrix)
    graph: list[list[int]] = [[] for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if matrix[i][j] != 0 and matrix[i][j] != float("inf"):
                graph[i].append(j)

    return graph


# === ADJACENCY MATRIX ===

def build_adj_matrix(n: int, edges: list[list[int]], directed: bool = False) -> list[list[int]]:
    matrix: list[list[int]] = [[0] * n for _ in range(n)]

    for edge in edges:
        u, v = edge[0], edge[1]
        w = edge[2] if len(edge) > 2 else 1
        matrix[u][v] = w
        if not directed:
            matrix[v][u] = w

    return matrix


# === UTILITY: COMPUTE INDEGREES (for topological sort / Kahn's) ===

def compute_indegrees(n: int, graph: list[list[int]]) -> list[int]:
    indegree = [0] * n

    for u in range(n):
        for v in graph[u]:
            indegree[v] += 1

    return indegree


# Examples (only run when executed directly)
if __name__ == "__main__":
    g = Graph(directed=True)
    g.add_edge(0, 1, 4)
    g.add_edge(0, 2, 1)
    g.add_edge(2, 1, 2)
    g.add_edge(1, 3, 1)
    print(g.get_neighbors(0))   # [(1, 4), (2, 1)]
    print(g.has_edge(0, 1))     # True
    print(g.has_edge(1, 0))     # False (directed)
    print(g.size)               # 4

    adj = build_adj_list(4, [[0, 1], [1, 2], [2, 3], [3, 0]])
    print(adj)  # [[1, 3], [0, 2], [1, 3], [2, 0]]

    weighted = build_weighted_adj_list(3, [[0, 1, 5], [1, 2, 3], [0, 2, 10]])
    print(weighted)  # [[(1, 5), (2, 10)], [(0, 5), (2, 3)], [(1, 3), (0, 10)]]

    matrix = build_adj_matrix(3, [[0, 1, 2], [1, 2, 3], [0, 2, 7]])
    print(matrix)  # [[0, 2, 7], [2, 0, 3], [7, 3, 0]]

Heap

Max Heap

# DATA STRUCTURE: MaxHeap
# DIFFICULTY: Medium | FREQUENCY: Very High (Top-K, running median, scheduling at Google/Meta/Amazon)

# A MaxHeap is a binary tree where the value of each node is greater than
# or equal to the values of its children. The root always holds the maximum.

# Time Complexity:
# - push: O(log n)
# - pop: O(log n)
# - peek: O(1)

# When to use:
# - Kth smallest element (maintain max-heap of size k)
# - Running median (pair with MinHeap)
# - Priority scheduling (highest priority first)
# - Merge K sorted lists (less common, usually MinHeap)

# NOTE: Python's `heapq` is a MIN-heap only. The idiomatic way to get a max-heap is to push
# negated values (heapq.heappush(h, -x)) and negate on pop. This explicit class is kept for
# teaching the internals; in real interviews mention the "negate values" trick with heapq.

from min_heap import MinHeap

# COMMON MISTAKES:
# - Assuming heapq is a max-heap (it is min-only; negate values or use this class).
# - Using '>' vs '>=' inconsistently in _up/_down, corrupting heap order.
# - Off-by-one in child/parent index math.
# - Integer vs float division for the running-median average.

# RELATED PROBLEMS:
# - Kth Largest Element in an Array (LC 215)
# - Find Median from Data Stream (LC 295)
# - Top K Frequent Elements (LC 347)
# - Last Stone Weight (LC 1046)


class MaxHeap:
    def __init__(self) -> None:
        self.h: list[int] = []

    def push(self, val: int) -> None:
        self.h.append(val)
        self._up(len(self.h) - 1)

    def pop(self) -> int | None:
        if not self.h:
            return None
        if len(self.h) == 1:
            return self.h.pop()

        top = self.h[0]
        self.h[0] = self.h.pop()
        self._down(0)
        return top

    def peek(self) -> int | None:
        return self.h[0] if self.h else None

    def size(self) -> int:
        return len(self.h)

    def _up(self, i: int) -> None:
        h = self.h
        while i > 0:
            p = (i - 1) >> 1
            if h[p] >= h[i]:
                break
            h[p], h[i] = h[i], h[p]
            i = p

    def _down(self, i: int) -> None:
        h = self.h
        n = len(h)
        while True:
            largest = i
            left = 2 * i + 1
            right = 2 * i + 2
            if left < n and h[left] > h[largest]:
                largest = left
            if right < n and h[right] > h[largest]:
                largest = right
            if largest == i:
                break
            h[i], h[largest] = h[largest], h[i]
            i = largest


# === RUNNING MEDIAN (classic SDE-2 problem) ===
# Use MaxHeap for lower half, MinHeap for upper half.
# Median is always accessible from the tops of the heaps.
class MedianFinder:
    def __init__(self) -> None:
        self.lo = MaxHeap()  # max-heap: stores smaller half
        self.hi = MinHeap()  # min-heap: stores larger half

    def add_num(self, num: int) -> None:
        self.lo.push(num)
        # Ensure max of lo <= min of hi
        self.hi.push(self.lo.pop())

        # Balance: lo can have at most 1 more element than hi
        if self.lo.size() < self.hi.size():
            self.lo.push(self.hi.pop())

    def find_median(self) -> float:
        if self.lo.size() > self.hi.size():
            return self.lo.peek()
        return (self.lo.peek() + self.hi.peek()) / 2


# Examples (only run when executed directly)
if __name__ == "__main__":
    max_heap = MaxHeap()
    max_heap.push(3)
    max_heap.push(1)
    max_heap.push(5)
    max_heap.push(2)
    print(max_heap.pop())   # 5
    print(max_heap.pop())   # 3
    print(max_heap.peek())  # 2

    mf = MedianFinder()
    mf.add_num(1)
    mf.add_num(2)
    print(mf.find_median())  # 1.5
    mf.add_num(3)
    print(mf.find_median())  # 2
    mf.add_num(4)
    print(mf.find_median())  # 2.5

Min Heap

# DATA STRUCTURE: MinHeap
# DIFFICULTY: Medium | FREQUENCY: Very High (Dijkstra, Prim, Top-K, Median at Google/Meta/Amazon)

# A MinHeap is a binary tree where the value of each node is less than or equal to the values of its
# children. This implementation uses a list to represent the heap.
# The root of the heap is at index 0, and for any node at index i:
# - The left child is at index 2*i + 1
# - The right child is at index 2*i + 2
# - The parent is at index (i - 1) // 2
# The main operations are push (to add an element) and pop (to remove the minimum element).
# Both operations maintain the heap property by bubbling elements up or down as necessary.

# Time Complexity:
# - push: O(log n) in the worst case, where n is the number of elements in the heap.
# - pop: O(log n) in the worst case.

# NOTE: In idiomatic Python, prefer the built-in `heapq` module for a min-heap
# (heapq.heappush / heapq.heappop). This explicit class is kept for teaching the internals.

# COMMON MISTAKES:
# - Forgetting to bubble up after push or bubble down after pop.
# - Comparing with '<' vs '<=' inconsistently in _up/_down (can loop or break heap order).
# - Off-by-one in child/parent index math: left = 2*i+1, right = 2*i+2, parent = (i-1)//2.
# - Popping from an empty heap without a guard.

# RELATED PROBLEMS:
# - Kth Largest Element in an Array (LC 215)
# - Top K Frequent Elements (LC 347)
# - Find Median from Data Stream (LC 295)
# - Merge k Sorted Lists (LC 23)


class MinHeap:
    def __init__(self) -> None:
        # Initialize empty heap list
        self.h: list[int] = []

    def push(self, val: int) -> None:
        # Add new value to end of heap
        self.h.append(val)
        # Bubble up to maintain heap property
        self._up(len(self.h) - 1)

    def pop(self) -> int | None:
        # Return None if heap is empty
        if not self.h:
            return None
        # Return last element if only one element
        if len(self.h) == 1:
            return self.h.pop()

        # Store minimum value (root)
        top = self.h[0]
        # Move last element to root
        self.h[0] = self.h.pop()
        # Bubble down to maintain heap property
        self._down(0)
        return top

    def peek(self) -> int | None:
        return self.h[0] if self.h else None

    def size(self) -> int:
        return len(self.h)

    def _up(self, i: int) -> None:
        h = self.h
        while i > 0:
            # Calculate parent index
            p = (i - 1) // 2
            # Stop if parent is smaller (heap property satisfied)
            if h[p] <= h[i]:
                break
            # Swap with parent
            h[p], h[i] = h[i], h[p]
            i = p

    def _down(self, i: int) -> None:
        h = self.h
        n = len(h)
        while True:
            smallest = i
            # Calculate left and right child indices
            left = 2 * i + 1
            right = 2 * i + 2
            # Find smallest among node and its children
            if left < n and h[left] < h[smallest]:
                smallest = left
            if right < n and h[right] < h[smallest]:
                smallest = right
            # Stop if current node is smallest (heap property satisfied)
            if smallest == i:
                break
            # Swap with smallest child
            h[i], h[smallest] = h[smallest], h[i]
            i = smallest


# Examples (only run when executed directly)
if __name__ == "__main__":
    min_heap = MinHeap()
    min_heap.push(5)
    min_heap.push(3)
    min_heap.push(8)
    min_heap.push(1)

    print(min_heap.pop())  # 1

Priority Queue

# DATA STRUCTURE: Min-Heap based Priority Queue
# DIFFICULTY: Medium | FREQUENCY: Very High (Dijkstra, Prim, task scheduling at Google/Amazon/Uber)

# A priority queue is an abstract data type similar to a regular queue, but where each element has a
# "priority". In a min-priority queue, elements with lower priority values are served first.

# Time Complexity:
# - Insertion (enqueue): O(log n)
# - Removal of minimum element (dequeue): O(log n)
# - Peek at minimum element: O(1)

# When to use:
# - When you need to efficiently retrieve and remove the highest-priority (lowest-value) element.
# - When implementing algorithms like Dijkstra's shortest path or Prim's minimum spanning tree.
# - When managing tasks with varying levels of urgency.

# NOTE: In idiomatic Python, use the built-in `heapq` module directly with tuples, e.g.
# heapq.heappush(pq, (priority, item)). To customize ordering, push a (key(item), item) tuple.
# This explicit class mirrors the JS MinPriorityScope with an optional `key` function
# (the Pythonic equivalent of a comparator) for teaching purposes.

import heapq
from collections.abc import Callable
from typing import Any

# COMMON MISTAKES:
# - Relying on heapq being stable / having decrease-key (it has neither).
# - Pushing raw objects that aren't comparable; use a (key, item) tuple instead.
# - Forgetting that heapq is a MIN-heap (negate the key for max-priority behaviour).
# - Peeking/popping without checking for emptiness.

# RELATED PROBLEMS:
# - Network Delay Time (LC 743)
# - K Closest Points to Origin (LC 973)
# - Task Scheduler (LC 621)
# - Merge k Sorted Lists (LC 23)


class MinPriorityQueue:
    def __init__(self, key: Callable[[Any], Any] | None = None) -> None:
        # `key` maps an element to its comparable priority. Default: the element itself.
        self._key = key if key is not None else (lambda x: x)
        self._heap: list[tuple[Any, int, Any]] = []
        # A monotonically increasing counter breaks ties so unorderable items never compare directly.
        self._counter = 0

    def enqueue(self, element: Any) -> None:
        heapq.heappush(self._heap, (self._key(element), self._counter, element))
        self._counter += 1

    def dequeue(self) -> Any | None:
        if not self._heap:
            return None
        return heapq.heappop(self._heap)[2]

    def peek(self) -> Any | None:
        return self._heap[0][2] if self._heap else None

    def is_empty(self) -> bool:
        return len(self._heap) == 0

    def size(self) -> int:
        return len(self._heap)


# Examples (only run when executed directly)
if __name__ == "__main__":
    # Simple numbers (default key)
    pq1 = MinPriorityQueue()
    pq1.enqueue(5)
    pq1.enqueue(2)
    pq1.enqueue(8)
    print(pq1.dequeue())  # 2

    # Custom key for tuples [distance, node] -> order by distance
    pq2 = MinPriorityQueue(key=lambda x: x[0])
    pq2.enqueue([10, "A"])
    pq2.enqueue([5, "B"])
    pq2.enqueue([15, "C"])
    print(pq2.dequeue())  # [5, 'B']

    # Custom key for dict-like tasks -> order by priority
    pq3 = MinPriorityQueue(key=lambda x: x["priority"])
    pq3.enqueue({"name": "Task A", "priority": 3})
    pq3.enqueue({"name": "Task B", "priority": 1})
    pq3.enqueue({"name": "Task C", "priority": 2})
    print(pq3.dequeue())  # {'name': 'Task B', 'priority': 1}

Linked List

Linked List

# DATA STRUCTURE: Singly Linked List & Common Operations
# DIFFICULTY: Medium | FREQUENCY: Very High (pointer manipulation staple at Google/Meta/Amazon)

# A singly linked list where each node points to the next node.
# Fundamental data structure for interviews - tests pointer manipulation skills.

# Time Complexity:
# - Access: O(n)
# - Search: O(n)
# - Insert at head: O(1)
# - Insert at tail: O(n) without tail pointer, O(1) with
# - Delete: O(n) to find, O(1) to remove

# When to use:
# - When you need O(1) insertion/deletion at known positions
# - When you don't need random access
# - Implementing stacks, queues, LRU cache
# - Problems involving pointer manipulation (reverse, merge, cycle detection)

from __future__ import annotations

# COMMON MISTAKES:
# - Losing the rest of the list by reassigning `next` before saving it.
# - Not using a dummy head node for merge/remove problems (causes edge-case bugs).
# - Off-by-one when advancing the fast pointer in "remove Nth from end".
# - Forgetting to terminate the reversed list (last node's next must become None).

# RELATED PROBLEMS:
# - Reverse Linked List (LC 206)
# - Linked List Cycle / Cycle II (LC 141 / LC 142)
# - Middle of the Linked List (LC 876)
# - Merge Two Sorted Lists (LC 21)
# - Remove Nth Node From End of List (LC 19)
# - Palindrome Linked List (LC 234)
# - Add Two Numbers (LC 2)


class ListNode:
    def __init__(self, val: int = 0, next: ListNode | None = None) -> None:
        self.val = val
        self.next = next


# === REVERSE LINKED LIST (iterative) ===
# The single most important linked list operation for interviews.
def reverse_list(head: ListNode | None) -> ListNode | None:
    prev: ListNode | None = None
    curr = head

    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt

    return prev


# === REVERSE LINKED LIST (recursive) ===
def reverse_list_recursive(head: ListNode | None) -> ListNode | None:
    if not head or not head.next:
        return head

    new_head = reverse_list_recursive(head.next)
    head.next.next = head
    head.next = None

    return new_head


# === DETECT CYCLE (Floyd's Tortoise & Hare) ===
def has_cycle(head: ListNode | None) -> bool:
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True

    return False


# === FIND CYCLE START ===
def detect_cycle(head: ListNode | None) -> ListNode | None:
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow is fast:
            # Move one pointer to head, advance both by 1
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow  # cycle start

    return None


# === FIND MIDDLE NODE ===
def middle_node(head: ListNode | None) -> ListNode | None:
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow


# === MERGE TWO SORTED LISTS ===
def merge_two_lists(l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
    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 if l1 else l2
    return dummy.next


# === REMOVE NTH NODE FROM END ===
# Two pointers: advance fast by n, then move both until fast reaches end.
def remove_nth_from_end(head: ListNode | None, n: int) -> ListNode | None:
    dummy = ListNode(0, head)
    fast = dummy
    slow = dummy

    for _ in range(n + 1):
        fast = fast.next

    while fast:
        fast = fast.next
        slow = slow.next

    slow.next = slow.next.next
    return dummy.next


# === PALINDROME LINKED LIST ===
# Find middle -> reverse second half -> compare.
def is_palindrome(head: ListNode | None) -> bool:
    slow = head
    fast = head

    # Find middle
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Reverse second half
    prev: ListNode | None = None
    while slow:
        nxt = slow.next
        slow.next = prev
        prev = slow
        slow = nxt

    # Compare both halves
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left = left.next
        right = right.next

    return True


# === ADD TWO NUMBERS (digits stored in reverse) ===
def add_two_numbers(l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
    dummy = ListNode(0)
    curr = dummy
    carry = 0

    while l1 or l2 or carry:
        total = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
        carry = total // 10
        curr.next = ListNode(total % 10)
        curr = curr.next

        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next

    return dummy.next


# Helper: build list from a Python list
def build_list(arr: list[int]) -> ListNode | None:
    dummy = ListNode(0)
    curr = dummy
    for val in arr:
        curr.next = ListNode(val)
        curr = curr.next
    return dummy.next


# Helper: linked list to a Python list
def to_array(head: ListNode | None) -> list[int]:
    result: list[int] = []
    while head:
        result.append(head.val)
        head = head.next
    return result


# Examples (only run when executed directly)
if __name__ == "__main__":
    list1 = build_list([1, 2, 4])
    list2 = build_list([1, 3, 4])
    print(to_array(merge_two_lists(list1, list2)))  # [1, 1, 2, 3, 4, 4]

    list3 = build_list([1, 2, 3, 4, 5])
    print(to_array(reverse_list(list3)))  # [5, 4, 3, 2, 1]

    print(middle_node(build_list([1, 2, 3, 4, 5])).val)  # 3

    print(is_palindrome(build_list([1, 2, 2, 1])))  # True
    print(is_palindrome(build_list([1, 2, 3])))     # False

Stack

Stack

# DATA STRUCTURE: Stack (LIFO) + MinStack
# DIFFICULTY: Easy | FREQUENCY: Very High (parentheses, monotonic stack, DFS at all top companies)

# A stack is a LIFO (Last In, First Out) data structure.
# Think of it like a stack of plates - you add and remove from the top.

# Time Complexity:
# - push: O(1)
# - pop: O(1)
# - peek: O(1)
# - is_empty: O(1)

# When to use:
# - Matching parentheses/brackets
# - Undo/redo operations
# - DFS traversal (iterative)
# - Expression evaluation (infix, postfix)
# - Monotonic stack problems (next greater element)
# - Function call simulation (recursion stack)

# NOTE: In idiomatic Python, a plain `list` already works as a stack (append / pop). This class
# is kept for teaching the ADT explicitly.

from typing import Any

# COMMON MISTAKES:
# - Popping/peeking an empty stack (list.pop() raises IndexError).
# - For MinStack: forgetting to push the running min on EVERY push so pop stays O(1).
# - Comparing with the wrong end of the list (top is index -1, not 0).

# RELATED PROBLEMS:
# - Valid Parentheses (LC 20)
# - Min Stack (LC 155)
# - Next Greater Element I (LC 496)
# - Evaluate Reverse Polish Notation (LC 150)


class Stack:
    def __init__(self) -> None:
        self.s: list[Any] = []

    def push(self, x: Any) -> None:
        self.s.append(x)

    def pop(self) -> Any:
        return self.s.pop()

    def peek(self) -> Any:
        return self.s[-1]

    def is_empty(self) -> bool:
        return len(self.s) == 0

    def size(self) -> int:
        return len(self.s)


# === MIN STACK (O(1) get_min) ===
# Common interview problem: design a stack that supports get_min in O(1).
class MinStack:
    def __init__(self) -> None:
        self.stack: list[int] = []
        self.min_stack: list[int] = []  # tracks minimum at each level

    def push(self, val: int) -> None:
        self.stack.append(val)
        cur_min = val if not self.min_stack else min(val, self.min_stack[-1])
        self.min_stack.append(cur_min)

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

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

    def get_min(self) -> int:
        return self.min_stack[-1]


# Examples (only run when executed directly)
if __name__ == "__main__":
    stack = Stack()
    stack.push(1)
    stack.push(2)
    stack.push(3)
    print(stack.peek())     # 3
    print(stack.pop())      # 3
    print(stack.size())     # 2
    print(stack.is_empty())  # False

    min_stack = MinStack()
    min_stack.push(5)
    min_stack.push(2)
    min_stack.push(7)
    print(min_stack.get_min())  # 2
    min_stack.pop()
    print(min_stack.get_min())  # 2
    min_stack.pop()
    print(min_stack.get_min())  # 5

Tree

Bst

# DATA STRUCTURE: Binary Search Tree (BST)
# DIFFICULTY: Medium | FREQUENCY: High (validate BST, kth smallest, LCA at Google/Meta/Amazon)

# A BST is a binary tree where for every node:
#   - All values in left subtree < node.val
#   - All values in right subtree > node.val

# Time Complexity (balanced):
# - Search: O(log n)
# - Insert: O(log n)
# - Delete: O(log n)
# Worst case (skewed): O(n) for all operations

# When to use:
# - Ordered data with dynamic insertions/deletions
# - Range queries, floor/ceiling lookups
# - Inorder traversal gives sorted output
# - Interview problems: validate BST, kth smallest, LCA in BST

from __future__ import annotations

# COMMON MISTAKES:
# - Validating a BST by only comparing a node with its direct children (must carry min/max bounds).
# - Mishandling the two-children delete case (replace with inorder successor, then delete it).
# - Using <= instead of < for the "all left < node" invariant (duplicates policy).
# - Recursing into both subtrees for LCA in a BST instead of exploiting the ordering.

# RELATED PROBLEMS:
# - Validate Binary Search Tree (LC 98)
# - Kth Smallest Element in a BST (LC 230)
# - Lowest Common Ancestor of a BST (LC 235)
# - Convert Sorted Array to Binary Search Tree (LC 108)


class TreeNode:
    def __init__(self, val: int = 0, left: TreeNode | None = None, right: TreeNode | None = None) -> None:
        self.val = val
        self.left = left
        self.right = right


class BST:
    def __init__(self) -> None:
        self.root: TreeNode | None = None

    # Insert a value
    def insert(self, val: int) -> None:
        self.root = self._insert_node(self.root, val)

    def _insert_node(self, node: TreeNode | None, val: int) -> TreeNode:
        if not node:
            return TreeNode(val)
        if val < node.val:
            node.left = self._insert_node(node.left, val)
        elif val > node.val:
            node.right = self._insert_node(node.right, val)
        return node  # duplicates ignored

    # Search for a value
    def search(self, val: int) -> bool:
        return self._search_node(self.root, val)

    def _search_node(self, node: TreeNode | None, val: int) -> bool:
        if not node:
            return False
        if val == node.val:
            return True
        if val < node.val:
            return self._search_node(node.left, val)
        return self._search_node(node.right, val)

    # Delete a value
    def delete(self, val: int) -> None:
        self.root = self._delete_node(self.root, val)

    def _delete_node(self, node: TreeNode | None, val: int) -> TreeNode | None:
        if not node:
            return None

        if val < node.val:
            node.left = self._delete_node(node.left, val)
        elif val > node.val:
            node.right = self._delete_node(node.right, val)
        else:
            # Found the node to delete
            # Case 1: leaf node
            if not node.left and not node.right:
                return None
            # Case 2: one child
            if not node.left:
                return node.right
            if not node.right:
                return node.left
            # Case 3: two children - replace with inorder successor
            successor = self._find_min(node.right)
            node.val = successor.val
            node.right = self._delete_node(node.right, successor.val)

        return node

    def _find_min(self, node: TreeNode) -> TreeNode:
        while node.left:
            node = node.left
        return node

    # Inorder traversal (sorted output)
    def inorder(self) -> list[int]:
        result: list[int] = []
        self._inorder_helper(self.root, result)
        return result

    def _inorder_helper(self, node: TreeNode | None, result: list[int]) -> None:
        if not node:
            return
        self._inorder_helper(node.left, result)
        result.append(node.val)
        self._inorder_helper(node.right, result)


# === COMMON BST INTERVIEW PROBLEMS ===

# Validate BST
def is_valid_bst(root: TreeNode | None, low: float = float("-inf"), high: float = float("inf")) -> bool:
    if not root:
        return True
    if root.val <= low or root.val >= high:
        return False
    return is_valid_bst(root.left, low, root.val) and is_valid_bst(root.right, root.val, high)


# Kth Smallest Element in BST (inorder traversal)
def kth_smallest(root: TreeNode | None, k: int) -> int | None:
    count = 0
    result: int | None = None

    def inorder(node: TreeNode | None) -> None:
        nonlocal count, result
        if not node or result is not None:
            return
        inorder(node.left)
        count += 1
        if count == k:
            result = node.val
            return
        inorder(node.right)

    inorder(root)
    return result


# Lowest Common Ancestor in BST
# Exploit BST property: if both values < node, go left; both > node, go right.
def lowest_common_ancestor(root: TreeNode | None, p: int, q: int) -> TreeNode | None:
    while root:
        if p < root.val and q < root.val:
            root = root.left
        elif p > root.val and q > root.val:
            root = root.right
        else:
            return root  # split point = LCA
    return None


# Convert Sorted Array to Balanced BST
def sorted_array_to_bst(nums: list[int]) -> TreeNode | None:
    def build(lo: int, hi: int) -> TreeNode | None:
        if lo > hi:
            return None
        mid = (lo + hi) >> 1
        node = TreeNode(nums[mid])
        node.left = build(lo, mid - 1)
        node.right = build(mid + 1, hi)
        return node

    return build(0, len(nums) - 1)


# Examples (only run when executed directly)
if __name__ == "__main__":
    bst = BST()
    for value in [5, 3, 7, 1, 4, 6, 8]:
        bst.insert(value)
    print(bst.inorder())    # [1, 3, 4, 5, 6, 7, 8]
    print(bst.search(4))    # True
    print(bst.search(9))    # False

    bst.delete(3)
    print(bst.inorder())    # [1, 4, 5, 6, 7, 8]

    balanced = sorted_array_to_bst([1, 2, 3, 4, 5, 6, 7])
    print(is_valid_bst(balanced))     # True
    print(kth_smallest(balanced, 3))  # 3

Fenwick Tree

# DATA STRUCTURE: Fenwick Tree (Binary Indexed Tree / BIT)
# DIFFICULTY: Medium | FREQUENCY: Medium (prefix-sum + update problems; competitive rounds)

# A compact array-based structure for prefix-sum queries WITH point updates in O(log n).
# The simpler cousin of a Segment Tree: less code and memory, but sum-style (invertible)
# operations only. Each index i is responsible for a range of size (i & -i) - the lowest set bit.

# Time Complexity:
# - Build: O(n log n) (or O(n) with the linear build below)
# - Prefix sum / range sum query: O(log n)
# - Point update: O(log n)
# Space: O(n)

# When to use:
# - Prefix sums / range sums that change (point updates) - cumulative frequency, inversions.
# - Prefer over a Segment Tree when the op is a sum (or any invertible group op) - simpler, less memory.
# - Reach for a Segment Tree instead if you need min/max/gcd (non-invertible) or range updates.

# COMMON MISTAKES:
# - Off-by-one: the tree is 1-indexed internally; convert 0-indexed inputs.
# - Using it for min/max (not invertible) - range query by subtraction only works for sums.
# - Forgetting update() adds a DELTA, not sets a value (track current values if you need "set").

# RELATED PROBLEMS:
# - Range Sum Query - Mutable (LC 307)
# - Count of Smaller Numbers After Self (LC 315)
# - Reverse Pairs (LC 493)


class FenwickTree:
    def __init__(self, size: int) -> None:
        self.n = size
        self.tree: list[int] = [0] * (size + 1)  # 1-indexed

    @classmethod
    def from_array(cls, arr: list[int]) -> "FenwickTree":
        ft = cls(len(arr))
        for i, val in enumerate(arr):
            ft.update(i, val)
        return ft

    def update(self, i: int, delta: int) -> None:
        """Add `delta` at 0-indexed position i."""
        i += 1  # to 1-indexed
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)  # move to next responsible index

    def prefix_sum(self, i: int) -> int:
        """Sum of arr[0..i] inclusive (0-indexed)."""
        i += 1  # to 1-indexed
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & (-i)  # move to parent
        return total

    def range_sum(self, left: int, right: int) -> int:
        """Sum of arr[left..right] inclusive (0-indexed)."""
        if left > right:
            return 0
        if left == 0:
            return self.prefix_sum(right)
        return self.prefix_sum(right) - self.prefix_sum(left - 1)


if __name__ == "__main__":
    arr = [1, 7, 3, 0, 5, 8, 3, 2, 6, 2]
    ft = FenwickTree.from_array(arr)

    # prefix_sum(4) = 1+7+3+0+5 = 16
    print(ft.prefix_sum(4))            # 16
    # range_sum(2, 5) = 3+0+5+8 = 16
    print(ft.range_sum(2, 5))          # 16
    # range_sum(0, 9) = sum(arr) = 37
    print(ft.range_sum(0, 9))          # 37

    # Point update: add 4 at index 3 (0 -> 4)
    ft.update(3, 4)
    # range_sum(2, 5) now = 3+4+5+8 = 20
    print(ft.range_sum(2, 5))          # 20
    # prefix_sum(3) = 1+7+3+4 = 15
    print(ft.prefix_sum(3))            # 15

Segment Tree

# DATA STRUCTURE: Segment Tree
# DIFFICULTY: Hard | FREQUENCY: Medium (range query + update problems at Google/competitive rounds)

# A binary tree built on array segments for fast range queries and point updates.
# Each node stores aggregate info (sum, min, max) for a range of the array.

# Time Complexity:
# - Build: O(n)
# - Query: O(log n)
# - Update: O(log n)
# Space: O(4n) ~= O(n)

# When to use:
# - Range sum/min/max queries WITH updates
# - Need O(log n) per query AND per update
# - Alternatives: Fenwick Tree (simpler, sum only), Sparse Table (O(1) query, no updates)

# COMMON MISTAKES:
# - Under-sizing the tree array; 4*n is the safe bound.
# - Mixing up the no-overlap / complete-overlap / partial-overlap cases in query.
# - Forgetting to re-aggregate the parent after a child update.
# - Using the wrong identity value (0 for sum, +inf for min, -inf for max).

# RELATED PROBLEMS:
# - Range Sum Query - Mutable (LC 307)
# - Count of Smaller Numbers After Self (LC 315)
# - The Skyline Problem (LC 218)


class SegmentTree:
    def __init__(self, arr: list[int]) -> None:
        self.n = len(arr)
        self.tree: list[int] = [0] * (4 * self.n)
        if self.n > 0:
            self._build(arr, 0, 0, self.n - 1)

    def _build(self, arr: list[int], node: int, start: int, end: int) -> None:
        if start == end:
            self.tree[node] = arr[start]
            return

        mid = (start + end) >> 1
        self._build(arr, 2 * node + 1, start, mid)
        self._build(arr, 2 * node + 2, mid + 1, end)
        self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]

    # Point update: set arr[idx] = val
    def update(self, idx: int, val: int) -> None:
        self._update_helper(0, 0, self.n - 1, idx, val)

    def _update_helper(self, node: int, start: int, end: int, idx: int, val: int) -> None:
        if start == end:
            self.tree[node] = val
            return

        mid = (start + end) >> 1
        if idx <= mid:
            self._update_helper(2 * node + 1, start, mid, idx, val)
        else:
            self._update_helper(2 * node + 2, mid + 1, end, idx, val)

        self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]

    # Range sum query [l, r]
    def query(self, l: int, r: int) -> int:
        return self._query_helper(0, 0, self.n - 1, l, r)

    def _query_helper(self, node: int, start: int, end: int, l: int, r: int) -> int:
        # No overlap
        if r < start or end < l:
            return 0
        # Complete overlap
        if l <= start and end <= r:
            return self.tree[node]
        # Partial overlap
        mid = (start + end) >> 1
        return (self._query_helper(2 * node + 1, start, mid, l, r)
                + self._query_helper(2 * node + 2, mid + 1, end, l, r))


# Min Segment Tree variant
class MinSegmentTree:
    def __init__(self, arr: list[int]) -> None:
        self.n = len(arr)
        self.tree: list[float] = [float("inf")] * (4 * self.n)
        if self.n > 0:
            self._build(arr, 0, 0, self.n - 1)

    def _build(self, arr: list[int], node: int, start: int, end: int) -> None:
        if start == end:
            self.tree[node] = arr[start]
            return

        mid = (start + end) >> 1
        self._build(arr, 2 * node + 1, start, mid)
        self._build(arr, 2 * node + 2, mid + 1, end)
        self.tree[node] = min(self.tree[2 * node + 1], self.tree[2 * node + 2])

    def update(self, idx: int, val: int) -> None:
        self._update_helper(0, 0, self.n - 1, idx, val)

    def _update_helper(self, node: int, start: int, end: int, idx: int, val: int) -> None:
        if start == end:
            self.tree[node] = val
            return

        mid = (start + end) >> 1
        if idx <= mid:
            self._update_helper(2 * node + 1, start, mid, idx, val)
        else:
            self._update_helper(2 * node + 2, mid + 1, end, idx, val)

        self.tree[node] = min(self.tree[2 * node + 1], self.tree[2 * node + 2])

    def query(self, l: int, r: int) -> float:
        return self._query_helper(0, 0, self.n - 1, l, r)

    def _query_helper(self, node: int, start: int, end: int, l: int, r: int) -> float:
        if r < start or end < l:
            return float("inf")
        if l <= start and end <= r:
            return self.tree[node]
        mid = (start + end) >> 1
        return min(
            self._query_helper(2 * node + 1, start, mid, l, r),
            self._query_helper(2 * node + 2, mid + 1, end, l, r),
        )


# Examples (only run when executed directly)
if __name__ == "__main__":
    seg = SegmentTree([1, 3, 5, 7, 9, 11])
    print(seg.query(1, 3))   # 15 (3 + 5 + 7)
    seg.update(2, 10)        # change index 2 from 5 to 10
    print(seg.query(1, 3))   # 20 (3 + 10 + 7)

    min_seg = MinSegmentTree([2, 5, 1, 4, 9, 3])
    print(min_seg.query(0, 5))  # 1
    print(min_seg.query(3, 5))  # 3
    min_seg.update(2, 7)
    print(min_seg.query(0, 2))  # 2

Trie

# DATA STRUCTURE: Trie (Prefix Tree)
# DIFFICULTY: Medium | FREQUENCY: High (autocomplete, word search, prefix queries at Google/Amazon)

# A trie is a tree-like data structure that stores a dynamic set of strings, where the keys are
# usually strings. It is used for efficient retrieval of strings, especially for prefix-based searches.

# Time Complexity:
# - Insertion: O(m), where m is the length of the word being inserted.
# - Search: O(m), where m is the length of the word being searched.
# - Prefix Search: O(m), where m is the length of the prefix being searched.

# When to use:
# - When you need to store a large number of strings and perform quick lookups.
# - When you want to implement features like autocomplete or spell checking.
# - When you need to efficiently find all words with a given prefix.

# COMMON MISTAKES:
# - Confusing "word exists" (is_end flag) with "prefix exists" (node reachable).
# - Forgetting to set is_end at the end of insert.
# - Not handling the empty-string edge case.
# - Using a fixed-size array of 26 when the charset is unknown (a dict is safer/general).

# RELATED PROBLEMS:
# - Implement Trie (Prefix Tree) (LC 208)
# - Design Add and Search Words Data Structure (LC 211)
# - Word Search II (LC 212)
# - Replace Words (LC 648)


class TrieNode:
    def __init__(self) -> None:
        self.children: dict[str, "TrieNode"] = {}
        self.is_end = False
        self.word: str | None = None  # used by find_words (Word Search II) to stash the full word


class Trie:
    def __init__(self) -> None:
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                cur.children[ch] = TrieNode()
            cur = cur.children[ch]
        cur.is_end = True

    def search(self, word: str) -> bool:
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                return False
            cur = cur.children[ch]
        return cur.is_end

    def starts_with(self, prefix: str) -> bool:
        cur = self.root
        for ch in prefix:
            if ch not in cur.children:
                return False
            cur = cur.children[ch]
        return True


# === WORD SEARCH II (LC 212): trie + grid DFS ===
# Classic Google problem combining two structures already here. Build a trie of all words, then DFS
# the grid following only paths that exist in the trie (prunes dead branches early). Storing the full
# word on the terminal node avoids rebuilding strings during DFS.
def find_words(board: list[list[str]], words: list[str]) -> list[str]:
    root = TrieNode()
    for word in words:
        node = root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True
        node.word = word  # stash the word on the terminal node

    rows, cols = len(board), len(board[0])
    found: list[str] = []

    def dfs(r: int, c: int, node: TrieNode) -> None:
        ch = board[r][c]
        if ch not in node.children:
            return
        nxt = node.children[ch]
        if nxt.is_end:
            found.append(nxt.word)
            nxt.is_end = False  # dedupe: don't report the same word twice

        board[r][c] = "#"  # mark visited
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "#":
                dfs(nr, nc, nxt)
        board[r][c] = ch  # restore

    for r in range(rows):
        for c in range(cols):
            dfs(r, c, root)

    return found


# Examples (only run when executed directly)
if __name__ == "__main__":
    trie = Trie()
    trie.insert("apple")
    trie.insert("app")
    trie.insert("banana")

    print(trie.search("apple"))      # True
    print(trie.search("app"))        # True
    print(trie.search("ap"))         # False
    print(trie.starts_with("ap"))    # True
    print(trie.starts_with("ban"))   # True
    print(trie.starts_with("cat"))   # False

    # Word Search II
    board = [
        ["o", "a", "a", "n"],
        ["e", "t", "a", "e"],
        ["i", "h", "k", "r"],
        ["i", "f", "l", "v"],
    ]
    print(sorted(find_words(board, ["oath", "pea", "eat", "rain"])))  # ['eat', 'oath']