Optimizing Two Sum: Moving from O(n²) to O(n) with Hash Maps

The Efficiency Gap in Pair Searching

When solving the classic Two Sum problem—finding two indices in an array whose values sum to a specific target—the instinctive approach is a nested loop. This brute-force method checks every possible pair, resulting in a time complexity of O(n²). For small datasets, this is negligible. However, as the input size grows, the execution time increases quadratically, often leading to a "Time Limit Exceeded" (TLE) error on platforms like LeetCode.

The core problem is redundant searching. In a brute-force approach, the algorithm repeatedly scans the remainder of the array for a value it has already seen or ignored. The takeaway is a fundamental engineering trade-off: by using a small amount of extra memory, we can eliminate the inner loop entirely.

The Single-Pass Hash Map Strategy

Instead of searching for the complement (target - current_value) by scanning the array, we can store every value we encounter in a hash map (or dictionary). A hash map allows for average O(1) time complexity for lookups.

The "single-pass" logic works by checking if the complement exists in the map before adding the current element to the map. This sequence ensures that you don't accidentally use the same element twice to reach the target—a common edge case when the target is exactly double the value of an element in the array.

Implementation Example

Below is the implementation using Python. This approach processes the list once, maintaining a map of {value: index}.

def twoSum(nums, target):
    # Map to store value as key and its index as value
    prevMap = {}

    for i, n in enumerate(nums):
        diff = target - n
        # Check if the complement has already been seen
        if diff in prevMap:
            return [prevMap[diff], i]
        # Store the current value and index for future complements
        prevMap[n] = i
    return []

Complexity and Trade-off Analysis

The shift from brute-force to a hash map changes the resource profile of the solution significantly:

Metric	Brute Force	Hash Map	Impact
Time Complexity	O(n²)	O(n)	Drastic speed increase for large arrays.
Space Complexity	O(1)	O(n)	Increased memory usage to store the map.

Validation and Edge Cases

To verify this logic, you should test against scenarios that typically break naive implementations:

• Duplicate Values: If the input is [3, 3] and the target is 6, the map must correctly identify the first 3 as the complement for the second 3.
• Negative Numbers: Ensure the logic holds for inputs like [-1, -2, -3] with a target of -5.
• End-of-Array Pairs: Ensure the loop doesn't terminate prematurely before reaching the final index.

Limitations and Constraints

While the hash map is the optimal general-purpose solution, it is not always the absolute best choice. If the input array is already sorted, a two-pointer approach can solve the problem in O(n) time while maintaining O(1) space, removing the need for the map entirely. Always check if the input is sorted before committing to a hash map.

Additionally, when testing on LeetCode, you will see "Runtime Percentile" and "Memory Percentile" scores. Be aware that these are often noisy. Identical code submitted twice may yield different percentiles due to server load and judge variance. Focus on the Big O complexity rather than chasing a 100% runtime score.