Fast Lookup Patterns

Store what you will need to look up again

One of the main algorithmic patterns with a hash table can be stated like this: if a traversal repeatedly needs to search through already processed data, try storing that data in a Set or Map. Additional memory can often replace a repeated linear search with an expected O(1) check.

The structure depends on the question. If it is enough to know whether a value has been seen, a Set is appropriate. If we also need to remember an index, a counter, or other information, we need a Map.

Example: Two Sum in one pass

Suppose we need to find the indexes of two array elements whose sum equals target. For the current number numbers[i], we can immediately compute the missing value target - numbers[i] and check whether it has been seen before.

static int[] twoSum(int[] numbers, int target) {
    Map<Integer, Integer> indexByValue = new HashMap<>();

    for (int i = 0; i < numbers.length; i++) {
        int needed = target - numbers[i];
        Integer previousIndex = indexByValue.get(needed);

        if (previousIndex != null) {
            return new int[]{previousIndex, i};
        }

        indexByValue.put(numbers[i], i);
    }

    return new int[0];
}

The map stores an element value and the index where it was encountered. For each new element, we perform one expectedly fast check instead of scanning the entire previous part of the array. The expected time complexity is therefore O(n), with O(n) additional memory.

Why lookup comes before insertion

The current element is added to the map only after checking needed. This prevents the same index from being used twice accidentally. At the same time, two equal values at different positions are handled correctly: the second one can see the first if that pair produces the required sum.

How to recognize this pattern

• we need to check quickly whether a value has appeared before;
• we need to find a complementary value instead of trying every pair;
• we need to associate an object with already computed information and retrieve it quickly later;
• repeated lookup through the processed prefix makes the solution quadratic.

A hash table does not make every algorithm faster automatically. We gain an advantage when we deliberately trade some memory for time and can replace repeated search with a fast lookup by key.