Two Sum

NeetCode: Two Sum · LeetCode: 1. Two Sum · Difficulty: Easy

Given an array nums and an integer target, return the indices i < j such that nums[i] + nums[j] == target. Exactly one valid answer exists, and you may not use the same element twice.

Example

Text

Input:  nums = [3, 4, 5, 6], target = 7    Output: [0, 1]
Input:  nums = [4, 5, 6],    target = 10   Output: [0, 2]

Brute force: check every pair

LeetCode's Java signature returns an int[]. The method returns an empty array when no pair exists. The Solution class is a static nested class here so the block is one complete program.

Java

public class Main {
    static 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[] {};
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(java.util.Arrays.toString(s.twoSum(new int[] {3, 4, 5, 6}, 7)));
        System.out.println(java.util.Arrays.toString(s.twoSum(new int[] {4, 5, 6}, 10)));
    }
}

Output

[0, 1]
[0, 2]

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

Optimal: one pass with a HashMap

For each value x, the required partner is target - x. A map from value to index records everything seen so far. If the partner is in the map, return its index and the current one; otherwise store x. Looking up before inserting stops an element from pairing with itself.

Java

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

public class Main {
    static 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++) {
                Integer j = seen.get(target - nums[i]);
                if (j != null) {
                    return new int[] {j, i};
                }
                seen.put(nums[i], i);
            }
            return new int[] {};
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(Arrays.toString(s.twoSum(new int[] {3, 4, 5, 6}, 7)));
        System.out.println(Arrays.toString(s.twoSum(new int[] {4, 5, 6}, 10)));
        System.out.println(Arrays.toString(s.twoSum(new int[] {5, 5}, 10)));
    }
}

Output

[0, 1]
[0, 2]
[0, 1]

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

seen.get returns a boxed Integer, which is null when the key is missing, so the code compares it with null and never with == against another Integer. target - nums[i] is int arithmetic and wraps on overflow. LeetCode's constraints keep the values small enough that it does not.