Counting

Topic type: Technique-Based
LeetCode tag size: ~200+ problems → depth: all variants, all advanced techniques, full edge-case and pitfall coverage

This file covers the counting technique: how to count occurrences, frequencies, and satisfying-subsets efficiently. It does not duplicate combinatorial formulas (C(n,k), stars & bars, inclusion-exclusion) — those live in combinatorics.md and math.md. It does not duplicate prefix-sum-based counting — that lives in prefix-sum.md. This file focuses on the practical coding pattern of building and querying frequency structures.

---

Core Concepts

Frequency map (counter) — a mapping from each distinct value to its number of occurrences in a collection. Building costs O(n); querying any key costs O(1) amortized. The canonical tool for "how many times does X appear?"

Frequency array — a fixed-size integer array indexed by value (character ordinal, digit, bounded integer) used instead of a hash map when the value domain is small and dense. Faster in practice than a hash map due to cache locality and no hashing overhead.

Counting sort prerequisite — when values are bounded integers in [0, k), a frequency array of size k enables O(n + k) sorting or O(1) range-count queries after O(n) build. Distinct from comparison-based sorting.

Running count — maintaining a count variable (or map) that is updated incrementally as a window slides or a traversal proceeds, rather than rebuilt from scratch. Enables O(1) per step.

Difference of counts — a technique that reduces "exactly k" queries to "at most k" minus "at most k-1". Useful when "at most k" is easier to implement (e.g., sliding window) but "exactly k" is asked.

Contribution counting — instead of iterating over all pairs/subsets and checking a property, assign each element a contribution to the answer based on its frequency or rank. Reduces O(n²) enumeration to O(n) in many problems.

Majority element — an element occurring more than ⌊n/2⌋ times. Boyer-Moore Voting extends this to the top-2 candidates with O(1) space. Generalizes to elements occurring more than ⌊n/k⌋ times with k−1 candidates.

---

Types / Variants

---

Key Algorithms

Build Frequency Map

Iterate once, incrementing counts. — O(n) time, O(d) space where d = number of distinct values.

from collections import Counter
freq = Counter(arr)  # or: freq = {}; for x in arr: freq[x] = freq.get(x, 0) + 1

Sliding Window with Frequency Map

Maintain a frequency map for the current window; when a constraint (distinct count, max frequency, etc.) is violated, shrink the left pointer while updating counts. Delete zero-count entries to keep len(freq) accurate. — O(n) time, O(k) space where k = window size or alphabet size.

freq = {}; l = 0
for r, c in enumerate(s):
    freq[c] = freq.get(c, 0) + 1
    while <invariant broken>: freq[s[l]] -= 1; (freq.pop(s[l]) if freq[s[l]] == 0 else None); l += 1

Exactly-K via At-Most-K Subtraction

Define atmost(k) = count of subarrays where the property holds for at most k distinct/odd/etc. values. Then exactly(k) = atmost(k) - atmost(k-1). — Reduces to two O(n) sliding window calls.

Boyer-Moore Voting (Majority Element)

Maintain a candidate and a count; increment count when the next element matches the candidate, decrement when it differs; reset the candidate when count hits 0. The surviving candidate is the majority if one exists; verify with a second pass. — O(n) time, O(1) space.

Top-K Frequent Elements (Bucket Sort)

Count frequencies, then place elements into buckets indexed by frequency (bucket[freq] = list of elements). Read buckets from highest to lowest to collect top-k. — O(n) time, O(n) space; avoids heap's O(n log k).

buckets = [[] for _ in range(len(arr) + 1)]
for val, cnt in Counter(arr).items(): buckets[cnt].append(val)

Counting Inversions (Merge Sort / BIT)

An inversion is a pair (i, j) with i < j but arr[i] > arr[j]. Count by combining merge sort's merge step (count right-side elements that land before left-side) or using a BIT to query how many previously seen values are larger than the current. — O(n log n) time.

