Two Sum

EasyHashing · Complement Lookup🧩 Hashing & Counting LeetCode #1 ↗Updated Oct 30, 2026

Problem

You are given an integer array nums and a number target. Find two different positions whose values add up to target and return their indices (in any order). Exactly one valid pair is guaranteed, and the same element may not be used twice.

Inputnums = [2,7,11,15], target = 9Output[0,1]

Inputnums = [3,2,4], target = 6Output[1,2]

Inputnums = [3,3], target = 6Output[0,1]

2 ≤ n ≤ 10⁴ · -10⁹ ≤ nums[i], target ≤ 10⁹ · exactly one answer · Follow-up: beat O(n²).

Try it yourself

Java

class Solution {
    public int[] twoSum(int[] nums, int target) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

For each value x the partner is fixed: target - x. Remember every value you have already passed in a hash map (value → index), and each lookup for the partner becomes O(1).

PatternHashing & Counting

Instinct Need "have I seen this before?", "how many times?" or "group things that look alike"? Trade memory for O(1) lookups with a HashMap, HashSet or int[26].

Memory hack Don't search, remember - every element checks in at the front desk, and the desk answers instantly.

Open the Hashing & Counting guide →

Approaches

Brute ForceTry Every Pair

Time O(n²)Space O(1)

Fix the first index i, then scan every later index j and test nums[i] + nums[j] == target. Starting j at i + 1 guarantees two different positions and checks each pair once.

Java

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) return new int[] {i, j};
        }
    }
    return new int[0]; // unreachable: a pair is guaranteed
}

No extra memory, but about n²/2 pair checks — too slow for the follow-up.

BetterSort Indices + Two Pointers

Time O(n log n)Space O(n)

Sort an array of indices by their values (sorting the values directly would lose the original positions). On the sorted order, a pair sum that is too small means move lo right; too large means move hi left.

Java

public int[] twoSum(int[] nums, int target) {
    int n = nums.length;
    Integer[] idx = new Integer[n];
    for (int i = 0; i < n; i++) idx[i] = i;
    Arrays.sort(idx, (a, b) -> Integer.compare(nums[a], nums[b]));
    int lo = 0, hi = n - 1;
    while (lo < hi) {
        long sum = (long) nums[idx[lo]] + nums[idx[hi]];
        if (sum == target) return new int[] {idx[lo], idx[hi]};
        if (sum < target) lo++;  // need a bigger sum
        else hi--;               // need a smaller sum
    }
    return new int[0];
}

Beats O(n²), but the sort dominates and the index bookkeeping is clumsy.

OptimalOne-Pass Hash Map

Time O(n)Space O(n)

Walk left to right. Before storing nums[i], ask the map whether its partner target - nums[i] was seen earlier. Looking up before inserting means an element can never pair with itself, yet duplicates like [3,3] still work.

Java

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>(); // value -> index
    for (int i = 0; i < nums.length; i++) {
        int need = target - nums[i];
        Integer j = seen.get(need);
        if (j != null) return new int[] {j, i};
        seen.put(nums[i], i);
    }
    return new int[0];
}

Dry runnums = [3,2,4], target = 6

i current changed

i=0
3
i
2

4

need 3: miss, store 3→0
i=1
3

2
i
4

need 4: miss, store 2→1
i=2
3

2

4
i
need 2: hit @1 ✔

Single pass with O(1) average lookups — trades O(n) memory for speed.

Pro tip

Note why the answer at i=0 is not [0,0]: 3 is looked up before it is inserted.

At a glance

Level	Approach	Time	Space
Brute Force	Try Every Pair	`O(n²)`	`O(1)`
Better	Sort Indices + Two Pointers	`O(n log n)`	`O(n)`
Optimal	One-Pass Hash Map	`O(n)`	`O(n)`

Common pitfalls

Inserting before looking up — [3,2,4], 6 wrongly pairs index 0 with itself.
Sorting the values directly — the original indices are lost.
Pre-filling the map in a separate pass without checking j != i.

Interview tips

Ask: indices or values? Sorted input? Duplicates? Always exactly one answer?
Mention the sorted two-pointer variant (LC 167) uses O(1) extra space.
Say the phrase complement lookup — it generalises to many sum problems.

Pattern

Hash map of seen values → when each element's partner is fully determined (e.g. target - x) and you need it fast.

My notes saved in this browser