Arrays & Hashing
Trade memory for speed: a hash map or set answers 'have I seen this?' in O(1), so one pass can count, group, or match what nested loops would compare pair by pair.
Duplicate detection, complement lookups, frequency counts, grouping by a canonical key, and prefix sums or products over an array.
One pass over the input with an O(1) average lookup and insert per element. The map or set can grow to n entries. With a fixed alphabet, an int[26] count array brings space down to O(1), and string or tuple keys add a factor of the key length to both time and space.
The core move is trading memory for time. A nested loop answers "is there an earlier element that pairs with this one?" by rescanning everything seen so far, which is O(n^2). A hash map or hash set answers the same question in O(1) average time, so a single pass is enough. Two Sum stores each value's index and looks up target - value before inserting. Contains Duplicate asks whether the value is already in a set. Valid Anagram and First Unique Character count how often each character appears, and when the keys are a small fixed alphabet an int[26] array does the same job without any hashing. Roman to Integer (a small value table) and Fizz Buzz (one pass that builds the output array) belong here as warm-ups for the same habit of handling each element once.
When the question is "which items belong together?", compute a canonical key that is identical for every equivalent item and different for everything else. For anagrams that is the sorted letters or the 26 letter counts. A map from key to list then collects every group in one pass. The key must be hashable (a tuple or string, not a Python list or a raw Java array) and cheap to build, because building it is usually the real cost: n strings of length k take O(n * k), not O(n). Sets also answer structural questions. In Longest Consecutive Sequence, checking whether x - 1 is present tells you whether x starts a run, which keeps the whole count linear.
Prefix sums turn range questions into lookups. With prefix[i] as the total of the first i elements, the sum of nums[i..j] is prefix[j + 1] - prefix[i]. Pair the running prefix with a map of how many times each earlier prefix occurred, and you can count subarrays that sum to k in one pass, even with negative numbers, where a sliding window breaks. Prefix and suffix products do the same job for Product of Array Except Self and avoid division entirely. The common thread across all of these is deciding exactly what to remember about each element so you never have to look back.
A hash map answers 'have I already seen the value I need?' in O(1) average time, so any problem that compares each element against earlier ones drops from O(n^2) to O(n), as long as you can name exactly what to look up: a complement, a canonical key, or an earlier prefix sum.
- Using an unhashable or identity-hashed key: Python lists can't be dict keys and Java int[] arrays hash by reference, so grouping by them silently fails. Convert to a tuple or string first.
- Inserting the current element before looking up its complement, so Two Sum pairs an element with itself, or a prefix-sum count with k = 0 includes the empty subarray.
- Forgetting to seed a prefix-sum map with {0: 1}, which misses every subarray that starts at index 0.
- Treating hash operations as free: they are O(1) on average, but building a string or tuple key costs its length, so grouping n strings of length k is O(n * k).
- Iterating the raw array instead of the deduplicated set when each element triggers extra work, which repeats the same scan for every duplicate (Longest Consecutive Sequence).
- Complement lookup: Two Sum; check for target - value, then store the value and its index.
- Frequency counting: Valid Anagram, First Unique Character, Top K Frequent; use int[26] when the alphabet is fixed.
- Grouping by canonical key: Group Anagrams, with sorted letters or a letter-count tuple as the key.
- Prefix sums and products: Subarray Sum Equals K (running sum plus a count map), Product of Array Except Self (prefix times suffix, no division).
// import java.util.*;
// Lookup pass: ask before you insert.
Map<Integer, Integer> seen = new HashMap<>(); // value -> index or count
// for prefix-sum counting, seed with seen.put(0, 1)
for (int i = 0; i < n; i++) {
int need = /* complement, canonical key, or prefix - k */ 0;
if (seen.containsKey(need)) {
// match found: combine with seen.get(need)
}
seen.put(nums[i], i); // record the current element after the lookup
}
// Grouping pass: bucket items by a canonical key.
Map<String, List<String>> groups = new HashMap<>();
for (String item : items) {
String key = /* canonical form of item */ item;
groups.computeIfAbsent(key, k -> new ArrayList<>()).add(item);
}
return new ArrayList<>(groups.values());Problems using this pattern
11Easiest first · Blind 75 above NeetCode 150