Anagram / Permutation Check via Frequency Array

Build a frequency array of size 26 for both strings; compare in O(1) using equality. For sliding window anagram search, maintain a running frequency array and a count of "satisfied" positions. — O(n) total after O(k) window setup.

need = Counter(p); have = Counter(); matches = 0

Frequency of Frequencies

Build a secondary map freq_of_freq[c] = number of elements with count c. Used in problems asking "can one deletion make all frequencies equal?" — O(n) build, O(1) per condition check.

---

Advanced Techniques

Contribution Counting (element-centric summation)

What it solves: "Sum/count over all subarrays/pairs" where iterating pairs is O(n²).
Mechanism: For each element (or pair), compute how many subarrays/pairs it appears in or contributes to, using its left and right boundaries. Multiply element value by its contribution count and sum.
When to use over brute force: When the answer can be decomposed as a sum of per-element contributions and boundaries can be computed in O(n) (often via monotonic stack for nearest-smaller/larger).
Complexity: O(n) time; O(n) space for boundary arrays.

Frequency Map + Sliding Window (at-most-k distinct)

What it solves: Longest subarray/substring with at most k distinct values, or with max frequency ≤ threshold.
Mechanism: Two-pointer window; shrink left when len(freq) > k or when max_freq * window_len > window_len + replacements.
When to use over DP: When the array/string is processed left-to-right and the window constraint degrades monotonically — sliding window is O(n) vs. DP's O(n²).
Complexity: O(n) time, O(k) space.

Difference of Counts (Exactly-K Pattern)

What it solves: "Number of subarrays with exactly k [odd elements / distinct values / elements equal to x]."
Mechanism: exactly(k) = atmost(k) - atmost(k-1); implement atmost once using a sliding window and call it twice.
When to use over direct counting: When "exactly k" breaks the sliding window monotonicity (removing an element can both add and remove constraint satisfaction), but "at most k" is monotone.
Complexity: O(n) with two passes.

Frequency of Frequencies for One-Edit Validity

What it solves: "Can removing exactly one element make all remaining elements have equal frequency?"
Mechanism: Build freq[val] then freq_of_freq[c]. Check the five valid configurations: all count = 1; all count = max and only one distinct value; one element appears once (removable outlier); one element has max+1 and max+1 = 1; all equal count and n+1 total frequencies.
When to use over simulation: Direct simulation is O(n log n) due to resorting after removal; frequency-of-frequency check is O(n) with O(1) case analysis.
Complexity: O(n) time, O(d) space.

Hash Map Counting + Binary Search (count pairs/subarrays meeting a threshold)

What it solves: "Count pairs (i, j) with arr[i] + arr[j] = target", "count subarrays with product < k".
Mechanism: Sort + binary search for pair counting on unbounded ranges; hash map for exact-sum pairs. For products, use two pointers on the sorted array or logarithms to reduce multiplication to addition.
When to use over two pointers: When duplicates are present and counting distinct pairs vs. index pairs differs, or when the array is unsorted and sorting changes problem semantics.
Complexity: O(n log n) with sorting + binary search; O(n) with hash map for exact pairs.

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Forgetting to delete zero-count entries in sliding window. When the frequency of a character drops to 0, leaving the key in the map inflates len(freq) (the distinct count), causing the window to shrink unnecessarily. Always del freq[k] or call freq.pop(k) when the count hits 0.

• At-most-k called with k = 0. If atmost(0) is not handled, atmost(k) - atmost(k-1) calls atmost(-1) which may produce nonsensical results or index errors. Guard with if k < 0: return 0.

• Boyer-Moore Voting does not guarantee the candidate is the majority. The algorithm finds the candidate that would survive if a majority exists. If no element appears more than n/2 times, the candidate is arbitrary. A second verification pass is required when majority existence is not guaranteed.

• Bucket sort frequency array bounds. buckets[count[val]] requires the array to be of size n+1 (counts range from 1 to n). Allocating n causes an index-out-of-bounds when every element is identical (count = n).

