Two Sum Problem: Multiple Solutions and Complexity Analysis

Introduction to the Two Sum Problem

The Two Sum problem is one of the most iconic algorithmic challenges in computer science. It is frequently the first problem developers encounter on platforms like LeetCode, and it serves as a foundational exercise for understanding hash maps, array traversal, and time-space tradeoffs. Despite its apparent simplicity, the problem reveals deep insights into how we can optimize solutions by trading memory for speed.

At its core, the problem asks: given an array of integers and a target integer, find the indices of the two numbers that add up to the target. You may assume each input has exactly one solution, and you cannot use the same element twice.

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.

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

Why the Two Sum Problem Matters

The Two Sum problem is more than an interview warm-up. It introduces several critical concepts that appear throughout software engineering:

Hash map usage: Demonstrates how to achieve O(1) lookups to avoid nested loops.
Time-space tradeoffs: Shows how spending extra memory can dramatically reduce runtime.
Edge case handling: Forces developers to consider duplicates, negative numbers, and single-element arrays.
Foundation for harder problems: Three Sum, Four Sum, and subset-sum problems all build on this concept.

In real-world applications, similar logic appears in financial reconciliation systems, gaming matchmakers, inventory pairing, and cryptographic verification routines where complementary values must be located quickly.

Solution 1: Brute Force Approach

The most intuitive solution is to check every possible pair of numbers in the array. For each element, iterate through every other element and check if their sum equals the target.

Implementation

function twoSumBruteForce(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    return [];
}

// Example usage
console.log(twoSumBruteForce([2, 7, 11, 15], 9)); // [0, 1]

Complexity Analysis

Time Complexity: O(n²) — nested loops compare every pair.
Space Complexity: O(1) — no additional data structures are used.

This approach works for small inputs but becomes prohibitively slow for large arrays. If the array has 100,000 elements, the inner loop could execute up to 10 billion times.

Solution 2: Hash Map (One Pass)

The optimal solution leverages a hash map to store numbers we have already seen. As we iterate through the array, we calculate the complement (the value needed to reach the target) and check if it already exists in the map. If it does, we have found our pair.

Implementation

function twoSumHashMap(nums, target) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        map.set(nums[i], i);
    }
    return [];
}

// Example usage
console.log(twoSumHashMap([2, 7, 11, 15], 9)); // [0, 1]
console.log(twoSumHashMap([3, 2, 4], 6));      // [1, 2]
console.log(twoSumHashMap([3, 3], 6));         // [0, 1]

How It Works

Using the example nums = [2, 7, 11, 15] with target = 9:

Index 0: value 2, complement 7. Map is empty, so store {2: 0}.
Index 1: value 7, complement 2. Map contains 2 at index 0. Return [0, 1].

Complexity Analysis

Time Complexity: O(n) — single pass through the array with O(1) hash map operations.
Space Complexity: O(n) — in the worst case, we store every element in the map.

This is the recommended solution for most scenarios because it scales linearly with input size.

Solution 3: Two Pointer Approach (Sorted Array)

If the input array is already sorted, or if we are allowed to sort it, we can use two pointers — one at the beginning and one at the end — moving them inward based on the current sum compared to the target.

Implementation

function twoSumTwoPointer(nums, target) {
    // Create array of [value, originalIndex] pairs
    const indexed = nums.map((value, index) => ({ value, index }));
    // Sort by value
    indexed.sort((a, b) => a.value - b.value);

    let left = 0;
    let right = indexed.length - 1;

    while (left < right) {
        const sum = indexed[left].value + indexed[right].value;
        if (sum === target) {
            return [indexed[left].index, indexed[right].index];
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return [];
}

// Example usage
console.log(twoSumTwoPointer([2, 7, 11, 15], 9)); // [0, 1]

Complexity Analysis

Time Complexity: O(n log n) — dominated by the sorting step. The two-pointer traversal itself is O(n).
Space Complexity: O(n) — for storing the indexed array (or O(1) if the array is already sorted and indices are not required).

This approach is particularly useful when the array is already sorted, in which case the time complexity drops to O(n) with O(1) space.

Comparing the Solutions

Approach	Time	Space	Best For
Brute Force	O(n²)	O(1)	Small inputs, memory-constrained environments
Hash Map	O(n)	O(n)	General purpose, large unsorted inputs
Two Pointer	O(n log n)	O(n)	Pre-sorted arrays, when indices are not required

Best Practices

Choose the hash map solution by default. It offers the best average-case performance and handles unsorted inputs gracefully.
Validate inputs. Check for null arrays, arrays with fewer than two elements, and non-integer values where appropriate.
Handle duplicates correctly. The one-pass hash map naturally handles duplicates because we check for the complement before inserting the current value.
Consider the return type. Some variations ask for values instead of indices. Adjust your data structure accordingly — sorting may be preferable if indices are not needed.
Profile before optimizing. For tiny arrays, the brute force approach may actually be faster due to lower constant overhead and cache locality.
Use typed maps when possible. In languages like Java or C++, using primitive maps (e.g., HashMap<Integer, Integer>) avoids autoboxing overhead.

Python Implementation for Reference

def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

# Example usage
print(two_sum([2, 7, 11, 15], 9))  # [0, 1]

Common Variations

Interviewers often extend the Two Sum problem to test deeper understanding:

Return all pairs: Instead of a single pair, return every unique pair that sums to the target.
Three Sum: Find all triplets that sum to zero, requiring sorting and two-pointer techniques.
Two Sum in a BST: Use in-order traversal combined with two pointers, or a hash set during traversal.
Two Sum with sorted input: Skip the hash map entirely and use the two-pointer approach for O(n) time and O(1) space.

Conclusion

The Two Sum problem elegantly demonstrates how algorithmic thinking transforms a naive O(n²) solution into an efficient O(n) one through the strategic use of a hash map. By understanding all three approaches — brute force, hash map, and two pointer — developers gain a versatile toolkit that applies far beyond this single problem. The hash map solution remains the gold standard for general use cases, offering linear time complexity at the cost of linear space, while the two-pointer technique shines when working with sorted data. Mastering these patterns builds the foundation for tackling more complex challenges like Three Sum, subset problems, and real-world pairing logic in production systems.