Two Sum & Variations: HashMap Solutions

1. Understanding the 'Two Sum' Problem

First, let's make sure we understand the problem statement and, just as importantly, the kinds of clarifying questions you should ask in an interview setting.

To summarize, the classic problem is:

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 can typically assume:

• Exactly one solution exists.
• You may not use the same element twice.

2. The Brute-Force Approach: A Starting Point

The most intuitive way to solve this is to check every possible pair of numbers. How would we do that? With nested loops.

1. The outer loop picks the first number, say nums[i].
2. The inner loop checks every subsequent number, nums[j], to see if nums[i] + nums[j] == target.

This approach is correct, but it's inefficient. For an array of size n, the outer loop runs n times, and the inner loop runs roughly n times for each of those iterations. This leads to a time complexity of O(n²). For the array sizes common in interviews (e.g., up to 10⁵), this would be too slow.

In an interview, it's good practice to mention this brute-force solution first to show you understand the problem, and then immediately discuss how to optimize it.

3. The Optimal Solution: Leveraging HashMap

The bottleneck in the brute-force method is finding the second number. For each nums[i], we are scanning the rest of the array to find its partner, complement = target - nums[i]. This search takes O(n) time.

How can we make that search faster? This is where your knowledge of data structures comes in. We need a structure that allows for fast lookups. A HashMap is perfect for this, offering O(1) average-time complexity for its get() and containsKey() operations.

The strategy is as follows: we will iterate through the array a single time. For each element, we'll check if its required partner is already in our map.

This video provides an excellent step-by-step walkthrough of this thought process.

The One-Pass HashMap Algorithm

Let's formalize the logic:

1. Create an empty HashMap<Integer, Integer> to store (number, index) pairs.
2. Iterate through the nums array with index i from 0 to n-1.
3. For each element nums[i], calculate the complement = target - nums[i].
4. Check if the complement exists as a key in your HashMap.
   • If it exists, you've found the solution! The indices are the value associated with the complement key in the map and the current index i. Return them.
   • If it does not exist, add the current element and its index to the map: map.put(nums[i], i). This prepares for future iterations, where nums[i] might be the complement for a later element.

Java Implementation

Here is a clean, interview-ready implementation of the one-pass HashMap solution.

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // Map to store numbers we've seen and their indices.
        Map<Integer, Integer> numMap = new HashMap<>();

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

            // Check if the complement needed to reach the target exists in the map.
            if (numMap.containsKey(complement)) {
                // If it exists, we've found our pair.
                return new int[]{numMap.get(complement), i};
            }

            // If the complement is not found, put the current number and its index in the map
            // for future lookups.
            numMap.put(currentNum, i);
        }

        // According to the problem statement, a solution always exists.
        // In a real-world scenario, you'd handle the case where no solution is found.
        throw new IllegalArgumentException("No two sum solution");
    }
}

• Time Complexity: O(n). We traverse the list containing n elements only once. Each lookup and insertion in the HashMap takes O(1) on average.
• Space Complexity: O(n). In the worst case, we might store all n elements in the HashMap.

4. Interview Strategy: Communication and Variations

Solving the problem is only half the battle. Communicating your thought process and handling follow-up questions is what distinguishes a strong candidate.

The following resource is exceptional for this. It's not just about the code; it's a guide on how to think and talk like an experienced engineer in an interview.

Handling a Common Variation: Sorted Array

A classic follow-up question is: "What if the input array is sorted?"

If the array is sorted, you can use a more space-efficient method called the two-pointer approach.

1. Initialize a left pointer at the start of the array (index 0) and a right pointer at the end (index n-1).
2. Calculate the sum = nums[left] + nums[right].
3. If sum == target, you've found the solution.
4. If sum < target, you need a larger sum, so move the left pointer one step to the right (left++).
5. If sum > target, you need a smaller sum, so move the right pointer one step to the left (right--).
6. Repeat until left crosses right.

This approach has a time complexity of O(n) and a space complexity of O(1), making it superior to the HashMap solution only when the array is already sorted and you don't need to preserve original indices from an unsorted array.

Conclusion

Mastering 'Two Sum' is a rite of passage in technical interviews. It's a simple problem that effectively tests your fundamentals in algorithms, data structures, and communication.

Key Takeaways:

• Brute-Force: An O(n²) solution using nested loops. A good starting point but not optimal.
• HashMap Solution: The standard optimal approach for an unsorted array. It trades O(n) space for a much-improved O(n) time complexity.
• Two-Pointer Solution: An O(n) time and O(1) space solution that works beautifully if and only if the input array is sorted.
• Communication is Key: Always state the brute-force solution, explain its inefficiency, and then present the optimized solution, clearly articulating the time and space trade-offs.

In our next lesson, we will continue building on this foundation. We'll tackle another common interview problem, 'Top K Frequent Elements', which requires a combination of a HashMap to count frequencies and a PriorityQueue to find the top elements.