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

Two Sum is the most-asked coding interview question on LeetCode. It's also a perfect example of how the right data structure turns an O(n²) problem into O(n). Here are all four approaches, from naive to optimal.

The Problem

Given an array of integers nums and a target value, return the indices of the two numbers that add up to the target. Each input has exactly one solution.

Approach 1: Brute Force — O(n²)

# Python — check every pair
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]

Time: O(n²) — nested loops. Space: O(1). Works but too slow for large inputs.

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

# Python — sort then squeeze
def twoSum(nums, target):
    indexed = sorted(enumerate(nums), key=lambda x: x[1])
    lo, hi = 0, len(indexed) - 1
    while lo < hi:
        s = indexed[lo][1] + indexed[hi][1]
        if s == target:
            return [indexed[lo][0], indexed[hi][0]]
        elif s < target:
            lo += 1
        else:
            hi -= 1

Time: O(n log n). Space: O(n). Better, but sorting costs us.

Approach 3: Hash Map — O(n) ✓ Optimal

# Python — one-pass hash map
def twoSum(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        diff = target - n
        if diff in seen:
            return [seen[diff], i]
        seen[n] = i

Time: O(n). Space: O(n). The classic interview answer.

Approach 3 in Go

func twoSum(nums []int, target int) []int {
    seen := make(map[int]int)
    for i, n := range nums {
        if j, ok := seen[target-n]; ok {
            return []int{j, i}
        }
        seen[n] = i
    }
    return nil
}

Approach 3 in JavaScript

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

Edge Cases to Mention in Interviews

• Duplicate values: [3, 3] with target 6 — the hash map handles this naturally since we check before inserting.
• Negative numbers: work exactly the same with the hash map approach.
• Empty or single-element arrays: clarify constraints — most versions guarantee a solution exists.

What Interviewers Actually Want

They want to see you start with brute force, explain why it's slow, and evolve to the hash map solution. Mention the time/space tradeoff. Ask clarifying questions about duplicates and return format.

Want real-time guidance during coding challenges? CodeSage Pro provides instant analysis and hints while you code.