• Contribution counting with equal elements. When multiple elements have the same value, contribution formulas based on "left boundary = nearest strictly smaller" versus "nearest smaller or equal" determine whether each pair is counted once or twice. Be consistent: use strict on one side, non-strict on the other.

• Counter update order for complement lookup. In pair-counting with a hash map (count pairs with a + b = target), checking freq[target - x] before inserting x avoids counting a pair of the same index twice. Inserting first and then checking double-counts self-pairs.

• Frequency of frequencies with a single distinct value. If all elements are equal, freq = {v: n} and fof = {n: 1}. The one-removal checks must handle this case: valid only if n = 1 (remove the only element) or the single frequency is 1 (remove any one copy to reach frequency 0, but that leaves an empty set).

• Max-frequency sliding window with character replacement. The invariant max_freq + k >= window_len uses the historical maximum of max_freq, not the true current maximum, which can only shrink the window but never invalidate it. This is intentional and correct: the window never needs to shrink below the best seen so far.

• Integer constraints: count can equal 0 vs. key absent. Counter and defaultdict(int) return 0 for missing keys; plain dict raises KeyError. Mixing these in one function causes silent errors on first-seen keys.

---

Implementation Notes

• Python collections.Counter supports arithmetic: Counter(a) - Counter(b) drops zero and negative counts, useful for set-difference frequency problems. Counter(a) & Counter(b) gives element-wise minimum (intersection).
• Counter.most_common(k) returns the top-k elements in O(n) using a heap internally; do not re-sort the full Counter just for top-k.
• Counter.update(iterable) adds counts (not replaces); Counter.subtract(iterable) decrements (allows negative counts, unlike subtraction operator).
• For fixed-alphabet frequency arrays, [0] * 26 with ord(c) - ord('a') indexing is faster than a dict for dense alphabets; the 26-length array comparison arr1 == arr2 in Python is O(26) = O(1).
• The running-max-frequency trick in the character replacement sliding window (max_freq = max(max_freq, freq[c])) intentionally does not recompute the true max when shrinking; Python's max(freq.values()) inside the loop would be O(26) = O(1) for bounded alphabets but adds constant factor.
• collections.defaultdict(int) avoids get(k, 0) boilerplate; use it in preference to plain dict when all values are counts.
• For very large n with bounded values (digits 0–9), a length-10 list beats a dict by a wide margin in constant factor.
• Python recursion limit (default 1000) is irrelevant for iterative counting patterns; only relevant if implementing merge sort recursively for inversion counting (use iterative bottom-up merge sort or sys.setrecursionlimit).

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

Frequency Fundamentals

• Majority Element (LC 169) — Boyer-Moore Voting
• Majority Element II (LC 229) — two-candidate Boyer-Moore
• Top K Frequent Elements (LC 347) — Counter + heap or bucket sort
• Sort Characters By Frequency (LC 451) — bucket sort by frequency
• First Unique Character in a String (LC 387) — frequency array then scan

Sliding Window + Frequency Map

• Longest Substring Without Repeating Characters (LC 3) — frequency map, shrink on duplicate
• Longest Substring with At Most K Distinct Characters (LC 340) — sliding window + delete-on-zero
• Longest Repeating Character Replacement (LC 424) — running max-frequency trick
• Find All Anagrams in a String (LC 438) — fixed-size sliding window, frequency array match count
• Permutation in String (LC 567) — same as LC 438 with boolean output
• Minimum Window Substring (LC 76) — need/have counter with formed count

Exactly-K Pattern

• Subarrays with K Different Integers (LC 992) — exactly-k = atmost-k minus atmost-(k-1)
• Count Number of Nice Subarrays (LC 1248) — remap odd→1, even→0; exactly-k prefix count
• Binary Subarrays With Sum (LC 930) — exactly-k prefix count or difference

Frequency Validity and Rearrangement

