Crack the Backend

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 exactly one solution exists, and you may not use the same element twice. Return the answer in any order.

The same element cannot be used twice (e.g. nums = [3,3], target = 6 → use the two indices 0 and 1, not the same index twice).
Exactly one valid pair exists; no need to handle "no solution" or multiple solutions.

Key Observations

For each index i, we need to know whether target - nums[i] has already been seen at some index j < i. If yes, the pair is (j, i).
A hash map from value to index lets us check "have we seen target - nums[i]?" in O(1) and retrieve its index. As we scan, we add (nums[i], i) to the map after checking, so future indices can find nums[i] as a complement.
One pass is enough: when we are at i, the map contains all values from indices 0..i-1, so if the complement of nums[i] exists in the array and is not at i, it must be in the map.

Approach

High-level: Scan the array once. For each nums[i], check if target - nums[i] is already in a hash map (value → index). If yes, return [map.get(target - nums[i]), i]. Otherwise, put (nums[i], i) in the map and continue.

Steps:

Create a Map<Integer, Integer> (value → index). For each i from 0 to n-1: let diff = target - nums[i]. If map.containsKey(diff), return new int[]{map.get(diff), i}. Else map.put(nums[i], i).
(Guaranteed to find before the loop ends.)

Implementation

Java

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
        int diff = target - nums[i];

        if (map.containsKey(diff)) {
            return new int[]{map.get(diff), i};
        }

        map.put(nums[i], i);
    }

    return new int[]{};
}

Test Cases

Example 1

Input

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

Expected

[0,1]

Explanation

nums[0]+nums[1]=9.

Complexity Analysis

Time: O(n).
Space: O(n).

Follow-ups

Two Sum II (sorted array): use two pointers for O(1) space.