data-structures

What this skill does

# Data Structure Patterns

This skill provides recognition signals, core ideas, Python templates, and pitfall guidance for seven advanced data structure patterns. Use it when a problem's constraints or access patterns suggest a specialized structure beyond basic arrays, hash maps, or linked lists. Each pattern section follows a consistent format: when to reach for it, how it works, a clean implementation template, and the mistakes that cost time in practice.

---

## Pattern Recognition Table

| Trigger Signals | Technique | Typical Complexity |
|---|---|---|
| "k-th largest/smallest", "top K", "merge K sorted" | Heap / Priority Queue | O(n log k) |
| "next greater/smaller element", "sliding window max/min" | Monotonic Stack / Queue | O(n) |
| "prefix matching", "autocomplete", "word search in grid" | Trie | O(L) per operation |
| "range query + point update", "range min/max/sum" | Segment Tree | O(log n) per query/update |
| "prefix sums with updates", "count of elements less than X" | Fenwick Tree (BIT) | O(log n) per query/update |
| "balanced parentheses", "evaluate expression", "nested structures" | Stack-Based Parsing | O(n) |
| "rank of element", "k-th smallest in dynamic set", "floor/ceiling" | Ordered Set (SortedList) | O(log n) per operation |

---

## Constraint-to-Technique Mapping

When the problem statement does not name a structure directly, use constraints to narrow the choice:

- **n <= 10^5 with repeated range queries** -- Segment Tree or Fenwick Tree. Prefer Fenwick when only prefix sums are needed; use Segment Tree for arbitrary range operations.
- **n <= 10^6 and "next greater" or "span" language** -- Monotonic Stack. Linear time is essential at this scale.
- **String dictionary with prefix lookups** -- Trie. Hash maps work for exact match but not prefix enumeration.
- **"Top K" or "k-th element" with streaming data** -- Heap. A size-k heap avoids sorting the full dataset.
- **Dynamic insertions + rank/order queries** -- SortedList. Python lacks a built-in balanced BST; sortedcontainers fills this gap.
- **Nested or recursive syntax (math expressions, HTML tags)** -- Stack-Based Parsing. The stack mirrors the nesting depth.

---

### Heap / Priority Queue

**Recognition Signals**
- "Find the k-th largest/smallest element"
- "Merge k sorted lists/arrays"
- "Continuously add elements and query the median or top-K"
- "Schedule tasks by priority"

**Core Idea**
A heap maintains partial order so that the min (or max) element is always accessible in O(1) with O(log n) insertion and extraction. For "top K" problems, maintain a min-heap of size k: every new element either replaces the root or is discarded, guaranteeing O(n log k) total work.

**Python Template**

```python
import heapq
from typing import List

def top_k_frequent(nums: List[int], k: int) -> List[int]:
    from collections import Counter
    freq = Counter(nums)
    # Min-heap of size k on frequency
    return heapq.nlargest(k, freq.keys(), key=freq.get)

def merge_k_sorted(lists: List[List[int]]) -> List[int]:
    result: list[int] = []
    heap: list[tuple[int, int, int]] = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))
    while heap:
        val, list_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        if elem_idx + 1 < len(lists[list_idx]):
            heapq.heappush(heap, (lists[list_idx][elem_idx + 1], list_idx, elem_idx + 1))
    return result
```

**Key Edge Cases**
- Empty input lists or sublists in merge-k scenarios
- All elements identical (heap still works, but deduplication may be needed)
- k equals n (heap degenerates; sorting may be simpler)
- Negative numbers with max-heap emulation (negate values for `heapq`)

**Common Mistakes**
- Forgetting that Python's `heapq` is a min-heap; for max-heap, negate values or use `heapq.nlargest`
- Not including a tiebreaker index in the heap tuple, causing crashes on uncomparable objects
- Using `heapify` then manually inserting without `heappush` (breaks the heap invariant)

---

### Monotonic Stack / Queue

**Recognition Signals**
- "Next greater element" or "next smaller element"
- "Sliding window maximum/minimum"
- "Largest rectangle in histogram"
- "Daily temperatures / stock span"

**Core Idea**
A monotonic stack maintains elements in strictly increasing or decreasing order. When a new element arrives, pop all elements that violate the monotonic property -- each popped element has found its "next greater" (or "next smaller"). Every element is pushed and popped at most once, yielding O(n) total. For sliding windows, a monotonic deque adds front-eviction to maintain the window boundary.

**Python Template**

```python
from collections import deque
from typing import List

def next_greater_element(nums: List[int]) -> List[int]:
    n = len(nums)
    result = [-1] * n
    stack: list[int] = []  # indices
    for i in range(n):
        while stack and nums[stack[-1]] < nums[i]:
            result[stack.pop()] = nums[i]
        stack.append(i)
    return result

def sliding_window_max(nums: List[int], k: int) -> List[int]:
    dq: deque[int] = deque()  # indices, front = max
    result: list[int] = []
    for i, val in enumerate(nums):
        while dq and dq[0] <= i - k:
            dq.popleft()
        while dq and nums[dq[-1]] <= val:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result
```

**Key Edge Cases**
- Array with all equal elements (no element is "greater"; result is all -1)
- Single-element array (result is trivially -1)
- Circular array variant (iterate 2n elements using modular indexing)
- Window size k = 1 (output equals input)

**Common Mistakes**
- Storing values instead of indices on the stack (cannot determine window boundaries)
- Using the wrong comparison direction (< vs. <=) and getting a non-strictly monotonic stack
- Forgetting to handle the circular case by iterating `range(2 * n)`

---

### Trie

**Recognition Signals**
- "Find all words with a given prefix"
- "Word search in a 2D grid with a dictionary"
- "Autocomplete / typeahead suggestions"
- "Maximum XOR of two numbers in an array"

**Core Idea**
A trie stores strings character-by-character in a tree where each edge represents one character. Shared prefixes share nodes, making prefix lookups O(L) regardless of dictionary size. For XOR tries, store numbers bit-by-bit (MSB to LSB) and greedily choose the opposite bit at each level.

**Python Template**

```python
from typing import Optional

class TrieNode:
    __slots__ = ("children", "is_end", "count")
    def __init__(self) -> None:
        self.children: dict[str, "TrieNode"] = {}
        self.is_end: bool = False
        self.count: int = 0  # words passing through this node

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

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

    def starts_with(self, prefix: str) -> int:
        """Return count of words with given prefix."""
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return 0
            node = node.children[ch]
        return node.count
```

**Key Edge Cases**
- Empty string insertion (root itself becomes an end node)
- Prefix that is also a complete word (must check `is_end` separately from prefix existence)
- Unicode or case-sensitive input (normalize before insertion)
- Deletion requires decrementing counts and pruning childless nodes

**Common Mistakes**
- Not distinguishing "prefix exists" from "exact word exists" (missing `is_end` check)
- Building a trie for exact-match-only problems where a hash set suffices
- Forgetting `__slots__` on trie nodes, leading to high memory usage on