• Unique Number of Occurrences (LC 1207) — all counts distinct
• Maximum Frequency of an Element After Performing Operations (LC 2190)
• Task Scheduler (LC 621) — ceil formula using max frequency
• Reorganize String (LC 767) — greedy with max frequency ≤ ⌈n/2⌉
• Find Minimum Number of Operations to Make Array Continuous (LC 2009)

Contribution and Pair Counting

• Sum of Subarray Minimums (LC 907) — contribution counting + monotonic stack
• Sum of Subarray Ranges (LC 2104) — min/max contribution combined
• Count of Range Sum (LC 327) — merge sort + inversion-count style
• Count Number of Bad Pairs (LC 2364) — complement map: remap arr[i]-i
• Number of Good Pairs (LC 1512) — C(freq, 2) contribution per value

Hard

• Count Subarrays Where Max Element Appears at Least K Times (LC 2962) — sliding window with count of max
• Frequency of the Most Frequent Element (LC 1838) — sliding window with prefix sum
• Make Array Zero by Subtracting Equal Amounts (LC 2357) — count distinct non-zero values

Clarification Questions to Ask

• What is the value range? (Determines hash map vs. fixed-size array)
• Are elements guaranteed to be positive, or can they be zero/negative? (Affects complement lookup and sliding window assumptions)
• Does "subarray" mean contiguous? (Prefix-frequency and sliding window apply only to contiguous subarrays)
• Is "distinct" by value or by index? (Pair counting: do (i, j) and (j, i) count separately?)
• When asking for "at most k distinct", can k be 0? (Guard atmost(-1) in the exactly-k pattern)
• Is the answer guaranteed to exist (e.g., majority element always present), or must we verify?
• Are counts expected modulo a prime? (Affects whether to use Python's arbitrary-precision Counter or modular arithmetic)

Common Interview Mistakes

• Not deleting zero-count keys from the sliding window frequency map, causing len(freq) to over-count distinct values and producing a window that is too narrow.
• Using Boyer-Moore Voting without a verification pass when the problem does not guarantee a majority exists — the algorithm always produces a candidate, not a guaranteed majority.
• Implementing exactly-k by trying to shrink/expand a single window directly, rather than the clean atmost(k) - atmost(k-1) decomposition.
• Using max(freq.values()) inside a loop when len(freq) is bounded (alphabet size), which is O(1) but adds unnecessary constant factor — prefer tracking max_freq with a running update.
• Checking freq[target - x] after inserting x into the map, which counts a pair (x, x) as valid even when the problem requires two different indices.
• Building the full frequency map upfront for a sliding window problem, then trying to update it — the window should build the map incrementally as it expands.
• Forgetting that Counter.subtract allows negative counts while Counter.__sub__ drops them — using the wrong one silently discards information.
• Allocating buckets[0..n-1] instead of buckets[0..n] for bucket-sort-by-frequency, causing an index error when all elements are identical (count = n).

Typical Follow-Up Escalations

• "Now support updates to the array." → Frequency map alone is insufficient; combine with a Binary Indexed Tree or Segment Tree for O(log n) point updates and range-count queries.
• "Find the majority element in a data stream." → Boyer-Moore Voting works in a single pass; keep running candidate and count, then verify over the full stream.
• "What if k = 0 in the exactly-k subarrays problem?" → atmost(0) - atmost(-1); define atmost(-1) = 0 explicitly.
• "Extend to 2D: count rectangles in a matrix with exactly k distinct values." → Fix top and bottom rows, reduce each column pair to a 1D exactly-k subarray problem; O(n² · m) total.
• "Do it in O(1) space." → Boyer-Moore for majority; for top-k, Space-Saving algorithm (streaming approximate top-k) replaces Counter; exact O(1)-space top-k is not possible in general.
• "Count subarrays with frequency of any element ≥ k." → Binary search on the answer or sliding window with a count of elements whose frequency meets the threshold.