3.Two Sum

EasyBlind 75Arrays & Hashing · 3/9

Problem

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

Exactly one valid pair is guaranteed to exist, and you may not use the same element twice (the two indices must be different). The answer can be returned in any order.

Examples

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

Input:  nums = [3, 2, 4], target = 6
Output: [1, 2]
Explanation: 2 + 4 = 6. Index 0 (value 3) cannot be paired with itself.

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
Exactly one valid answer exists.

💡 Key Insight

For each number x, the only partner that works is its complement target - x. Instead of searching the array for the complement every time, remember every value seen so far in a HashMap<value, index>. Then "does the complement exist to my left?" becomes an O(1) lookup, and one pass finds the pair.

Brute Force

TimeO(n²)SpaceO(1)

Intuition

Try every pair of distinct indices (i, j) and return the first one whose values sum to target.

Algorithm

For i from 0 to n - 1:
For j from i + 1 to n - 1:
If nums[i] + nums[j] == target, return [i, j].
(Unreachable given the guarantee) return an empty array.

Visualization

nums = [3, 2, 4], target = 6

i=0 (3): 3+2=5 ✗, 3+4=7 ✗
i=1 (2): 2+4=6 ✓ → return [1, 2]

Code

java

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) { // j > i, so an element is never paired with itself
                if (nums[i] + nums[j] == target) {
                    return new int[] {i, j};
                }
            }
        }
        return new int[0];
    }
}

Complexity

Time: O(n²) — every pair is examined in the worst case.
Space: O(1) — only loop indices.

Sorting + Two Pointers

TimeO(n log n)SpaceO(n)

Intuition

In a sorted array, two pointers at both ends can home in on the target: if the sum is too small, move the left pointer right to increase it; if too large, move the right pointer left. Sorting loses the original indices, so we sort an array of indices by their values instead of sorting nums itself.

Algorithm

Build Integer[] idx = {0, 1, ..., n-1} and sort it by nums[idx].
Set lo = 0, hi = n - 1.
While lo < hi: compute sum = nums[idx[lo]] + nums[idx[hi]].
- If sum == target, return [idx[lo], idx[hi]].
- If sum < target, lo++; else hi--.

Visualization

nums = [3, 2, 4], target = 6
indices sorted by value: [1(2), 0(3), 2(4)]

lo→2, hi→4: sum 6 == 6 → return [1, 2]

Code

java

import java.util.Arrays;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) {
            idx[i] = i;
        }
        // Sort indices by their value so we keep the original positions
        Arrays.sort(idx, (a, b) -> Integer.compare(nums[a], nums[b]));

        int lo = 0, hi = n - 1;
        while (lo < hi) {
            long sum = (long) nums[idx[lo]] + nums[idx[hi]]; // long avoids overflow
            if (sum == target) {
                return new int[] {idx[lo], idx[hi]};
            } else if (sum < target) {
                lo++; // need a bigger sum
            } else {
                hi--; // need a smaller sum
            }
        }
        return new int[0];
    }
}

Complexity

Time: O(n log n) — sorting the index array dominates; the two-pointer scan is O(n).
Space: O(n) — the boxed index array.

One-Pass Hash MapOptimal

TimeO(n)SpaceO(n)

Intuition

Walk the array once. At index i, the needed partner is complement = target - nums[i]. If that complement was seen earlier, its index is stored in the map and we are done. Otherwise, record nums[i] → i so later elements can find it. Checking before inserting guarantees we never pair an element with itself.

Algorithm

Create Map<Integer, Integer> seen (value → index).
For each index i:
- complement = target - nums[i].
- If seen contains complement, return [seen.get(complement), i].
- Put nums[i] → i into seen.
Return an empty array (unreachable).

Dry Run

flowchart TD
    A["i=0, num=2<br/>need 7, seen = {}"] -->|"7 missing, store 2 at 0"| B["i=1, num=7<br/>need 2, seen = {2:0}"]
    B --> C{"2 in seen?"}
    C -->|"yes, at index 0"| D["return [0, 1]"]

Code

java

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

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>(); // value -> index
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            Integer j = seen.get(complement);
            if (j != null) {
                return new int[] {j, i}; // complement appeared earlier
            }
            seen.put(nums[i], i); // insert after the check, so i is never paired with itself
        }
        return new int[0];
    }
}

Complexity

Time: O(n) — each element is looked up and inserted once, O(1) average each.
Space: O(n) — the map may hold up to n - 1 entries.

Complexity Comparison

Approach	Time	Space
Brute Force	O(n²)	O(1)
Sorting + Two Pointers	O(n log n)	O(n)
One-Pass Hash Map	O(n)	O(n)

Common Pitfalls

Inserting nums[i] into the map before checking — with nums = [3, ...], target = 6 you would return [0, 0].
Sorting nums directly and returning the sorted positions — the problem asks for the original indices.
Duplicates like [3, 3]: a two-pass map that first inserts everything overwrites the first 3's index; the one-pass version handles it naturally.
Returning the values instead of the indices.