Knowing What to Track — How the Pattern Works
Knowing What to Track is a state-reduction pattern that replaces repeated input scans, pairwise comparisons, and combinatorial enumerations with compact summary state updated incrementally during a linear pass. By selecting the minimal lookup key (such as a character, canonical signature, modular remainder, or boundary index) and maintaining an invariant aggregate (frequency count, running sum, streak length, or difference mark), each step queries and updates prior history in O(1) time. This collapses brute-force O(n!), O(n^2), or O(n * q) procedures into O(n) or O(n log n) algorithms while bounding auxiliary memory by the key domain.
- Prompts asking whether two strings, sliding windows, or collections contain identical elements regardless of order, or whether a supply pool covers a target demand (anagrams, palindrome permutations, ransom notes).
- Pair-counting or partner-matching queries where each element x matches earlier elements satisfying an algebraic or structural relation such as (x + y) % k == 0 or mirror reversal w[::-1].
- Stateful data structures and online game/stream queries (such as n x n Tic-Tac-Toe win checks or a maximum-frequency stack) that must respond in O(1) time per update without rescanning history.
- Contiguous streak, balance-index, zigzag routing, or batch range-coverage problems where O(1) scalar variables or an O(n) difference array replace full substring enumeration or 2D grid materialization.
- Custom sorting or greedy cost-assignment problems where ordering depends on global occurrence counts or multi-rank vote vectors.
- Recording the current element in the frequency map before querying its complement in pair-counting problems, which falsely pairs an element with itself when key(x) == partner(x) (e.g., remainder 0 or 30 mod 60, or symmetric words like "cc").
- Iterating over hash map entries instead of re-scanning the input sequence when positional order matters (such as finding the earliest unique character), or skipping an upfront len(s) == len(t) check when only checking for negative counts in anagram tests.
- Off-by-one right boundaries in difference arrays: an inclusive query [left, right] must place -1 at index right + 1 (requiring an array of size n + 1), because placing -1 at right prematurely cancels coverage on index right.
- Neglecting structural boundary cases such as num_rows == 1 in Zigzag Conversion (where row-bounce logic steps out of bounds), empty prefix/suffix sums of 0 at array endpoints in Find Pivot Index, or adding more than one unpaired symmetric piece to a palindrome's center.
def check_supply_covers_demand(supply, demand):
count = {}
for x in supply:
count[x] = count.get(x, 0) + 1
for x in demand:
if count.get(x, 0) == 0:
return False
count[x] -= 1
return Truedef count_partner_pairs(items, key_fn, partner_fn):
seen = {}
pairs = 0
for x in items:
pairs += seen.get(partner_fn(x), 0)
k = key_fn(x)
seen[k] = seen.get(k, 0) + 1
return pairsdef count_run_boundary_matches(seq):
prev_run, cur_run, total = 0, 1, 0
for i in range(1, len(seq)):
if seq[i] == seq[i - 1]:
cur_run += 1
else:
prev_run, cur_run = cur_run, 1
if cur_run <= prev_run:
total += 1
return totaldef range_coverage(n, queries):
mark = [0] * (n + 1)
for left, right in queries:
mark[left] += 1
mark[right + 1] -= 1
cover, out = 0, [0] * n
for i in range(n):
cover += mark[i]
out[i] = cover
return out