Introduction to Counting Pattern

Counting works by trading a second linear pass (or nested pairwise comparisons) for a single pass plus O(1)-amortized lookups into a hash map or fixed-size array, so you can answer "how many", "which one is most/least frequent", or "does any value exceed a threshold" without re-scanning the collection for every element.

Recognize the pattern

• The question asks for a frequency, a majority/mode, a duplicate, an anagram/permutation check, or "count elements satisfying condition X".
• Your first instinct is an O(n²) nested loop comparing every pair of elements.
• The value range is small and bounded (lowercase letters, digits 0-9) — a hint that a fixed-size array can replace a hash map for a constant-factor speedup.
• Order does not matter, only how many times each distinct value occurs.

Brute force → optimal

Brute force: for each character, scan the remaining string and count matches. Left as-is, this is O(n²) time, O(1) space — but it will re-report the same tally once per occurrence (e.g. it prints "s appears 4 times" four separate times for "mississippi", once per each 's'). To report each distinct character exactly once, you additionally track which characters have already been tallied in a seen-set, which costs O(k) extra space (k = distinct characters) on top of the same O(n²) time. So the O(1)-space brute force and the O(k)-space brute force are the same nested-loop core with or without duplicate-suppression bookkeeping — neither changes the O(n²) time bound.

Optimal (counting pattern): a single pass where each character looks up and increments its own slot in a hash map (or a 26-length int array for lowercase letters). Both operations are O(1) amortized, so the whole scan is O(n).

Complexity, derived

Time: the loop body runs exactly n times (once per input character). Each iteration performs one map get and one put/array increment, each O(1) amortized — array indexing is O(1) worst-case, which is exactly why bounded-alphabet problems prefer arrays over hash maps. Total work = n × O(1) = O(n).

Space: the map stores at most one entry per distinct value. If k is the number of distinct characters, space is O(k); in the worst case (all characters unique) k = n, so space is O(n). With a fixed alphabet of size 26, space collapses to O(1) regardless of n.

Traced example: count("mississippi")

Final: {m:1, i:4, s:4, p:2} after exactly 11 O(1) steps.

Java: character frequency count

import java.util.LinkedHashMap;
import java.util.Map;

public class CharFrequency {
    public static Map<Character, Integer> countChars(String s) {
        Map<Character, Integer> freqMap = new LinkedHashMap<>();
        for (char c : s.toCharArray()) {
            freqMap.merge(c, 1, Integer::sum); // O(1) amortized get+put
        }
        return freqMap;
    }

    public static void main(String[] args) {
        System.out.println(countChars("mississippi"));
        // {m=1, i=4, s=4, p=2}
    }
}

Go: character frequency count

package main

import "fmt"

func countChars(s string) map[rune]int {
	freq := make(map[rune]int)
	for _, c := range s {
		freq[c]++ // O(1) amortized read-modify-write
	}
	return freq
}

func main() {
	fmt.Println(countChars("mississippi"))
	// map[i:4 m:1 p:2 s:4]
}

Pitfalls

• Mutating while iterating: modifying a hash map's keys while iterating over it (e.g. in Java's for-each) throws ConcurrentModificationException; increment values only, never add/remove keys mid-loop.
• Off-by-one on missing keys: forgetting to default a missing key to 0 before incrementing causes a NullPointerException (Java Map<K,Integer> unboxing) — use merge/getOrDefault or Go's zero-value default.
• Assuming hash map O(1) is worst-case: with adversarial input or poor hashing it degrades to O(n) per operation; for small fixed alphabets, an array sidesteps this entirely.
• Case/locale sensitivity: "A" and "a" hashing to different keys silently doubles counts unless the problem intends case sensitivity.

When to use / when not — trade-offs

Use counting when you need frequencies, duplicates, majority elements, or condition-based tallies over an unordered collection. It beats the nested-loop brute force (O(n²) time, O(1) space, or O(n²) time and O(k) space if you add a seen-set to suppress duplicate reports) by trading extra space for guaranteed O(n) time — almost always a win unless memory is the binding constraint and k is close to n.

Compare to sorting-then-scanning (e.g. to find duplicates or the majority element): sorting costs O(n log n) time. Space depends on the sort: an iterative in-place sort like heapsort is O(1) extra space, but the common in-place choices (quicksort, introsort) recurse and typically cost O(log n) stack space, not true O(1). Counting instead costs O(n) time but O(k) space. Choose sorting when memory is scarce and the log n time overhead (and log n stack space, if using quicksort/introsort) is acceptable; choose counting when you need true linear time and can afford the map/array.

Do not reach for counting when element order or adjacency matters (use sliding window / two pointers instead), or when the value range is enormous and sparse with few repeats (a hash map's overhead may not pay off vs. a direct comparison approach).

Takeaways

• Counting converts repeated re-scanning into one pass plus O(1) amortized map/array operations: O(n²) → O(n).
• Space cost is O(k) for k distinct values; bounded alphabets let you use a fixed array for O(1) space and guaranteed O(1) worst-case access.
• It is the workhorse behind anagram checks, majority element, duplicate detection, and top-k frequency problems.
• It composes with sorting, heaps, and sliding windows — recognizing "I need to know how many of each" is the trigger to reach for it.

Recall question: Why does switching from a HashMap<Character,Integer> to a fixed int[26] array for lowercase-only input improve worst-case time complexity, not just constant factors?

Synthesized from the original counting-pattern walkthrough plus standard interview-prep treatments of hashing-based counting (frequency maps, majority element, anagram detection) and complexity analysis by first principles.