Arrays & Hashing Pattern

The Arrays & Hashing pattern uses hash sets or hash maps to store intermediate values during traversal, transforming linear scan operations into constant-time lookups.

Recognition Signals

You should consider this pattern if you see any of the following cues in the problem description:

• The problem asks about frequency, counting, duplicates, or existence (e.g. “does this element appear”, “how many times”, “is there a pair”).
• You need to search for a value in a list in better than O(n) time.
• You are trading space for speed, and the input array is not sorted (if it were sorted, Two Pointers might be cheaper).
• The task requires grouping elements by a derived property (e.g. grouping anagrams by sorted character representation).

How It Works

Instead of checking all pairs using nested loops (which takes quadratic time), you store each element in a hash map as you iterate through the collection. For each new element, you can check if its complement or match already exists in the map in constant time.

For example, to find if a list contains duplicate numbers:

1. Initialize an empty hash set: {}.
2. Traverse the list: [2, 5, 1, 5].
3. Read 2: not in set, add it: {2}.
4. Read 5: not in set, add it: {2, 5}.
5. Read 1: not in set, add it: {2, 5, 1}.
6. Read 5: already in set, duplicate detected. Return true.

Complexity, With Caveats

• Time Complexity: Average case O(1) for lookup and insertion operations, assuming a high-quality hash function and low hash collision rate. In the worst case (where all keys collide to the same bucket), operations degrade to O(n) time, though this is rare with standard library implementations.
• Space Complexity: O(n) auxiliary space. In the worst case, you must insert every unique element from the input collection into the hash table before finding a match or finishing the scan.

Minimal Code Template

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class ArrayHashingTemplate {
    // Membership and Duplicate Tracking
    public boolean hasDuplicate(int[] nums) {
        Set<Integer> visited = new HashSet<>();
        for (int num : nums) {
            if (visited.contains(num)) {
                return true;
            }
            visited.add(num);
        }
        return false;
    }

    // Frequency and Index Mapping
    public Map<Integer, Integer> buildFrequencyMap(int[] nums) {
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }
        return freqMap;
    }
}

# Membership and Duplicate Tracking
def has_duplicate(nums: list[int]) -> bool:
    visited = set()
    for num in nums:
        if num in visited:
            return True
        visited.add(num)
    return False


# Frequency and Index Mapping
def build_frequency_map(nums: list[int]) -> dict[int, int]:
    freq_map = {}
    for num in nums:
        freq_map[num] = freq_map.get(num, 0) + 1
    return freq_map

#include <vector>
#include <unordered_set>
#include <unordered_map>

class ArrayHashingTemplate {
public:
    // Membership and Duplicate Tracking
    bool hasDuplicate(const std::vector<int>& nums) {
        std::unordered_set<int> visited;
        for (int num : nums) {
            if (visited.count(num)) {
                return true;
            }
            visited.insert(num);
        }
        return false;
    }

    // Frequency and Index Mapping
    std::unordered_map<int, int> buildFrequencyMap(const std::vector<int>& nums) {
        std::unordered_map<int, int> freqMap;
        for (int num : nums) {
            freqMap[num]++;
        }
        return freqMap;
    }
};

Where This Pattern Falls Short

• Ordering constraints: Hash sets and maps do not preserve the insertion or sorted order of keys. If you need to access elements in sorted order, or keep track of insertion sequence, you must use supplementary structures like sorted maps or linked tables, which increase overhead.
• Strict memory restrictions: If O(n) extra space is not permitted, hashing is the wrong choice. You must look for in-place algorithms (like sorting the array and using Two Pointers).
• Mutable keys: If a key object is mutated after insertion into a hash map, its hash code changes, making it impossible to retrieve or delete the key, causing memory leaks.

Related Patterns, Compared

• Two Pointers: choose this instead when the array is sorted or can be sorted without losing needed info, since you can trade the O(n) space of a hash set for O(1) space with two pointers.
• Sliding Window: choose this instead when you need to track elements within a contiguous block or subarray, using a hash map to maintain counts of elements inside the window boundary.

Frequently Asked Questions

Why does a Hash Map have O(1) average lookup time? A hash map uses a hash function to translate keys into integer array indices. This allows direct array offset lookups, which are performed in constant time.

How do you handle hash collisions? Standard library implementations handle collisions using chaining (linking colliding keys in list or tree buckets at the same index) or open addressing (probing adjacent array slots).

When should I use a Hash Set instead of a Hash Map? Use a hash set when you only need to check if an element exists or track uniqueness. Use a hash map when you need to pair the element with an associated value, such as its frequency count or array index.