Hash-Based Solutions for Two Sum and Its Variations

1. Understanding the Two Sum Problem

The problem is simple to state but serves as a perfect test for moving from a brute-force to an optimized mindset.

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

• You may assume that each input would have exactly one solution.
• You may not use the same element twice.

Example:

• Input: nums = [2, 7, 11, 15], target = 9
• Output: [0, 1]
• Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

As with any interview problem, the first step is to think of a simple, correct solution, even if it's not the most efficient. This demonstrates a solid problem-solving foundation.

The brute-force approach, checking every possible pair of numbers, gives us a time complexity of $O(n^2)$. For a typical interview constraint where n can be up to 10⁵, an $n^2$ algorithm would be too slow ($10^{10}$ operations). This is your cue to find a more optimal solution.

2. The Hash Map Optimization

How can we do better? The bottleneck is finding the second number. For each element x in the array, we are looking for its complement, which is target - x. The brute-force method takes $O(n)$ time to search for this complement.

What data structure gives us a faster search? The hash map, which provides an average lookup time of $O(1)$. This is the key insight.

The core idea is to trade space for time. We'll use a hash map to store the numbers we've already seen, allowing us to find the complement in an instant.

There are two main ways to structure this: a two-pass approach and a one-pass approach.

Two-Pass Hash Map Approach

This is an intuitive way to apply the hash map.

1. First Pass: Iterate through the entire array and store each element and its index in a hash map. The map will look like {value: index}.
2. Second Pass: Iterate through the array again. For each element nums[i], calculate the complement c = target - nums[i]. Check if c exists in the hash map. If it does, and its index is not i, you've found your solution.

This approach is correct and improves the time complexity to $O(n)$, but can we do even better and solve it in a single pass?

One-Pass Hash Map Approach

This is the standard, most elegant solution you should aim for in an interview.

The logic is refined: you can build the hash map and check for the complement at the same time.

As you iterate through the array (let's say you're at index i with value x):

1. Calculate the complement: c = target - x.
2. Check if c already exists in your hash map. If it does, you have found your pair! The first index is stored in map[c], and the second index is your current index, i.
3. If the complement is not in the map, add the current value x and its index i to the map. This prepares you for future iterations.

By checking for the complement before adding the current element, you naturally avoid using the same element twice.

Let's watch a video that walks through this clever one-pass trick.

Here is a visual representation of this one-pass process:

3. Implementation and Complexity

Now, let's translate this logic into code. Given your familiarity with Python, here is a clean implementation.

def two_sum(nums: list[int], target: int) -> list[int]:
    seen = {}  # A dictionary to store value -> index
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:
            return [seen[complement], i]
        seen[x] = i
    return [] # Should not be reached based on problem constraints

This code perfectly implements the one-pass strategy.

• Time Complexity: $O(n)$. We traverse the list containing $n$ elements only once. Each lookup and insertion in the hash map takes $O(1)$ time on average.
• Space Complexity: $O(n)$. In the worst case, we might have to store all $n$ elements in the hash map before finding the solution pair (e.g., if the pair is the last two elements).

This is a classic time-space tradeoff. We use extra memory to reduce the time complexity from quadratic to linear.

4. Variations and Interview Context

Recognizing and solving the basic Two Sum problem is just the first step. In an interview, you need to articulate your solution, discuss tradeoffs, and handle variations.

One of the most common variations is when the input array is sorted.

• Question: If the input array nums were sorted, could you solve this problem with $O(1)$ space complexity?
• Answer: Yes. You could use the Two Pointers technique. Start one pointer at the beginning (left) and one at the end (right). If nums[left] + nums[right] is too small, increment left. If it's too large, decrement right. If it's equal to the target, you've found your pair. This takes $O(n)$ time and $O(1)$ space. We'll cover this pattern in-depth in a future module. Mentioning this alternative shows the interviewer that you think critically about problem constraints.

Conclusion

Congratulations! You've just mastered one of the most important patterns for technical interviews. The "find a complement using a hash map" strategy is applicable to a wide range of "pair-finding" problems.

Key Takeaways:

• The Two Sum Pattern: For a given element x, you can instantly check for the existence of its complement (target - x) using a hash map.
• One-Pass is Optimal: The one-pass hash map approach is the standard, efficient solution, achieving $O(n)$ time and $O(n)$ space.
• Articulate Tradeoffs: Be ready to discuss the brute-force $O(n^2)$ solution and explain why the hash map's time-space tradeoff is superior. Also, be aware of constraint-specific alternatives like the two-pointer method for sorted arrays.

In the next lesson, we will look at Hash Sets. While hash maps store key-value pairs, hash sets are simpler: they only store unique keys. We will see how this is perfectly suited for problems involving duplicate detection and membership testing.