1. Two Sum

Jason Yang
11 Nov, 2025
Updated 27 Jul, 2026
Views —

Two Sum is the “hello world” of coding interviews — the cleanest place to show the brute-force-versus-hash-map trade-off that shows up in half the array problems you’ll meet. Here are both solutions in Java, and how to talk through them.

Question

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example1

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example2

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

Example3

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

Constraints

$2 <= nums.length <= 10^4$
$-10^9 <= nums[i] <= 10^9$
$-10^9 <= target <= 10^9$
Only one valid answer exists.

Follow-up

Can you come up with an algorithm that is less than $O(n^2)$ time complexity?

Intuition: from brute force to a hash map

The brute-force answer is the one everyone writes first: check every pair. Two nested loops, $O(n^2)$ time, and it passes. But that follow-up line is a hint — “less than $O(n^2)$ ” almost always means trade memory for time.

Here’s the shift. For each number x, you’re really asking one question: have I already seen target - x? That’s a membership lookup, and a hash map answers it in $O(1)$ . So instead of scanning the rest of the array for the complement, you remember what you’ve walked past and let the map do the search. One pass, $O(n)$ .

Solution

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

public class TwoSum {

    /**
     * Brute force
     * TC: O(n^2), for double loop
     * SC: O(1), no extra space allocated
     */
    public int[] sol1(int[] nums, int target) {

        for (int i = 0; i < nums.length - 1; i++) {

            for (int j = i + 1; j < nums.length; j++) {

                if (nums[i] + nums[j] == target) {
                    return new int[] { i, j };
                }
            }
        }
        return new int[] {};
    }

    /**
     * TC: O(n), single pass
     * SC: O(n), the HashMap can hold up to n entries
     */
    public int[] sol2(int[] nums, int target) {

        // <target - nums[i], i>
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {

            if (map.containsKey(nums[i])) {
                return new int[] { map.get(nums[i]), i };
            }
            // store the complement so a later element can find this index
            map.put(target - nums[i], i);
        }
        return new int[] {};
    }

    public static void main(String[] args) {
        TwoSum t = new TwoSum();

        int[] nums = { 1, 4, 7, 8 };
        int target = 11;

        Utils.printArray(t.sol2(nums, target));
    }
}

Reading the hash-map solution

One detail in sol2 trips people up: it stores the complement as the key, not the number itself.

map.put(target - nums[i], i);   // key = the value that would complete a pair with nums[i]

So when a later element equals a key already in the map, you’ve found the earlier index that pairs with it. It’s the mirror image of the more common “store nums[i], look up target - nums[i]” variant — both are correct, they just pick a different thing to remember. Either is fine; the point is to say out loud which one you’re doing so whoever’s reading can follow.

Edge cases worth naming out loud

Duplicates ([3,3], target 6): this works because the check happens before the insert, so the second 3 finds the first one already sitting in the map.
The same element twice: it can’t happen. You only ever match against indices stored on earlier iterations, which are strictly before the current one.
No valid pair: the problem guarantees exactly one solution, so the trailing return new int[] {} is just defensive. In real code I’d rather throw or return an Optional than hand back an empty array — a silent empty return is the kind of thing that quietly becomes a bounds bug two layers up the call stack.

Complexity and the trade-off

Approach	Time	Space
Brute force	$O(n^2)$	$O(1)$
Hash map	$O(n)$	$O(n)$

You’re spending $O(n)$ memory to cut a factor of $n$ off the runtime. At this constraint ( $n \le 10^4$ ) both pass comfortably, but the hash-map version is what the follow-up is fishing for, and it’s the one that keeps its shape as the input grows. Coming from backend work, this is the same instinct as adding an index to dodge a full table scan: pay a little space, save a lot of time.

In an interview

Say the brute force out loud first — it shows you see the baseline — then pivot: “but I can trade space for time with a hash map.” Write the one-pass version, run one example through it ([2,7,11,15], target 9) so the interviewer sees the map fill up, and flag the duplicate case before they poke at it. That arc — baseline, optimization, edge cases — is usually what’s actually being graded, more than landing the optimal solution on the first try.

Once the complement trick clicks, 3Sum is the natural next step — it fixes one number and reduces the rest to a Two Sum (on a sorted array it uses two pointers rather than a hash map). The same “have I seen this value?” idea is the whole trick behind Contains Duplicate.

References

#LeetCode