Solving Two Sum: From Brute Force to Optimal HashMap

The Two Sum Problem

The problem is straightforward: given an array of integers and a target value, you need to find two numbers in the array that add up to the target. Most commonly, you are asked to return the indices of these two numbers.

Now that we understand the goal, let's start with the most direct way to solve it.

Approach 1: The Brute-Force Solution

The most intuitive approach is to simply try every possible pair of numbers in the array and see if their sum equals the target. This is the brute-force method. How would we implement this? We can use two nested loops. The outer loop selects the first number, and the inner loop iterates through the rest of the array to find a second number that forms a valid pair.

The "take U forward" video below explains this logic clearly.

Here is a typical Java implementation for this approach:

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        // Outer loop iterates from the first element to the second-to-last
        for (int i = 0; i < nums.length; i++) {
            // Inner loop iterates from the element after 'i' to the end
            for (int j = i + 1; j < nums.length; j++) {
                // Check if the pair sums to the target
                if (nums[i] + nums[j] == target) {
                    // If so, return their indices
                    return new int[]{i, j};
                }
            }
        }
        // If no solution is found (though the problem guarantees one exists)
        return new int[]{-1, -1};
    }
}

Complexity Analysis:

• Time Complexity: $O(n^2)$. For each element in the array, we iterate through the rest of the array. If the array has $n$ elements, this results in approximately $n\ast (n-1)/2$ comparisons, which is on the order of $n^2$.
• Space Complexity: $O(1)$. We are not using any extra space that scales with the size of the input array.

For a small array, this solution works fine. However, in an interview context where arrays can contain thousands or millions of elements, an $O(n^2)$ solution is often too slow. The interviewer will almost certainly ask you to optimize it.

Approach 2: A Better, but Not Optimal, Solution (Two Pointers)

Before we jump to the optimal hash-based solution, it's useful to know another common pattern: the two-pointer technique. This approach works on a sorted array.

The algorithm is as follows:

1. Sort the input array.
2. Initialize two pointers: left at the beginning of the array (index 0) and right at the end (n-1).
3. While left is less than right:
   • Calculate the sum: currentSum = nums[left] + nums[right].
   • If currentSum == target, you've found the pair.
   • If currentSum < target, you need a larger sum, so you increment the left pointer to include a larger number.
   • If currentSum > target, you need a smaller sum, so you decrement the right pointer to include a smaller number.

Complexity Analysis:

• Time Complexity: $O(n\log n)$. The dominant operation is sorting the array. The two-pointer scan itself is only $O(n)$.
• Space Complexity: $O(1)$ or $O(\log n)$ depending on the sorting algorithm's implementation space, assuming we can modify the input array.

This is a significant improvement over the brute-force method. However, it has a major drawback for the specific problem of returning original indices: sorting the array shuffles the elements, losing their original positions. You would need to use extra space (e.g., an array of pairs [value, original_index]) to keep track of the original indices, which complicates the solution and increases space complexity to $O(n)$.

Because of this complication, for the specific task of returning original indices from an unsorted array, there is a cleaner and more efficient way.

Approach 3: The Optimal One-Pass HashMap Solution

This is where the concepts from our last lesson come into play. The bottleneck in the brute-force approach is the inner loop, which performs a linear search for the second number. The core question we are trying to answer is: "For the current number nums[i], does the required complement, target - nums[i], exist elsewhere in the array?"

A linear search takes $O(n)$ time. But as you know, a HashMap can answer the "does it exist?" question in $O(1)$ average time.

This insight allows us to redesign the algorithm completely. We can iterate through the array just once, and for each element, we can instantly check if its complement has already been seen.

Here is the one-pass algorithm:

1. Create an empty HashMap<Integer, Integer> to store numbers we've seen and their corresponding indices. The map will store (value -> index).
2. Iterate through the nums array from i = 0 to n-1.
3. For each element nums[i], calculate the complement we need: complement = target - nums[i].
4. Check if this complement exists as a key in our HashMap.
   • If it does, we have found our solution! The two numbers are nums[i] (the current number) and complement (the number we saw earlier). We can immediately return the current index i and the index of the complement, which we retrieve from the map: map.get(complement).
   • If it does not exist, it means we haven't found a pair yet. We add the current number and its index to the map: map.put(nums[i], i). This is so that future elements can use it as their complement.
5. Repeat until the solution is found.

The "Coding with John" video provides an exceptionally clear explanation and visualization of this one-pass approach.

To see this in action, consider the example nums = [3, 2, 4] and target = 6.

1. i = 0, num = 3:
   • complement = 6 - 3 = 3.
   • Is 3 in the map? No, the map is empty.
   • Add (3, 0) to the map. Map is now {3: 0}.
2. i = 1, num = 2:
   • complement = 6 - 2 = 4.
   • Is 4 in the map? No.
   • Add (2, 1) to the map. Map is now {3: 0, 2: 1}.
3. i = 2, num = 4:
   • complement = 6 - 4 = 2.
   • Is 2 in the map? Yes! Its index is 1.
   • Solution found! Return the complement's index from the map (1) and the current index (2). Result: [1, 2].

The image below from algo.monster depicts the state of the hash table just before finding the solution in a similar example. Notice how it stores the numbers encountered so far and their indices, ready for a quick lookup.

Here is the clean Java code for the optimal solution:

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

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>(); // Stores <number, index>
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                // Found the solution
                return new int[] { map.get(complement), i };
            }
            // If complement not found, put the current number and its index in the map
            // for future elements to check against.
            map.put(nums[i], i);
        }
        // According to the problem statement, a solution always exists,
        // so this part should ideally not be reached.
        throw new IllegalArgumentException("No two sum solution");
    }
}

Complexity Analysis:

• Time Complexity: $O(n)$. We traverse the list containing $n$ elements only once. Each lookup and insertion in the HashMap takes, on average, $O(1)$ time.
• Space Complexity: $O(n)$. In the worst case, we might have to store all $n$ elements in the HashMap before finding a pair at the very end.

This solution is both time-efficient and relatively straightforward to implement, making it the preferred answer in a FAANG-level interview.

You can find the full write-up, including all three approaches, in the Striver A2Z course material.

Conclusion

In this lesson, we took a deep dive into solving a classic algorithm problem, Two Sum, by systematically improving our solution. This process mirrors the expectations in a real coding interview.

Key Takeaways:

• Problem-solving progression: We moved from a brute-force $O(n^2)$ solution to an $O(n\log n)$ two-pointer solution, and finally to the optimal $O(n)$ one-pass HashMap solution.
• Choosing the right data structure is key: The HashMap's $O(1)$ average time complexity for lookups was the critical factor that enabled the optimal solution.
• The "Complement Lookup" Pattern: The strategy of iterating through an array while using a hash map to look for a target - current_element complement is a fundamental and powerful pattern you will use again and again.

Now that you've mastered the Two Sum problem, you are ready to apply similar logic to other problems. In our next lesson, we will tackle the "Longest Consecutive Sequence" problem, where you'll use a HashSet to achieve a similarly elegant and efficient solution.