Hashing & Counting

At a glance

The instinct

Whenever a brute-force solution contains an inner loop whose only job is to find something (a complement, a duplicate, a previous position, a matching group), that inner loop can usually be replaced by a hash lookup. Hashing is the classic space-for-time trade: you spend O(n) memory so every "is it there?" or "how many?" question costs O(1) on average.

The pattern has three faces: membership (HashSet: seen it or not), frequency (HashMap or int[26]: how many), and grouping (HashMap from a canonical key to a list: which items belong together).

Recognise it

Not this pattern if...

• The input is sorted and you need a pair: two pointers give O(1) space.
• The question is about a contiguous window with a constraint: use Sliding Window (often with a map inside it).
• You need subarray sums: use Prefix Sum (whose fast version stores prefix values in a map).
• Order or nearest-greater queries matter: a map loses ordering; consider a TreeMap, heap or monotonic stack.

Memory hack

Say it out loud in the interview:

1. "The brute force has an inner loop that only searches, so I'll replace it with a hash lookup."
2. "What exactly is my key and what is my value: index, count, or list of items?"
3. "Do I check before I insert, or insert before I check?" (Decides whether an element can pair with itself.)

How it works

Walk the input once. For each element, first query the structure for whatever partner or history you need, then record the current element. The order of these two steps is what prevents an element from matching itself.

Trace for Two Sum on [2, 7, 11, 15], target 9:

For grouping (Group Anagrams), the trick is a canonical key: two strings belong together exactly when their keys are equal. Sorting the letters gives a key in O(k log k); a 26-slot count vector turned into a string gives one in O(k).

For Longest Consecutive Sequence, load everything into a set, then only start counting from values v where v - 1 is absent. Each value is visited at most twice overall, so the whole scan is O(n).

Java template

import java.util.*;

class HashingToolkit {
    // 1) Complement lookup: query first, then record.
    static int[] pairWithTarget(int[] nums, int target) {
        Map<Integer, Integer> seenAt = new HashMap<>();   // value -> index
        for (int i = 0; i < nums.length; i++) {
            Integer j = seenAt.get(target - nums[i]);      // problem-specific partner
            if (j != null) return new int[]{j, i};
            seenAt.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }

    // 2) Frequency table: int[26] for lowercase letters, HashMap otherwise.
    static boolean sameLetters(String a, String b) {
        if (a.length() != b.length()) return false;
        int[] cnt = new int[26];
        for (int i = 0; i < a.length(); i++) {
            cnt[a.charAt(i) - 'a']++;
            cnt[b.charAt(i) - 'a']--;
        }
        for (int c : cnt) if (c != 0) return false;
        return true;
    }

    // 3) Grouping by canonical key.
    static List<List<String>> groupBySignature(String[] words) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String w : words) {
            groups.computeIfAbsent(signature(w), k -> new ArrayList<>()).add(w);
        }
        return new ArrayList<>(groups.values());
    }

    static String signature(String w) {
        int[] cnt = new int[26];
        for (char c : w.toCharArray()) cnt[c - 'a']++;
        return Arrays.toString(cnt);                       // equal for equivalent items
    }

    // 4) Count pairs on the fly: each element pairs with all earlier equal ones.
    static long countEqualPairs(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        long pairs = 0;
        for (int x : nums) {
            int before = freq.getOrDefault(x, 0);
            pairs += before;
            freq.put(x, before + 1);
        }
        return pairs;
    }
}

Complexity

Note the space claim interviewers like to probe: a counter over lowercase letters is O(1), not O(n), because its size is bounded by the alphabet.

Variations

• Complement lookup: store what you've seen, search for what you need. Two Sum.
• Membership / duplicate detection: a set, or a map of last index for distance limits. Contains Duplicate, Contains Duplicate II.
• Frequency comparison: count one side, consume with the other. Valid Anagram, Ransom Note, Maximum Number of Balloons.
• Bijection checks: two maps (or two arrays) enforce one-to-one mapping. Isomorphic Strings.
• Canonical grouping: signature key to bucket. Group Anagrams.
• Set-based sequence building: start only at sequence heads. Longest Consecutive Sequence.
• Greedy with counts: Reorganize String (most frequent first), Split Array into Consecutive Subsequences (count map plus "needs" map).
• Implementing the structure itself: buckets and chaining. Design HashMap.

Common mistakes

• Inserting before checking in Two Sum, so nums[i] pairs with itself when target == 2 * nums[i].
• Using a HashMap<Character,Integer> when an int[26] would be faster, simpler and O(1) space.
• Using a mutable object (like an int[] or a List you keep changing) directly as a map key; arrays hash by identity, so convert to a String or immutable key.
• Forgetting getOrDefault or merge, causing a NullPointerException when unboxing a missing count.
• Assuming hash maps preserve insertion order; use LinkedHashMap if order matters.

All practice problems

16 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.