Two Sum

Problem in Plain English

Given an integer array and a target value, return the indices of the two numbers that add up to the target. Exactly one valid pair exists and the same element cannot be used twice.

Problem Statement

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

You may assume that each input has exactly one valid solution, and you may not use the same element twice. You can return the answer in any order.

Constraints

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

Examples

Example 1

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

Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2

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

The first value 3 would need another 3, which is absent. Values 2 and 4 add to 6 at indices 1 and 2, so the answer is [1, 2].

Example 3

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

The two 3 values occupy different positions. Neither index can be reused, but indices 0 and 1 together sum to 6.

Intuition

For each number, subtract it from the target to find the only partner value that can complete the pair. In [2, 7, 11, 15] with target 9, the partner of 2 is 7. A map remembers each earlier value and its index; when 7 arrives, its partner 2 is already stored. Checking before storing keeps the two positions distinct, even when the values are equal.

Approaches

Brute Force

Solution Details

Reveal Brute Force: intuition, complexity, and code

Intuition

Try every pair of positions and check whether the two values sum to the target. Exhaustive pairing always finds the guaranteed answer but repeats work, since each element is re-examined against everything after it.

Step-by-Step Logic

For each index i from 0 through n - 2, examine every later index j from i + 1 through n - 1. Starting j after i avoids reusing an index and checking the same pair twice.
Compute nums[i] + nums[j] and compare it with target. On Example 1, the first pair uses i = 0 and j = 1, so the sum is 2 + 7 = 9.
If the sum matches, return [i, j] immediately; otherwise continue with the next pair. Example 1 returns [0, 1] without checking the remaining pairs.
The final empty-array return is defensive; the guaranteed unique solution means valid inputs always return from the loops.

Why It Works

Every legal pair has a smaller index i and a larger index j, so the nested loops include it exactly once. They return only when those two distinct positions sum to the target. Since a solution is guaranteed, the search must find it; uniqueness means no further pair is needed.

Dry Run

Brute Force: variable states at each step
`i`	`j`	`nums[i]`	`nums[j]`	sum	result
`0`	`1`	`2`	`7`	`9`	match, return `[0, 1]`

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(1)

Let n be the array length. In the worst case the answer is the last tested pair, requiring n(n - 1)/2 checks and O(n^2) time, even though Example 1 finishes after one. Loop counters and the two-index result use constant space. With the stated bounds, sums between -2000000000 and 2000000000 fit Java int and are exact in JavaScript.

Code

Solution.java

1class Solution {2    public int[] twoSum(int[] nums, int target) {3        for (int i = 0; i < nums.length; i++) {4            for (int j = i + 1; j < nums.length; j++) {5                if (nums[i] + nums[j] == target) {6                    return new int[] { i, j };7                }8            }9        }10        return new int[0];11    }12}

Hints

Hint 1

Start by checking every pair; that works but costs

O(n^2)

time on an array of length 10^4.

Hint 2

For the value in front of you, the partner you need is fixed: target minus that value.

Hint 3

Keep values seen so far in a hash map and look up each complement before inserting the current value.

Edge Cases

The minimum size input of exactly two elements is itself the answer.
Duplicate values such as [3, 3] with target 6 need the lookup-before-insert order so one 3 does not pair with itself.
Negative values and zero work unchanged: [-3, 4, 3, 90] with target 0 returns [0, 2].
A zero at index 0 must still be found: [0, 4, 3, 0] with target 0 returns [0, 3].
If target is twice the current value, one occurrence alone is not a pair; wait for a second index.

Common Mistakes and Interview Tips

Inserting the current value into the map before the complement check, which lets an element pair with itself when target is twice its value.
Starting the brute-force inner loop at 0 instead of i + 1, which rechecks pairs and compares each element with itself.
Returning values rather than original indices answers a different question. Sorting alone also loses original positions unless they are carried along.
Using a truthiness test for a stored index misses index 0; use a membership test such as JavaScript Map.has.
Interview tip: state the map invariant before writing code, and explain why lookup-before-insert handles [3, 3] without self-pairing.

Key Takeaway

When each element seeks a fixed partner value, remembering visited elements in a hash map turns a quadratic pair search into one linear scan.