LeetCode #1 Two Sum: Every Approach Explained (Brute Force to Optimal)

The Problem

Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. You may assume exactly one solution exists and you may not use the same element twice.

Input:  nums = [2, 7, 11, 15], target = 9
Output: [0, 1]  // because nums[0] + nums[1] = 2 + 7 = 9

Approach 1: Brute Force — O(n²) Time, O(1) Space

The simplest idea: check every pair of elements.

def twoSum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

Why it works: We systematically check all combinations. If two numbers sum to target, we'll find them.

Why it's slow: For an array of size n, we do up to n*(n-1)/2 comparisons — quadratic growth. Unacceptable for large inputs.

Approach 2: Sorting + Two Pointers — O(n log n) Time, O(n) Space

Sort the array while keeping track of original indices. Use two pointers from each end.

def twoSum(nums, target):
    indexed = sorted(enumerate(nums), key=lambda x: x[1])
    left, right = 0, len(indexed) - 1
    while left < right:
        s = indexed[left][1] + indexed[right][1]
        if s == target:
            return [indexed[left][0], indexed[right][0]]
        elif s < target:
            left += 1
        else:
            right -= 1

Why it's better: Sorting takes O(n log n), then the two-pointer scan is O(n). Total: O(n log n).

Limitation: We need to store sorted pairs with original indices, adding O(n) space. Still not the best.

Approach 3: Hash Map — O(n) Time, O(n) Space ✅ Optimal

This is the canonical solution. For each element, check if its complement (target - num) already exists in a hash map. If yes, we're done. If not, store the current number and its index.

def twoSum(nums, target):
    seen = {}  # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

Let's trace through the example: nums = [2, 7, 11, 15], target = 9

i=0, num=2: complement is 7. Not in seen. Store seen[2] = 0.
i=1, num=7: complement is 2. Found in seen at index 0. Return [0, 1]. ✅

Why it's optimal: One pass through the array. Each lookup and insert is O(1) amortized. Total: O(n) time, O(n) space.

Comparison Summary

Approach	Time	Space	Recommended?
Brute Force	O(n²)	O(1)	❌ Too slow
Sort + Two Pointers	O(n log n)	O(n)	⚠️ Good to know
Hash Map	O(n)	O(n)	✅ Use this

Key Insight to Carry Forward

The hash map approach works because we transform the question from "do any two elements sum to target?" into "has the complement of this element appeared before?" — a much cheaper question to answer. This complement-lookup trick extends to Three Sum, Four Sum, and countless other problems.

Edge Cases to Consider

Negative numbers — the algorithm handles them correctly since we're using subtraction.
Duplicates like [3, 3] with target 6 — works because we check before inserting.
No solution — the problem guarantees one exists, but in practice you'd return [] or raise an error.