# Data Structures > >- - **Type:** Skill - **Install:** `agentstack add skill-sequenzia-agent-alchemy-data-structures` - **Verified:** Yes — security-reviewed for prompt injection and unsafe behavior - **Seller:** [sequenzia](https://agentstack.voostack.com/s/sequenzia) - **Installs:** 0 - **Category:** [Agent Skills](https://agentstack.voostack.com/c/agent-skills) - **Latest version:** 0.1.0 - **License:** MIT - **Upstream author:** [sequenzia](https://github.com/sequenzia) - **Source:** https://github.com/sequenzia/agent-alchemy/tree/main/claude/cs-tools/skills/data-structures - **Website:** https://sequenzia.github.io/agent-alchemy ## Install ```sh agentstack add skill-sequenzia-agent-alchemy-data-structures ``` Requires the [AgentStack CLI](https://agentstack.voostack.com/docs/cli). Works with Claude Code, Cursor, and any MCP-compatible agent. ## About # 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 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 List[int]: n = len(nums) result = [-1] * n stack: list[int] = [] # indices for i in range(n): while stack and nums[stack[-1]] List[int]: dq: deque[int] = deque() # indices, front = max result: list[int] = [] for i, val in enumerate(nums): while dq and dq[0] = 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 ( 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 large dictionaries --- ### Segment Tree **Recognition Signals** - "Range sum/min/max query with point updates" - "Count of elements in a range satisfying a condition" - "Range update + range query" (lazy propagation) **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** ```python 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 >= 1 right >>= 1 return res ``` **Key Edge Cases** - Single-element array (tree has two levels; queries are trivial) - Query range equals the full array (should return root value) - Index-0 vs. index-1 conventions (this template uses 0-indexed input) - Overflow on large sums (use Python's arbitrary-precision integers or explicit modular arithmetic) **Common Mistakes** - Off-by-one in the query range (half-open `[left, right)` vs. closed `[left, right]`) - Forgetting to propagate lazy values before accessing children in lazy segment trees - Building with `2 * n` size but using 1-indexed logic (need `4 * n` for 1-indexed recursive style) --- ### Fenwick Tree (BIT) **Recognition Signals** - "Prefix sum queries with dynamic updates" - "Count of elements less than X after insertions" - "Inversion count in an array" - "2D prefix sums with updates" **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** ```python 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 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** - Zero-indexed input (convert to 1-indexed before calling update/query) - Querying index 0 (should return 0, which the while loop handles naturally) - Negative values in updates (Fenwick handles deltas, not absolute values) **Common Mistakes** - Using 0-indexed positions (index 0 causes an infinite loop in `update` because `0 & (-0) == 0`) - Confusing "set value" with "add delta" (Fenwick stores cumulative deltas, not absolute values) - Forgetting that `range_query(1, 0)` should return 0 (guard against inverted ranges) --- ### Stack-Based Parsing **Recognition Signals** - "Check if parentheses/brackets are balanced" - "Evaluate arithmetic expression with operator precedence" - "Decode nested encoded strings like `3[a2[c]]`" - "Basic calculator with +, -, *, /, and parentheses" **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** ```python 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** - Empty string (should be considered balanced / evaluate to 0) - Unary minus at the start of an expression (e.g., `-3 + 5`) - Deeply nested structures that could overflow recursion (iterative stack avoids this) **Common Mistakes** - Not handling multi-digit numbers (accumulate digits before processing operators) - Forgetting to process the last number after the loop ends (no trailing operator triggers it) - Popping from an empty stack on mismatched closing brackets (check `len(stack)` first) --- ### Ordered Set (SortedList) **Recognition Signals** - "Find the k-th smallest element in a dynamic collection" - "Count elements in a range [lo, hi] with insertions and deletions" - "Floor/ceiling of a value in a dynamic set" - "Sliding window median" **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** ```python 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 int: """Count elements in [lo, hi] inclusive.""" return sl.bisect_right(hi) - sl.bisect_left(lo) ``` **Key Edge Cases** - Duplicate values (SortedList allows duplicates; use `discard` to remove one occurrence, not all) - Empty collection (bisect returns 0; floor/ceiling should return None) - Value exactly equal to an existing element (floor and ceiling are both that element) - Large n with frequent add/remove (handles 10^5-10^6 operations efficiently) **Common Mistakes** - Using `remove` on a value not in the list (raises ValueError; use `discard` for safe removal) - Confusing `bisect_left` and `bisect_right` for floor/ceiling logic (left for ceiling, right for floor) - Assuming SortedList is available everywhere (some contest judges lack `sortedcontainers`; have a BIT fallback) ## Source & license This open-source skill is cataloged on AgentStack and links to its original source — we do not rehost the code. - **Author:** [sequenzia](https://github.com/sequenzia) - **Source:** [sequenzia/agent-alchemy](https://github.com/sequenzia/agent-alchemy) - **License:** MIT - **Homepage:** https://sequenzia.github.io/agent-alchemy Install and usage instructions live in the source repository linked above. ## Pricing - **Free** — Free ## Security capabilities Automated source analysis of v0.1.0 — what this tool can access: - **Network access:** no - **Filesystem access:** no - **Shell / process execution:** no - **Environment & secrets:** no - **Dynamic code execution:** no *"Yes" means the capability is present in the source — more access means more to trust, not that it is unsafe.* ## Versions - **0.1.0** — security scan: passed — Imported from the upstream source. ## Links - Listing page: https://agentstack.voostack.com/l/skill-sequenzia-agent-alchemy-data-structures - Seller: https://agentstack.voostack.com/s/sequenzia - Browse the marketplace: https://agentstack.voostack.com/browse --- Listed on AgentStack — the marketplace for AI agent skills and MCP servers. Every listing is security-reviewed. Creators keep 70%.