Two Sum

Easy Arrays & Hashing Two Sum Original on LeetCode

Two Sum is a easy arrays & hashing problem solved with the two sum pattern. The best approach, optimal (one-pass hash map), runs in O(n) time and O(n) space. Below are 2 approaches in Java, from brute force up.

Problem

You get an integer array nums and an integer target. Return the indices of the two numbers that add up to target.

Exactly one pair works, and you cannot use the same index twice. The two indices can be returned in any order.

Examples

Example 1

Input: nums = [3, 8, 11, 5], target = 16
Output: [2, 3]
Why: nums[2] + nums[3] = 11 + 5 = 16.

Example 2

Input: nums = [4, 4, 1], target = 8
Output: [0, 1]
Why: The same value can appear twice, but each index is used once.

Constraints

2 <= nums.length <= 10^4
-10^9 <= nums[i], target <= 10^9
Exactly one valid pair exists.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Brute force	`O(n²)`	`O(1)`
Optimal (one-pass hash map)	`O(n)`	`O(n)`

1Brute force

TimeO(n²)Every pair is checked once: n(n - 1) / 2 pairs.

SpaceO(1)Only two loop indices.

Try every pair of indices and return the first pair whose values add up to the target.

Loop i from 0 to n - 1.
Loop j from i + 1 to n - 1.
If nums[i] + nums[j] == target, return [i, j].

Java

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];
    }
}

2Optimal (one-pass hash map)

TimeO(n)One pass; each map lookup and insert is O(1) on average.

SpaceO(n)The map can hold up to n entries.

Walk the array once. For each number, its partner is target - nums[i]. Keep a map from value to index of everything seen so far; if the partner is already in the map, you have the pair.

Create an empty map from value to index.
For each index i, compute need = target - nums[i].
If need is in the map, return [map.get(need), i].
Otherwise store nums[i] -> i and continue.

Java

class Solution {
    public 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 };
            }
            seen.put(nums[i], i);
        }
        return new int[0];
    }
}

Edge cases to test

Duplicate values that together make the target, like [4, 4] with target 8
Negative numbers and zero
The pair is the first and last element

Hints

Hint 1

For each number x, which exact value would complete the pair?

Hint 2

Can you look that value up in O(1) instead of scanning for it?

FAQ

What is the best time complexity for Two Sum?

Optimal (one-pass hash map) runs in O(n) time and O(n) extra space. One pass; each map lookup and insert is O(1) on average.

Which pattern does Two Sum use?

It is a arrays & hashing problem that uses the two sum pattern. Other problems with the same pattern: 3Sum.

Is there a brute force solution for Two Sum?

Yes. Brute force takes O(n²) time and O(1) space. Try every pair of indices and return the first pair whose values add up to the target.

Which edge cases should I test for Two Sum?

Duplicate values that together make the target, like [4, 4] with target 8; Negative numbers and zero; The pair is the first and last element.