Skip to content

Agent Evolved (English)

🎯 How to use this map (fast)

  • Start from API Kernels β†’ pick a pattern β†’ solve the mapped problems
  • Keep one invariant per pattern: expand (add right / go deeper) then contract (move left / undo)
  • Sliding window mental model (copy this into code)
  • Outer loop advances R (expand via on_enter(R))
  • Inner loop advances L while invariant violated (maximize/exist) or while window valid (minimize)
  • Each pointer moves monotonically (L and R each increase ≀ n)
  • Progress tracking
  • Finish all Easy anchors
  • Finish all Medium anchors
  • Finish at least 3 Hard anchors
  • Legend
  • πŸ”₯ must-know (FAANG frequent)
  • ⭐ common
  • 🧊 nice-to-know

🧠 Big Picture: From Technique β†’ Kernel β†’ Pattern β†’ Problem

  • Technique (e.g., Two Pointers)
  • API Kernel (reusable β€œengine”, e.g., SubstringSlidingWindow)
    • Pattern (invariant + state)
    • LeetCode {number} (practice + recognition)

βœ… Decision table: signal β†’ kernel

Signal Use this kernel
Contiguous subarray/substring + constraint/invariant SubstringSlidingWindow
Sorted array + pair/tuple constraints TwoPointersTraversal
Cycle/middle on linked list or function iteration FastSlowPointers
Merge K sorted streams/lists KWayMerge
Grid shortest time / distance transform (multi-source) GridBFSMultiSource
Monotone predicate over index/value BinarySearchBoundary

🧩 Sequences / arrays / strings

πŸͺŸ SubstringSlidingWindow (API Kernel)

  • Inputs: string/array; contiguous window; often k, target, or required frequency map
  • Output shape: max/min length, boolean exists, indices, list of start positions
  • Invariant: window property holds under expand/contract transitions
  • Failure modes / when not to use: sum/cost constraints typically require non-negative numbers (monotone expansion); if negatives exist, use prefix sums + hash/balanced tree depending on query
  • Summary: 1D window state machine over sequences with dynamic invariants
  • Cost model: each index moves monotonically (L and R each increase ≀ n), so pointer work is \(O(n)\). Map/counter ops add expected \(O(1)\) per update (hashing) or \(O(\log \sigma)\) if balanced tree.
  • State toolbelt: hash_map / counter, sometimes integer sum
  • Standard hooks: on_enter(right), on_exit(left), is_valid(), score(window)
  • Example use in production: rate-limit / anomaly detection over event streams; log scanning for minimal covering window

πŸ§ͺ Sliding window pseudocode template (hooks)

L = 0
for R in range(n):
  on_enter(R)
  while invariant_violated():   # or while is_valid() for "minimize while valid"
    on_exit(L); L += 1
  ans = score(ans, L, R)        # update max/min/exist/output
return ans

βœ… Pattern comparison table (must-know)

Problem Invariant State Window Size Goal
πŸ”₯ LeetCode 76 - Minimum Window Substring Β· Solution (H) - Minimum Window Substring covers all of t need/have maps variable minimize
πŸ”₯ LeetCode 3 - Longest Substring Without Repeating Characters Β· Solution (M) - Longest Substring Without Repeating Characters all unique last_index map variable maximize
⭐ LeetCode 438 - Find All Anagrams in a String · Solution (M) - Find All Anagrams in a String exact multiset match freq + matched count fixed all positions
⭐ LeetCode 567 - Permutation in String · Solution (M) - Permutation in String exact multiset match freq + matched count fixed exists
⭐ LeetCode 340 - Longest Substring with At Most K Distinct Characters Β· Solution (H) - Longest Substring with At Most K Distinct Characters ≀ K distinct freq map variable maximize
⭐ LeetCode 209 - Minimum Size Subarray Sum Β· Solution (M) - Minimum Size Subarray Sum sum β‰₯ target integer sum variable minimize

sliding_window_unique

  • Invariant: no duplicates in window
  • State: last_seen_index[char] (jump-left optimization)
  • Approach A: last seen index jump-left (\(O(n)\), simpler)
  • Approach B: freq map shrink-left (also \(O(n)\), more uniform template)
  • Anchor problems
  • πŸ”₯ LeetCode 3 - Longest Substring Without Repeating Characters Β· Solution (M) - Longest Substring Without Repeating Characters

