Two Sum

What the problem is really asking

We need to find two positions in the array whose values add up to target.

The important part is that the answer wants indices, not the numbers themselves.

Intuition

When we look at a number like 7, we immediately know what we want next: target - 7.

That means every value creates a "missing partner" we should look for.

Brute-force idea

The most direct approach is to try every pair:

• check nums[0] with every later number
• then check nums[1] with every later number
• and so on

That works, but it takes O(n^2) time because there can be a lot of pairs.

Optimized approach

Instead of searching forward every time, we store what we have already seen in a hash map.

For each index i:

1. compute target - nums[i]
2. check whether that complement already exists in the map
3. if it does, we are done
4. if it does not, store nums[i] with its index

The nice part is that hash map lookup is fast, so the whole solution becomes one pass.

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

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];

            if (seen.containsKey(complement)) {
                return new int[] {seen.get(complement), i};
            }

            seen.put(nums[i], i);
        }

        return new int[] {};
    }
}

Dry run

Take nums = [2, 7, 11, 15] and target = 9.

• start with an empty map
• at index 0, value is 2, so we need 7
• 7 is not in the map, so store 2 -> 0
• at index 1, value is 7, so we need 2
• 2 is already in the map at index 0

So the answer is [0, 1].

Common mistakes

1. Storing the current number before checking the complement

If you do that, some variants of the problem can accidentally match the same element with itself.

2. Returning the values instead of the indices

The question wants positions, not the actual pair of numbers.

3. Forgetting that the map should store index information

A set is not enough here because we need to know where the earlier number came from.

Complexity

Time Complexity: O(n)

Space Complexity: O(n)

We scan the array once, and in the worst case we store almost every number in the map.