← All patterns

Tracking Patterns

Run a rolling aggregation (sum, count, last-seen index) over a stream and test it against a target. A cousin of hash maps that emphasizes mutable state over time.

18 problems 7 Easy 8 Medium 3 Hard

Run a rolling aggregation (sum, count, last-seen index, mod state) over a stream and look up the aggregate's history in a hash map. Strongly tied to prefix sums: 'subarray with sum k' becomes 'have I seen `prefix - k` before?'. Modular variants enable 'subarray sum divisible by k'.

The `{0: -1}` seed is the canonical bookkeeping for 'prefix matched from the very start'.

When to reach for this pattern

  • Subarray / substring with sum / count property
  • Running aggregate that, when seen twice, tells you something
  • Modular-arithmetic constraints over running sums
  • Find anchors by index or value with hash-key lookup

Canonical template 

// subarray sum equals k — count
unordered_map<int, int> freq{{0, 1}};
int prefix = 0, count = 0;
for (int x : nums) {
    prefix += x;
    if (auto it = freq.find(prefix - k); it != freq.end()) count += it->second;
    ++freq[prefix];
}

// longest subarray with sum k — earliest-seen prefix
unordered_map<int, int> firstSeen{{0, -1}};
int prefix = 0, best = 0;
for (int i = 0; i < (int)nums.size(); ++i) {
    prefix += nums[i];
    auto it = firstSeen.find(prefix - k);
    if (it != firstSeen.end()) best = max(best, i - it->second);
    firstSeen.try_emplace(prefix, i);
}

C++ · adapt the names and types to your problem.

Common pitfalls

  • Forgetting the {0: -1} (or {0: 1}) seed — misses subarrays starting from index 0
  • Modular hashing: negative-mod handling in C++ (((x % k) + k) % k)
  • Updating the map before vs after the lookup — depends on whether equal indices count
  • Storing first-seen vs all-occurrences — depends on whether 'longest' or 'count' is wanted

Related patterns

Hash Maps Sliding Window Two Pointers

Problems (18)

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.