sliding_window_at_most_k_distinct

sliding_window_freq_cover

  • Invariant: window meets required frequencies
  • State: need_frequency, have_frequency, chars_satisfied

sliding_window_min_cover

  • Invariant: valid cover holds
  • State: need_frequency, have_frequency, chars_satisfied
  • Loop: expand to become valid β†’ contract while valid to minimize
  • Anchor problems
  • πŸ”₯ LeetCode 76 - Minimum Window Substring Β· Solution (H) - Minimum Window Substring

sliding_window_fixed_match

sliding_window_fixed_size

sliding_window_cost_bounded

  • Invariant: sum/cost constraint satisfied
  • State: integer window_sum
  • Requires: monotone expansion property (typically non-negative numbers)
  • See also: Prefix sums (negatives break sliding window)
  • Anchor problems
  • ⭐ LeetCode 209 - Minimum Size Subarray Sum Β· Solution (M) - Minimum Size Subarray Sum

πŸ‘ˆπŸ‘‰ TwoPointersTraversal (API Kernel)

  • Inputs: array/string; often sorted; sometimes target sum / tuple constraints
  • Output shape: max/min value, boolean exists, indices, list of tuples
  • Invariant: pointer moves preserve feasibility region / dedup rules
  • Failure modes / when not to use: unsorted + pair sum usually needs hashmap; opposite-pointers assumes sorted/monotone movement is valid
  • Summary: traverse with two coordinated pointers under invariant-preserving rules
  • Core promise: each index moves monotonically (L and R each increase ≀ n), so pointer work is \(O(n)\)
  • Example use in production: stable in-place filtering/compaction; scanning sorted logs/ids

πŸ§ͺ Two pointers pseudocode template (hooks)

L, R = ...
while L < R:
  if should_move_L(): L += 1
  elif should_move_R(): R -= 1
  else: record_answer(); move_and_dedup()

βœ… Two pointers pattern comparison table

Pattern Init Movement Typical invariant Time Space
Opposite 0, n-1 toward center lies within [L,R] \(O(n)\) \(O(1)\)
Writer write=0, read=0 both forward a[0:write] is β€œkept” \(O(n)\) \(O(1)\)
Dedup enumeration i + (L,R) nested + skips unique tuples only \(O(n^2)\) \(O(1)\)

two_pointer_opposite_maximize

two_pointer_three_sum (dedup enumeration)

  • Recipe: sort β†’ fix i β†’ opposite pointers β†’ skip duplicates
  • Notes
  • Sorting cost: \(O(n \log n)\), then scan is \(O(n^2)\)
  • Duplicate skipping: skip i if nums[i]==nums[i-1]; after finding a hit, move L/R past equal values
  • Output size can dominate runtime (many triples) even if pointer work is \(O(n^2)\)
  • Anchor problems
  • πŸ”₯ LeetCode 15 - 3Sum Β· Solution (M) - 3Sum
  • ⭐ LeetCode 16 - 3Sum Closest Β· Solution (M) - 3Sum Closest

two_pointer_writer_dedup (same-direction)

two_pointer_writer_remove (same-direction)

two_pointer_writer_compact (same-direction)

two_pointer_opposite_palindrome

two_pointer_opposite_search (sorted array)

🧱 TwoPointerPartition (API Kernel)

  • Inputs: array; predicate/pivot; in-place rearrangement
  • Output shape: partitioned array, pivot index, kth element
  • Invariant: elements are maintained in partition regions
  • Failure modes / when not to use: quickselect worst-case without randomization; stability not guaranteed
  • Summary: partition array using two pointers (Dutch flag, quickselect)

πŸ§ͺ Partition pseudocode template (2-way)

i = 0
for j in range(n):
  if predicate(a[j]):
    swap(a[i], a[j]); i += 1
return i  # boundary

dutch_flag_partition

two_way_partition

quickselect_partition

  • Goal: kth element without full sort (avg \(O(n)\))
  • Note: random pivot (or shuffle) to avoid adversarial worst-case; deterministic median-of-medians is overkill for interviews
  • See also: HeapTopK (alternative for kth/top-k), same partition routine powers quicksort/quickselect
  • Anchor problems
  • πŸ”₯ LeetCode 215 - Kth Largest Element in an Array Β· Solution (M) - Kth Largest Element in an Array

