Reference for advanced data structure patterns used in competitive programming and technical interviews. Covers heaps, monotonic stacks, tries, segment trees, Fenwick trees, stack-based parsing, and ordered sets with Python templates, recognition signals, and edge case guidance.
Provides Python templates and recognition signals for advanced data structures like segment trees, tries, and monotonic stacks.
/plugin marketplace add sequenzia/agent-alchemy/plugin install agent-alchemy-cs-tools@agent-alchemyThis skill inherits all available tools. When active, it can use any tool Claude has access to.
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.
| 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 |
When the problem statement does not name a structure directly, use constraints to narrow the choice:
Recognition Signals
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
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
heapq)Common Mistakes
heapq is a min-heap; for max-heap, negate values or use heapq.nlargestheapify then manually inserting without heappush (breaks the heap invariant)Recognition Signals
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
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
Common Mistakes
range(2 * n)Recognition Signals
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
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
is_end separately from prefix existence)Common Mistakes
is_end check)__slots__ on trie nodes, leading to high memory usage on large dictionariesRecognition Signals
Core Idea A segment tree is a binary tree where each leaf represents one element and each internal node stores an aggregate (sum, min, max) of its children's range. Queries and updates both traverse O(log n) nodes. Lazy propagation defers range updates by tagging nodes, applying pending updates only when a child is accessed, keeping range updates at O(log n).
Python Template
from typing import List
class SegmentTree:
"""Range sum query with point update."""
def __init__(self, data: List[int]) -> None:
self.n = len(data)
self.tree = [0] * (2 * self.n)
# Build leaves
for i in range(self.n):
self.tree[self.n + i] = data[i]
# Build internal nodes
for i in range(self.n - 1, 0, -1):
self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
def update(self, idx: int, val: int) -> None:
idx += self.n
self.tree[idx] = val
while idx > 1:
idx >>= 1
self.tree[idx] = self.tree[2 * idx] + self.tree[2 * idx + 1]
def query(self, left: int, right: int) -> int:
"""Sum of data[left:right] (half-open interval)."""
res = 0
left += self.n
right += self.n
while left < right:
if left & 1:
res += self.tree[left]
left += 1
if right & 1:
right -= 1
res += self.tree[right]
left >>= 1
right >>= 1
return res
Key Edge Cases
Common Mistakes
[left, right) vs. closed [left, right])2 * n size but using 1-indexed logic (need 4 * n for 1-indexed recursive style)Recognition Signals
Core Idea
A Fenwick tree (Binary Indexed Tree) uses the binary representation of indices to partition prefix sums across O(log n) nodes. Each node at index i stores the sum of a range whose length equals the lowest set bit of i. Updates and prefix queries both run in O(log n). Fenwick trees use less memory and have smaller constants than segment trees but only support prefix-based queries natively. Range [l, r] is computed as prefix(r) - prefix(l - 1).
Python Template
from typing import List
class FenwickTree:
def __init__(self, n: int) -> None:
self.n = n
self.tree = [0] * (n + 1) # 1-indexed
def update(self, i: int, delta: int) -> None:
"""Add delta to element at 1-indexed position i."""
while i <= self.n:
self.tree[i] += delta
i += i & (-i)
def query(self, i: int) -> int:
"""Return prefix sum from index 1 to i (inclusive)."""
s = 0
while i > 0:
s += self.tree[i]
i -= i & (-i)
return s
def range_query(self, left: int, right: int) -> int:
"""Sum of elements in [left, right], 1-indexed."""
return self.query(right) - self.query(left - 1)
@classmethod
def from_array(cls, data: List[int]) -> "FenwickTree":
ft = cls(len(data))
for i, val in enumerate(data, 1):
ft.update(i, val)
return ft
Key Edge Cases
Common Mistakes
update because 0 & (-0) == 0)range_query(1, 0) should return 0 (guard against inverted ranges)Recognition Signals
3[a2[c]]"Core Idea A stack naturally mirrors nesting depth: push context when entering a deeper level (opening bracket, new sub-expression) and pop when leaving it (closing bracket, operator resolution). For expression evaluation, use two stacks (operands and operators) or convert to reverse Polish notation first. The stack preserves the outer context while you process the inner context; restoring is a simple pop.
Python Template
from typing import List
def eval_expression(s: str) -> int:
"""Evaluate expression with +, -, and parentheses."""
stack: list[tuple[int, int]] = [] # (result_before_paren, sign_before_paren)
result = 0
num = 0
sign = 1
for ch in s:
if ch.isdigit():
num = num * 10 + int(ch)
elif ch in "+-":
result += sign * num
num = 0
sign = 1 if ch == "+" else -1
elif ch == "(":
stack.append((result, sign))
result = 0
sign = 1
elif ch == ")":
result += sign * num
num = 0
prev_result, prev_sign = stack.pop()
result = prev_result + prev_sign * result
result += sign * num
return result
def is_balanced(s: str) -> bool:
"""Check if brackets are balanced."""
pairs = {"(": ")", "[": "]", "{": "}"}
stack: list[str] = []
for ch in s:
if ch in pairs:
stack.append(pairs[ch])
elif ch in pairs.values():
if not stack or stack.pop() != ch:
return False
return len(stack) == 0
Key Edge Cases
-3 + 5)Common Mistakes
len(stack) first)Recognition Signals
Core Idea
Python lacks a built-in balanced BST, but sortedcontainers.SortedList provides O(log n) insertion, deletion, and index-based access with excellent constant factors. It supports bisect for floor/ceiling, positional indexing for rank queries, and islice for range iteration. For contest environments without third-party imports, a Fenwick tree over a value-indexed array can simulate rank queries.
Python Template
from sortedcontainers import SortedList
from typing import List, Optional
def sliding_window_median(nums: List[int], k: int) -> List[float]:
sl = SortedList()
result: list[float] = []
for i, val in enumerate(nums):
sl.add(val)
if len(sl) > k:
sl.remove(nums[i - k])
if len(sl) == k:
if k % 2 == 1:
result.append(float(sl[k // 2]))
else:
result.append((sl[k // 2 - 1] + sl[k // 2]) / 2.0)
return result
def floor_ceiling(sl: SortedList, val: int) -> tuple[Optional[int], Optional[int]]:
"""Return (floor, ceiling) of val in the sorted list."""
idx = sl.bisect_right(val)
floor = sl[idx - 1] if idx > 0 else None
ceil_idx = sl.bisect_left(val)
ceiling = sl[ceil_idx] if ceil_idx < len(sl) else None
return floor, ceiling
def count_in_range(sl: SortedList, lo: int, hi: int) -> int:
"""Count elements in [lo, hi] inclusive."""
return sl.bisect_right(hi) - sl.bisect_left(lo)
Key Edge Cases
discard to remove one occurrence, not all)Common Mistakes
remove on a value not in the list (raises ValueError; use discard for safe removal)bisect_left and bisect_right for floor/ceiling logic (left for ceiling, right for floor)sortedcontainers; have a BIT fallback)Activates when the user asks about AI prompts, needs prompt templates, wants to search for prompts, or mentions prompts.chat. Use for discovering, retrieving, and improving prompts.
Search, retrieve, and install Agent Skills from the prompts.chat registry using MCP tools. Use when the user asks to find skills, browse skill catalogs, install a skill for Claude, or extend Claude's capabilities with reusable AI agent components.
This skill should be used when the user asks to "create an agent", "add an agent", "write a subagent", "agent frontmatter", "when to use description", "agent examples", "agent tools", "agent colors", "autonomous agent", or needs guidance on agent structure, system prompts, triggering conditions, or agent development best practices for Claude Code plugins.