Java LeetCode Two Sum Solution Explained Step by Step

2025-08-04

If you are studying for coding interviews, Two Sum is one of the friendliest problems to practice. It shows up often because it tests three things interviewers care about: how you translate a short English spec into code, how you reason about time and space, and whether you reach for the right data structure under pressure.

Below is a clean, step by step path from the simple approach to the optimal Java solution. I will also show you a short proof of correctness, common mistakes, and a tiny JUnit test you can paste into your IDE.

Problem recap

You are given an array nums and a target integer target. Return the indices of the two numbers such that they add up to target. You can assume exactly one valid answer and you may not use the same element twice. Return the indices in any order.

Example

nums = [2, 7, 11, 15], target = 9

Answer: [0, 1] because nums[0] + nums[1] = 2 + 7 = 9.

Step 1: Start simple with brute force

Think first, code second. The most direct way is to try every pair. That is O(n^2) time and O(1) extra space.

public class TwoSumBruteForce {
    public static 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};
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

This passes small tests and is a good sanity check. It will not scale.

Step 2: Optimize with a hash map in one pass

Key idea: when you are at nums[i], the partner you need is target - nums[i]. If you have already seen that partner earlier, you are done. A hash map gives you constant time lookups.

Use a map from number to its index. While scanning, for each num, compute need = target - num. If need exists in the map, return [map.get(need), i]. Otherwise, put num -> i in the map and continue.

Time O(n)

Space O(n)

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

public class TwoSum {
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (seen.containsKey(need)) {
                return new int[]{seen.get(need), i};
            }
            // Put current number after the check to avoid using the same element twice
            seen.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

Walkthrough on the classic example

nums = [2, 7, 11, 15], target = 9

i = 0, num = 2, need = 7. Map is empty, store 2 -> 0.
i = 1, num = 7, need = 2. Map has 2 -> 0. Return [0, 1].

That is the full story.

Why this is correct

Invariant: at index i, the map stores every value from indices 0..i-1 and the index where it first appeared. If there exists j < i with nums[j] + nums[i] = target, then nums[j] = target - nums[i] which we check with one lookup. Because LeetCode guarantees exactly one solution, the first match we find is valid and we can return immediately.

Common mistakes and how to avoid them

Putting into the map before you check.

If you insert first, arrays with target = 2 * nums[i] can cause you to match the same index twice. Insert only after the check.
Using value as a key but overwriting earlier indices when duplicates appear.

The single pass pattern above is safe because you return as soon as you find the partner. If you want to store first occurrence only, check containsKey before put.
Returning values instead of indices.

The problem wants indices. Your map holds indices. Return indices.
Forgetting negative numbers or zero.

The map approach works fine with negatives and zero.
Using long when not needed.

Regular int is fine for standard constraints. If you are working with very large sums elsewhere, adjust types, but here keep it simple.

Optional: Two pointers variant with index recovery

Only use this when the interviewer says indices do not have to correspond to original order or when the array is sorted. Two pointers work after you sort a copy and then map back to original indices.

import java.util.*;

public class TwoSumTwoPointers {
    public static int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        int[][] pairs = new int[n][2]; // [value, index]
        for (int i = 0; i < n; i++) {
            pairs[i][0] = nums[i];
            pairs[i][1] = i;
        }
        Arrays.sort(pairs, Comparator.comparingInt(a -> a[0]));
        int l = 0, r = n - 1;
        while (l < r) {
            int sum = pairs[l][0] + pairs[r][0];
            if (sum == target) return new int[]{pairs[l][1], pairs[r][1]};
            if (sum < target) l++;
            else r--;
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

Time O(n log n) due to the sort. Space O(n) for the decorated array. Useful when an interviewer wants to see the two pointer pattern.

Complexity summary

Brute force: O(n^2) time, O(1) space
Hash map one pass: O(n) time, O(n) space
Two pointers with sort: O(n log n) time, O(n) space

In most standard interviews, the one pass hash map is the expected answer.

Mini checklist you can read out loud

Restate the problem and confirm exactly one solution
Ask about constraints and size of n
Start with a simple approach to show baseline thinking
Propose the hash map idea and explain the invariant
Write the code with clear variable names
Walk through one example and one edge case
State time and space
Mention follow ups if there is time

Small JUnit test you can run

import static org.junit.jupiter.api.Assertions.*;
import org.junit.jupiter.api.Test;

public class TwoSumTest {
    @Test
    void exampleCase() {
        int[] nums = {2, 7, 11, 15};
        int[] res = TwoSum.twoSum(nums, 9);
        assertArrayEquals(new int[]{0, 1}, res);
    }

    @Test
    void worksWithNegatives() {
        int[] nums = {-3, 4, 3, 90};
        int[] res = TwoSum.twoSum(nums, 0);
        // Either [0,2] or [2,0] is fine
        assertEquals(0, nums[res[0]] + nums[res[1]]);
    }

    @Test
    void worksWithDuplicates() {
        int[] nums = {3, 3};
        int[] res = TwoSum.twoSum(nums, 6);
        assertArrayEquals(new int[]{0, 1}, res);
    }
}

If your project does not have JUnit 5, you can still run the methods manually with a main method and print results.

Follow ups you should practice next

Two Sum II where the input is sorted
Two Sum IV on a binary search tree
Count the number of pairs that sum to target
Return all unique pairs that sum to target

These push you to reuse the same mental model in slightly different settings.

Final notes

Two Sum is not about memorizing code. It is about recognizing that the right data structure turns a nested loop into a single pass. Once that clicks, you will start seeing the same move in many different problems.

If you want a quick way to sanity check your reasoning steps during practice, or to study a clean explanation when you hit a wall, you can use tools that overlay your screen with guidance while you rehearse mock questions. When you are short on time and want a concise solution outline to review, this can help you learn faster.

Try StealthCoder to capture a prompt and get a solution outline you can study and explain back later: https://stealthcoder.app