πŸ”Ž BinarySearchBoundary (API Kernel)

  • Inputs: sorted array or monotone predicate over index/value space
  • Output shape: index boundary, boolean, minimal feasible value
  • Invariant: predicate is monotone; search interval maintains β€œanswer inside”
  • Failure modes / when not to use: predicate not monotone; mid bias mistakes cause infinite loops/off-by-one
  • Summary: boundary binary search (first true / last true) + answer-space search
  • When it fits: predicate is monotone over index or value space

πŸ§ͺ Binary search template (with mid bias note)

# first_true
l, r = 0, n-1
while l < r:
  m = (l + r) // 2          # bias left
  if pred(m): r = m
  else: l = m + 1
return l

# last_true: use m = (l + r + 1) // 2  (bias right) to ensure progress

binary_search_rotated

binary_search_first_last_position

binary_search_on_answer

πŸ“š MonotonicStack (API Kernel)

  • Inputs: array (often temperatures/prices/heights); queries about next/previous greater/smaller
  • Output shape: next/prev index/value, spans, max area
  • Invariant: stack indices maintain monotone order (increasing/decreasing)
  • Failure modes / when not to use: use wrong monotone direction; forget to flush stack at end; equal-handling matters
  • Summary: stack maintaining monotonic order for next-greater/smaller queries
  • Typical queries: next greater/smaller, previous smaller/greater, span, histogram max rectangle
  • State: stack of indices (values accessed via array)
  • Example use in production: range-based alerting, stock span analytics, histogram-like dashboards

πŸ§ͺ Monotonic stack pseudocode template

st = []  # indices
for i in range(n):
  while st and violates_monotone(a[st[-1]], a[i]):
    j = st.pop()
    answer_for(j, i)
  st.append(i)
flush_remaining(st)

monotonic_next_greater

histogram_max_rectangle

βž• PrefixSumHash (API Kernel)

  • Inputs: array; sums/zero-one transforms; can handle negatives
  • Output shape: count of subarrays, max length, boolean exists
  • Invariant: prefix sums accumulated; hashmap stores earliest index / counts
  • Failure modes / when not to use: beware overflow in other languages; choose earliest vs counts depending on query
  • Summary: prefix sum + hash map for subarray sum / balance conditions
  • Example use in production: telemetry windows with negatives; anomaly β€œnet change” queries

πŸ§ͺ Prefix sum + hash template

seen = {0: 1}     # or {0: -1} for longest-length variants
prefix = 0
for x in nums:
  prefix += x
  ans += seen.get(prefix - target, 0)
  seen[prefix] = seen.get(prefix, 0) + 1
return ans

prefix_sum_subarray_sum_equals_k

prefix_sum_longest_balance

πŸ”— Linked lists

πŸ”€ MergeSortedSequences (API Kernel)

  • Inputs: two sorted linked lists/arrays; possibly in-place merge
  • Output shape: merged sequence/list
  • Invariant: output prefix is fully merged and sorted
  • Failure modes / when not to use: if not sorted, need sort or different approach
  • Summary: merge two sorted sequences using two pointers
  • When it wins: stable linear merge, \(O(m+n)\)

πŸ§ͺ Merge pseudocode template

dummy = Node()
tail = dummy
while a and b:
  take smaller; tail.next = taken; tail = tail.next
tail.next = a or b
return dummy.next

merge_two_sorted_lists

merge_two_sorted_arrays

merge_sorted_from_ends

πŸ’πŸ‡ FastSlowPointers (API Kernel)

  • Inputs: linked list or implicit function next(x)
  • Output shape: boolean cycle, node (cycle start), midpoint, palindrome check helper
  • Invariant: fast moves 2 steps, slow moves 1 step; meeting implies cycle
  • Failure modes / when not to use: pointer null checks; list mutation can break assumptions
  • Summary: two pointers at different speeds for cycle detection / midpoint
  • Key theorem: if a cycle exists, fast meets slow in \(O(n)\)

πŸ§ͺ Fast/slow template

slow = fast = head
while fast and fast.next:
  slow = slow.next
  fast = fast.next.next
  if slow == fast: cycle_found

