Hash Map Techniques for Target-Sum Problems

The Cornerstone Problem: Two Sum

The "Two Sum" problem is LeetCode #1 for a reason. While categorized as "Easy," it serves as a powerful filter in interviews. It tests your ability to move beyond a naive solution, recognize a core algorithmic pattern, and articulate the trade-offs involved. For your goal of succeeding in top-tier interviews, mastering this problem and its underlying pattern is non-negotiable.

Let's start with the formal problem statement.

From Brute Force to Optimized Insight

The most straightforward way to solve this is to consider every possible pair of numbers. This is the brute-force approach.

The key to optimization lies in reframing the question. Instead of checking if a + b = target, for each number a we see, we can calculate its complement: complement = target - a. The problem then becomes: "Does this complement exist anywhere in the array?"

A naive scan for the complement would still be $O(n)$ for each number, keeping us at $O(n^2)$. But what if we could answer "have I seen this complement before?" in $O(1)$ time? This is precisely what a hash map enables.

This is the complement lookup pattern:

1. Iterate through the array.
2. For each number, calculate its required complement.
3. Look up this complement in a hash map of numbers we have already seen.
4. If it exists, we have found our solution.
5. If not, add the current number to the hash map so it can be found by a future number.

To see this logic in action, the following image provides a static, step-by-step walkthrough.

The One-Pass Implementation

A subtle but important implementation detail is when to add elements to the hash map. If you populate the map with all elements before you start iterating, you have to handle the edge case where a number's complement is itself (e.g., nums = [3, 5, 3], target = 6).

A more elegant solution is the one-pass approach: you iterate through the array, check for the complement among the numbers seen so far, and if it's not found, you add the current number to the map. This naturally prevents you from using the same element twice and is more efficient.

The following video provides an excellent explanation and live coding of this one-pass strategy.

Here is the final code, which you should be able to write from memory.

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

Complexity and Interview Articulation

In an interview, after writing your code, you will always be asked about its complexity. Being able to crisply analyze and justify your approach is as important as the code itself.

• Time Complexity: $O(n)$. We iterate through the list of n elements exactly once. Each hash map lookup (complement in seen) and insertion (seen[num] = i) takes, on average, $O(1)$ time.
• Space Complexity: $O(n)$. In the worst-case scenario, we might have to store all n elements in the hash map before finding the pair at the very end. This is the classic time-space trade-off.

Extending the Pattern: 3-Sum and Beyond

The true power of a pattern is its applicability to other problems. The complement lookup is the foundation for many "target-sum" variants.

3-Sum (LeetCode #15)

A common follow-up is the 3-Sum problem: find all unique triplets in an array that sum to zero.

A brute-force $O(n^3)$ solution is too slow. We can improve this by applying the Two Sum pattern. If we fix one number, a, the problem reduces to finding two other numbers b and c such that b + c = -a. We're back to a Two Sum problem!

The video below explores a few ways to solve this, but pay close attention to the final, optimal approach. It combines sorting with a two-pointer technique, which is more space-efficient than using a hash map for the inner "Two Sum" part when the array is sorted.

Subarray Sum Equals K (LeetCode #560)

We encountered this problem in the last lesson. Let's revisit it through the lens of the complement pattern. The problem asks for the number of subarrays that sum to k.

As we iterate and calculate the current_prefix_sum, we are looking for a previous prefix_sum such that:
current_prefix_sum - old_prefix_sum = k

Rearranging this, we get:
old_prefix_sum = current_prefix_sum - k

This is the complement pattern! At each step, our "target" is current_prefix_sum - k. We use a hash map to check how many times we've seen this complement prefix_sum before. This is a beautiful fusion of the frequency counting and complement lookup patterns.

Conclusion

You have now learned one of the most fundamental and frequently tested patterns in coding interviews. The ability to recognize a problem as a variation of "Two Sum" and apply the complement lookup pattern is a significant step forward in your preparation.

Key Takeaways:

• Complement Lookup Pattern: For a target T and a current element x, the problem often reduces to finding a complement y = T - x that has been previously seen.
• The One-Pass Solution: The most elegant way to solve Two Sum is to iterate through the array once, checking for the complement in a hash map of already-processed elements, and then adding the current element to the map.
• Time-Space Trade-off: The optimal hash map solution achieves a linear $O(n)$ time complexity by sacrificing linear $O(n)$ space. This is a trade-off you must be able to articulate.
• Pattern Extension: The core idea of finding a complement is not limited to Two Sum. It's the basis for solving more complex problems like 3-Sum and Subarray Sum Equals K.

In the next lesson, we will explore a third hash map pattern: grouping and classification. We'll see how using a "canonical" key can help us group related items, such as anagrams, efficiently.