Linear Time Complement Lookup using Hash Maps

Welcome to the next lesson in our journey through core algorithmic patterns. In our last session, we explored how a Map can be used for frequency counting, helping us efficiently track how many times we've seen an element. Today, we'll adapt this powerful tool for a different purpose: instead of tracking the count, we will track the location (i.e., the index) of elements we've encountered.

This unlocks the complement-lookup pattern, a fundamental technique for solving a wide class of problems that involve finding pairs of elements satisfying a specific relationship. By the end of this lesson, you will be able to use a value-to-index map to solve these problems in linear time, a significant improvement over more naive approaches. We will ground our discussion in the "Two Sum" problem, arguably one of the most famous and foundational questions in coding interviews.

The Problem: Two Sum

Let's begin with the problem statement, which is a classic from LeetCode (LC1).

Given an array of integers nums and an integer target, return the indices of the two numbers in the array such that they add up to target.

You can assume that each input would have exactly one solution, and you may not use the same element twice.

For example, if nums = [2, 7, 11, 15] and target = 9, the answer should be [0, 1] because nums[0] + nums[1] is 2 + 7 = 9.

The Brute-Force Approach: A Natural Starting Point

As a developer, your first instinct might be to check every possible pair of numbers in the array. This is a perfectly valid starting point and is known as the brute-force solution. We can implement this with nested loops: the outer loop picks the first number, and the inner loop iterates through the remaining numbers to find a pair that sums to the target.

The video below gives an excellent visual and conceptual breakdown of this approach, including a careful analysis of why its time complexity is $O(n^2)$.

While $O(n^2)$ is correct and works for small inputs, it's often too slow for typical interview constraints where n can be large. The bottleneck is the inner loop; for each element, we are performing a linear scan to find its partner. How can we make this search faster?

Optimizing with a Hash Map

This is where our knowledge of hash maps comes into play. In the last two lessons, we've seen that Set and Map give us average-case $O(1)$ time for lookups. What if we could use a map to find the required partner in constant time instead of linear time?

The key insight for the Two Sum problem is this: as we iterate through the array, for each number x, we know exactly what we're looking for. The number we need is its complement: complement = target - x.

The question then becomes: "Have we seen complement before, and if so, where?"

To answer this, we can use a Map to store the numbers we've already processed and their corresponding indices. This creates a value-to-index map.

Let's walk through how this map helps us.

The One-Pass Hash Table Solution

While one could first populate the map in one pass and then check for complements in a second pass, the most efficient and common interview solution does this in a single pass. The logic is subtle but powerful.

Here is the algorithm:

1. Initialize an empty map, seen = new Map<number, number>().
2. Iterate through the nums array with index i from 0 to n-1.
3. For the current number num = nums[i]:
   a. Calculate its complement: complement = target - num.
   b. Check if complement exists as a key in our seen map.
   - If it does, we have found our pair! The index of the complement is seen.get(complement), and the index of the current number is i. We can return [seen.get(complement), i].
   - If it does not, add the current number and its index to the map: seen.set(num, i). Then, continue to the next iteration.

This "check first, then add" sequence is critical. By adding an element to the map only after checking for its complement, we ensure that the map only contains elements from previous iterations. This elegantly prevents an element from being paired with itself and correctly handles all cases.

The following video provides a TypeScript implementation and a clear explanation of this one-pass approach, including why we check for the complement before adding the current number to the map.

To solidify this, let's trace the one-pass algorithm with an example: nums = [2, 11, 7, 15], target = 9.

i	num	complement	seen Map Before Check	Check seen.has(complement)?	Action	seen Map After Action
0	2	7	{}	false	seen.set(2, 0)	{ 2 => 0 }
1	11	-2	{ 2 => 0 }	false	seen.set(11, 1)	{ 2 => 0, 11 => 1 }
2	7	2	{ 2 => 0, 11 => 1 }	true (seen.get(2) is 0)	Return [0, 2]	-

As you can see, when we reached the number 7 at index 2, its complement 2 was already in the map with its index 0. The algorithm terminated and returned the correct answer.

This resource provides another excellent, concise explanation and a step-by-step trace.

Final TypeScript Implementation

Here is a clean, commented implementation of the one-pass solution in TypeScript, using a Map.

function twoSum(nums: number[], target: number): number[] {
    // The map will store the value and its most recently seen index.
    // Map<value, index>
    const seen = new Map<number, number>();

    for (let i = 0; i < nums.length; i++) {
        const currentNum = nums[i];
        const complement = target - currentNum;

        // Check if the complement needed to reach the target exists in our map.
        if (seen.has(complement)) {
            // If it exists, we've found our solution.
            // The problem guarantees a solution exists, so we can use the non-null assertion !.
            return [seen.get(complement)!, i];
        }

        // If the complement is not found, add the current number and its index to the map
        // for future lookups.
        seen.set(currentNum, i);
    }

    // Per the problem statement, a solution always exists, so this path is unreachable.
    // We include it to satisfy TypeScript's compiler about all paths returning a value.
    return []; 
}

This solution has a time complexity of $O(n)$ because we iterate through the array once. The Map operations (has, get, set) take $O(1)$ time on average. The space complexity is $O(n)$ because, in the worst case, we might store all n elements in the map. This time/space trade-off is central to many efficient algorithms.

Conclusion

Today we've added a crucial pattern to our toolkit. By moving from frequency counting to storing indices in a Map, we were able to solve the "Two Sum" problem in linear time.

Key Takeaways:

• Complement Lookup: This pattern is ideal for problems where you need to find two elements x and y that satisfy a simple algebraic relation (e.g., x + y = target).
• Value-to-Index Map: The core tool is a hash map that stores value -> index pairs, enabling instantaneous lookup of a number's location.
• One-Pass Strategy: The most efficient solution involves iterating through the array once, simultaneously checking for a complement among past elements and populating the map for future elements.
• Check Before Add: The logical key to the one-pass solution is to check for the complement before adding the current element to the map. This correctly handles all edge cases and ensures you don't use the same element twice.
• Time-Space Trade-off: We improved the time complexity from $O(n^2)$ to $O(n)$ at the cost of using $O(n)$ extra space for the map.

In our next lesson, we will continue to leverage the power of hash maps. We will explore how to "Transform strings into canonical keys for grouping equivalent items." This will allow us to solve problems like grouping anagrams together, building directly on the hash map skills we've developed so far.