Dashboard/Coding patterns/24. Knowing What to Track

CODING PATTERNS · LESSON 24 OF 28 · 74 MIN VIDEO · 25 PROBLEMS

Knowing What to Track

Module Progress (0 / 25 Problems Solved)0%
Coding patterns Track (0 / 28 Modules) · Overall 0/80 (0%)0%
⌁

Narrated HD Video Lesson (74 min) · Pro

Pattern Guide + Problem #01 + Checkpoint Quiz #1 are unlocked free below (no login required). Unlock all 80 HD video lessons and all 540 Python problems — or watch our two free sample video lessons first.

PATTERN STUDY GUIDE

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.

WHEN TO USE THIS PATTERN
  • 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.
COMMON INTERVIEW PITFALLS
  • 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.
Frequency Map / Supply-and-Demand TallyWhen element order does not matter and validity depends on matching or bounding character/item multiplicities.
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 True
Single-Pass Complement / Partner CountingWhen counting or pairing index pairs (i, j) with i < j by querying already-seen partner keys before recording the current element.
def 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 pairs
Adjacent Run-Length Scalar StateWhen valid substrings, streaks, or RLE encodings depend only on the active contiguous run and at most the immediately preceding run.
def 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 total
Difference Array for Batch Range CoverageWhen applying q uniform increments across inclusive intervals [left, right] and evaluating per-index coverage in O(n + q) time.
def 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
🔒 PRO PROBLEMTarget: O(n log n) time · O(n) space

21. Sort Array by Increasing Frequency

Problem #01 of every pattern lesson is unlocked free outside the paywall. Unlock all 540 Python 3.14 problems, step-by-step solution editorials, and 80 narrated HD video lessons with Monthly ($69), 3-Month ($149), or Annual ($299) access — or 50% off for verified university students.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

We count the letters of banana. How many keys end up in the table?