fast_slow_cycle_detect

fast_slow_cycle_start

fast_slow_implicit_cycle

fast_slow_midpoint

fast_slow_palindrome_via_reverse

πŸ” LinkedListReversal (API Kernel)

  • Inputs: singly linked list; segment bounds or group size k
  • Output shape: new head (and/or modified list)
  • Invariant: reversed prefix points back to previous nodes; remaining suffix preserved
  • Failure modes / when not to use: off-by-one around segment boundaries; losing next pointer; restoring list if required
  • Summary: in-place reversal via pointer surgery (local rewiring)

πŸ§ͺ Reverse template (iterative)

prev = None
cur = head
while cur:
  nxt = cur.next
  cur.next = prev
  prev = cur
  cur = nxt
return prev

linked_list_full_reversal

linked_list_partial_reversal

linked_list_k_group_reversal

πŸ”οΈ Heaps / selection / merging streams

🧺 KWayMerge (API Kernel)

  • Inputs: K sorted lists/arrays/streams
  • Output shape: merged sorted output / single list
  • Invariant: heap contains next candidate from each list (or each non-empty list)
  • Failure modes / when not to use: forgetting to push next after pop; unstable if you need stable tie-breaking
  • Summary: merge K sorted sequences using heap or divide-and-conquer
  • Two standard strategies
  • Min-heap: push heads, pop+advance β‡’ \(O(N \log K)\)
  • Divide & conquer: pairwise merge β‡’ \(O(N \log K)\)
  • Example use in production: merge sorted shard results; streaming merge in search/index pipelines
  • See also: HeapTopK (same heap mechanics)

πŸ§ͺ K-way merge (heap) template

heap = []
push (value, list_id, node_ptr) for each non-empty list
while heap:
  v, i, node = heappop(heap)
  output.append(v)
  if node.next: heappush(heap, (node.next.val, i, node.next))
return output

merge_k_sorted_heap

merge_k_sorted_divide

merge_two_sorted (also appears in answer-space problems)

πŸ”οΈ HeapTopK (API Kernel)

  • Inputs: stream/array; k; sometimes comparator
  • Output shape: kth element or list of top-k
  • Invariant: heap stores current best candidates (size ≀ k)
  • Failure modes / when not to use: using wrong heap orientation; forgetting to cap size k
  • Summary: maintain top K / kth using heap
  • Rule of thumb
  • min_heap of size K for top K largest
  • max_heap of size K for top K smallest
  • Anchor problems
  • πŸ”₯ LeetCode 215 - Kth Largest Element in an Array Β· Solution (M) - Kth Largest Element in an Array (dual-approach: heap vs quickselect)
  • ⭐ LeetCode 347 - Top K Frequent Elements (M) - Top K Frequent Elements

🌐 Graph / grid

🌊 GridBFSMultiSource (API Kernel)

  • Inputs: grid; multiple starting cells (β€œsources”)
  • Output shape: minimum time/steps to reach all, distance matrix, or unreachable indicator
  • Invariant: queue holds frontier of increasing distance (unweighted); first time visiting a cell is shortest time
  • Failure modes / when not to use: marking visited late (on dequeue) causes duplicates; miscounting levels/time
  • Summary: multi-source BFS wavefront propagation on grid graph
  • State: queue, visited, distance/time layers
  • Example use in production: propagation in grids: distance transforms, flood fill of influence

πŸ§ͺ Multi-source BFS template

q = deque(all_sources)
mark visited on enqueue
dist = 0
while q:
  for _ in range(len(q)):     # level by level
    r,c = q.popleft()
    for nr,nc in neighbors(r,c):
      if not visited:
        visited = True
        q.append((nr,nc))
  dist += 1

grid_bfs_propagation

🚦 GraphBFSShortestPath (API Kernel)

  • Inputs: graph (adjacency list); unweighted edges; start/target
  • Output shape: shortest distance, path length, or path reconstruction
  • Invariant: queue holds frontier of increasing distance; first time reaching node is shortest
  • Failure modes / when not to use: weighted edges need Dijkstra; visited-on-enqueue to avoid blowup
  • Summary: BFS shortest path on general graphs (not just grids)

πŸ§ͺ Graph BFS template

