Problem 4.1 · HashingEasy

Two Sum

What it teaches: The complement trick: for each number, look up target − number among the numbers already seen.

Practise it on judges as “Two Sum”.

The problem

Given an integer array nums and an integer target, return the indexes of the two numbers that add up to target. Exactly one solution exists, and you may not use the same element twice. Return the smaller index first.

Example 1

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

nums[0] + nums[1] = 2 + 7 = 9.

Example 2

Input: nums = [3, 2, 4], target = 6
Output: [1, 2]

Example 3

Input: nums = [3, 3], target = 6
Output: [0, 1]

Constraints

2 ≤ nums.length ≤ 10⁴
−10⁹ ≤ nums[i], target ≤ 10⁹
Exactly one valid answer

Pattern clues in the wording

→ Find a pair with a given sum
→ Return original indexes, so sorting would lose them
→ Unsorted input

These clues point to Hash Map Lookup (Complement): As you scan, store what you've seen; for each new element, ask in O(1) whether its partner was already seen.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        return new int[0];
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	nums = [2,7,11,15] target = 9	[0,1]
2	nums = [3,2,4] target = 6	[1,2]
3	nums = [3,3] target = 6	[0,1]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Brute force: every pair · O(n²)2. Optimal: one-pass hash map · O(n)

Brute force: every pair

Time O(n²) Space O(1)

Check all pairs (i, j) with i < j until one sums to target.

Approach 1

class Solution {
    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];
    }
}

Verdict: Fine for tiny inputs, about 5 × 10⁷ checks at n = 10⁴. The repeated work: searching the array again for each complement.

Optimal: one-pass hash map

Time O(n) Space O(n)

Keep a map from value to index for the numbers seen so far. For each nums[i], if target − nums[i] is in the map, return its index and i. Otherwise store nums[i] → i.

▶ Dry run: Looking up complementsnums = [2, 7, 11, 15], target = 9

↑i

seen (value → index)(map)

2 → 0

Step 1/2Need 9 − 2 = 7: not seen yet. Store 2 → 0.

Approach 2

import java.util.HashMap;
import java.util.Map;

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

Verdict: One pass with O(1) lookups. The standard answer.

Before you submit

Edge cases and common mistakes

Test these inputs

The two numbers are equal (e.g. [3, 3], target 6)
Negative numbers
Answer uses the last element

Mistakes people make

Storing all numbers first, then looking up: x can match itself when target = 2x.
Sorting to use two pointers, then returning sorted positions instead of original indexes.
target - nums[i] can overflow for extreme values; with the constraints here it fits in an int, but say so.

Interview

Follow-up questions

What if the array is sorted?

What if you must return all pairs, or count them?

Command Palette