High-Frequency Hash Table Patterns

Core Value of Hash Tables

The primary value of hash tables is the Time-Space trade-off: converting O(n) search/de-duplication operations into O(1).

Common Java Operations:

// HashMap - Key-Value Mapping
Map<Integer, Integer> map = new HashMap<>();
map.put(key, value);
map.getOrDefault(key, 0);
map.containsKey(key);
map.merge(key, 1, Integer::sum);  // Ideal for frequency counting

// HashSet - De-duplication / Existence Checks
Set<Integer> set = new HashSet<>();
set.add(val);
set.contains(val);
set.remove(val);

Counting Patterns

Contains Duplicate (LeetCode 217)

boolean containsDuplicate(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int num : nums) {
        // add() returns false if the element was already present
        if (!seen.add(num)) return true;
    }
    return false;
}

Group Anagrams (LeetCode 49)

Use the sorted string as a key to group all anagrams:

List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    for (String s : strs) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(map.values());
}

Optimization: Use a frequency array (int[26]) converted to a string (Arrays.toString(freq)) as the key to avoid the O(L log L) sorting cost.

Top K Frequent Elements (LeetCode 347)

Count frequencies, then use a min-heap to maintain the top k:

int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> countMap = new HashMap<>();
    for (int n : nums) countMap.merge(n, 1, Integer::sum);

    // Min-Heap ordered by frequency
    PriorityQueue<Integer> pq = new PriorityQueue<>(
        (a, b) -> countMap.get(a) - countMap.get(b)
    );
    
    for (int key : countMap.keySet()) {
        pq.offer(key);
        // Maintain heap size k; smallest frequency is polled
        if (pq.size() > k) pq.poll();
    }

    int[] res = new int[k];
    for (int i = k - 1; i >= 0; i--) res[i] = pq.poll();
    return res;
}

Mapping Patterns

Two Sum (LeetCode 1)

Checking for the complement while iterating is faster than nested loops:

int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[]{map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    return new int[]{};
}

Isomorphic Strings (LeetCode 205)

Mapping s[i] -> t[i] must be a bijection (one-to-one):

boolean isIsomorphic(String s, String t) {
    Map<Character, Character> sToT = new HashMap<>();
    Map<Character, Character> tToS = new HashMap<>();
    for (int i = 0; i < s.length(); i++) {
        char a = s.charAt(i), b = t.charAt(i);
        // Check if existing mapping contradicts current characters
        if (sToT.containsKey(a) && sToT.get(a) != b) return false;
        if (tToS.containsKey(b) && tToS.get(b) != a) return false;
        
        sToT.put(a, b);
        tToS.put(b, a);
    }
    return true;
}

Interval and Continuity Patterns

Longest Consecutive Sequence (LeetCode 128)

Store all values in a HashSet. Only initiate counting from the sequence start (where n-1 is absent).

int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int n : nums) set.add(n);

    int maxLen = 0;
    for (int n : set) {
        // Only trigger search if 'n' is the start of a sequence
        if (!set.contains(n - 1)) {
            int currentNum = n;
            int currentLen = 1;
            while (set.contains(currentNum + 1)) {
                currentNum++;
                currentLen++;
            }
            maxLen = Math.max(maxLen, currentLen);
        }
    }
    return maxLen;
}

Complexity: O(n). Although nested, each number is visited exactly once via the while loop across the entire process.

Selection Suggestions