q = deque([start])
dist = {start: 0}
while q:
  u = q.popleft()
  if u == target: return dist[u]
  for v in adj[u]:
    if v not in dist:
      dist[v] = dist[u] + 1
      q.append(v)
return -1

bfs_shortest_path

🧭 Search / enumeration

🧭 BacktrackingExploration (API Kernel)

  • Inputs: choice set / constraints; often need all solutions
  • Output shape: list of solutions, count, or boolean exists
  • Invariant: state matches current path exactly
  • Failure modes / when not to use: missing pruning causes exponential blowups; duplicates without dedup rules
  • Summary: exhaustive search with pruning; rhythm: Choose β†’ Explore β†’ Unchoose
  • Note: most backtracking is exponential; win condition is pruning/constraints; be ready to justify pruning and bounds

πŸ§ͺ Backtracking template

def dfs(state):
  if is_solution(state): record; return
  for choice in choices(state):
    apply(choice)
    if feasible(state): dfs(state)
    undo(choice)

βœ… Backtracking β€œshape” cheat sheet

Shape What you track Canonical trick Anchor
Permutation used[] each element once πŸ”₯ LeetCode 46 - Permutations Β· Solution (M) - Permutations
Permutation + dup used[] + sort skip if prev unused ⭐ LeetCode 47 - Permutations II · Solution (M) - Permutations II
Subset start_index collect every node ⭐ LeetCode 78 - Subsets · Solution (M) - Subsets
Subset + dup start_index + sort same-level skip ⭐ LeetCode 90 - Subsets II · Solution (M) - Subsets II
Combination start_index + size stop when size==k ⭐ LeetCode 77 - Combinations · Solution (M) - Combinations
Target sum remaining prune remaining<0 ⭐ LeetCode 39 - Combination Sum · Solution (M) - Combination Sum /40/216
Constraint sat. constraint sets propagate constraints πŸ”₯ LeetCode 51 - N-Queens Β· Solution (H) - N-Queens /52
Grid path visited mark undo on return ⭐ LeetCode 79 - Word Search · Solution (M) - Word Search
String cuts cut positions validate segment ⭐ LeetCode 93 - Restore IP Addresses · Solution (M) - Restore IP Addresses /131

backtracking_permutation

backtracking_permutation_dedup

backtracking_subset

backtracking_subset_dedup

backtracking_combination

backtracking_n_queens (constraint satisfaction)

backtracking_grid_path

backtracking_string_segmentation

🌳 Trees / DFS

🌲 DFSTraversal (API Kernel)

  • Inputs: tree (binary/n-ary) or grid/graph for DFS-style traversal
  • Output shape: aggregated value (height), boolean, paths, component count, LCA node
  • Invariant: recursion/stack maintains call path; each node processed once (tree) or once with visited (graph)
  • Failure modes / when not to use: missing visited in graphs; recursion depth in deep trees
  • Summary: depth-first traversal patterns (preorder/inorder/postorder), plus common queries

πŸ§ͺ Tree DFS template

def dfs(node):
  if not node: return base
  left = dfs(node.left)
  right = dfs(node.right)
  return combine(node, left, right)

dfs_tree_height

dfs_invert_tree

dfs_island_counting

dfs_lca

πŸ”— Compositions (kernels used together)

  • Sort + TwoPointersTraversal (3Sum)
  • TwoPointerPartition + HeapTopK (hybrid selection/top-k workflows)
  • BFS + BinarySearchBoundary (time feasibility via predicate; common in scheduling variants)

🧩 Starter Packs (pick one roadmap slice)

🎯 Sliding Window Track (~6 problems, 2–4 hours)

πŸ‘ˆπŸ‘‰ Two Pointers & Partition Track (~8 problems, 2–4 hours)

🧭 Backtracking Track (~6–8 problems, 2–4 hours)

πŸ”— Linked List Track (~6–8 problems, 2–4 hours)

πŸ”οΈ Heap & Merge Track (~6–8 problems, 2–4 hours)

βœ… Ontology kernels not yet in this map (TODO)

  • UnionFindConnectivity
  • TreeTraversalBFS
  • DPSequence
  • DPInterval
  • TopologicalSort
  • TriePrefixSearch

🧾 Still to add (scope reminders)

  • DP, Union-Find, Trie, Segment Tree/Fenwick, Topological sort, Dijkstra