Problem

Given an array of integers, return the two distinct indices whose element values add up to a specific target. If no solution exists, return [-1,-1]. You can assume there will not be multiple solutions. 1

Examples:

Example 1
nums = [2, 11, 7, 15], target = 9
nums[0] + nums[2] = 2 + 7 = 9
return [0, 2]
Example 2
nums = [3, 10, -1, 10], target = 3
no solution exists
return [-1, -1]

Solution

We need to find the one pair of elements that add up to target. Specifically, we need to find the indices i and j in nums that make the following equation true.

  target = nums[i] + nums[j]

Brute force solution

The most straightforward approach is to check all possible combinations of elements until we find a pair that adds up to target. We can do this with a double loop over nums.

Python

def twoSum(self, nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return [-1, -1]

Java

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[] { -1, -1 };
}

Javascript

var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return [i, j];
            }
        }
    }
    return [-1, -1];
};

C#

public int[] TwoSum(int[] nums, int target) {    
    for (int i = 0; i < nums.Length - 1; i++) {
        for (int j = i + 1; j < nums.Length; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[] { i, j };
            }
        }
    }
    return new int[] { -1, -1 };
}
  • Time complexity is O(n2)
  • Space complexity is O(1)

Using a hash table

The brute force approach above makes good use of space, but it takes too long. How can we get to a solution faster? The key is to leverage the given relationship between the two array elements and target.

When we’re visiting an element i in nums, the given equation target = nums[i] + nums[j] allows us to deduce what the other value, nums[j] needs to be in order to satisfy the equation. All we need is an efficient way to check if that value exists within nums. What’s a good data structure to use for efficient lookups? A hash table.

For each element in nums, if we save its value in a hash table, then we can use the given equation when visiting other elements in the array to do an O(1) lookup2 to see if the pair adds up to target. So when we visit the element at index i, we can check the hash table to see if there exists an element whose value is equal to target - nums[i].

Since the solution we’re after here is to return the indices that add up to target, we’ll also use the hash table to store the associated index for each key value.

Python

def twoSum(self, nums, target):
    val_to_index = {}
    for i in range(len(nums)):
        if target - nums[i] in val_to_index:
            return [val_to_index[target - nums[i]], i]
        val_to_index[nums[i]] = i
    return [-1, -1]

Java

public int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> valToIndex = new HashMap<Integer, Integer>(nums.length);
    for (int i = 0; i < nums.length; i++) {
        if (valToIndex.containsKey(target - nums[i])) {
            return new int[] { valToIndex.get(target - nums[i]), i };
        }
        valToIndex.put(nums[i], i);
    }
    return new int[] { -1, -1 };
}

Javascript

var twoSum = function(nums, target) {
    const valToIndex = {};
    for (let i = 0; i < nums.length; i++) {
        if (target - nums[i] in valToIndex) {
            return [valToIndex[target - nums[i]], i];
        }
        valToIndex[nums[i]] = i;
    }
    return [-1, -1];
};

C#

public int[] TwoSum(int[] nums, int target) {    
    Dictionary<int, int> valToIndex = new Dictionary<int, int>(nums.Length);
    for (int i = 0; i < nums.Length; i++) {
        if (valToIndex.ContainsKey(target - nums[i])) {
            return new int[] { valToIndex[target - nums[i]], i };
        }
        valToIndex[nums[i]] = i;
    }
    return new int[] { -1, -1 };
}
  • Time complexity is O(n)
  • Space complexity is O(n)
Footnotes

  1. Problem adapted from the Two Sum problem on Leetcode ↩

  2. Lookup time in a hash table is not strictly O(1) time, it’s amortized O(1) time. See this discussion on Stack Overflow. ↩