Arrays, Strings, Hash Maps, And Frequency Counting

What's being tested

Array/string counting questions test whether you can turn brute-force comparisons into linear or near-linear passes using prefix/suffix state, two pointers, hash maps, and frequency vectors. Interviewers are probing correctness under duplicates, zeros, negative values, collisions, and boundary cases—not just happy-path O(n) code.

Patterns & templates

• Prefix/suffix accumulation — compute left-to-right and right-to-left products/counts in O(n) time; avoid division and handle zeros explicitly.

• Two-pointer scan on sorted arrays — move l/r based on sum comparison; skip duplicate values when returning unique pairs.

• Frequency map counting — use dict, HashMap, or Counter for character/item counts; compare vectors in O(k) where k is alphabet size.

• Fixed alphabet arrays — prefer int[26] or int[128] for lowercase/ASCII strings; faster and simpler than hash maps when domain is bounded.

• Partition state tracking — maintain left/right distinct-character counts as a split moves; update counts carefully when a frequency reaches zero.

• Modulo reasoning — maximize distinct remainders by tracking used residues in a set; remember residues range from 0 to k - 1.

• Hash map internals — know hashing, buckets, collisions, load factor, resizing, and worst-case O(n) lookup; mention concurrency concerns when relevant.

Common pitfalls

Pitfall: Using division in product-except-self fails when zeros appear and may violate the stated constraint.

Pitfall: Returning duplicate pairs from a sorted array because you advance pointers but do not skip repeated values.

Pitfall: Treating hash map operations as always O(1) without acknowledging collisions, resizing cost, and adversarial keys.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.