Problem

You are given an array of n integers and a target sum T. The goal is to determine whether or not there are two numbers x, y in A with x+y=T.

OR

Given an array of integers, find two numbers such that they add up to a specific target number.

Variant: Return the indices instead of the elements in array.

Example

Example 1:

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

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

Solution

There are three approaches to solve this problem - 1) brute force, 2) sort the array and use binary and search, and 3) Using the hashtable.  Please scroll down, if you are only interested in the best approach i.e. approach 3 using hashtables.

Method 1 : Brute Force Method

The first approach is to use brute force which gives time complexity of O(n^2) and space complexity of O(n). We basically just have to loop through the array and for each number we add it to each of other numbers and see if they sum up to 5. If so, we print out the pair. Here is the code for brute force approach:

Code

Java
void twoSum(int nums[], int target) {
    int n = arrayOfNum.length;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (arrayOfNum[i] + arrayOfNum[j] == sum)
                System.out.println("" + arrayOfNum[i] + "--" + arrayOfNum[j]);
        }
    }
}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)

Method 2A - Use Sorting and Binary Search

A better way would be to sort the array. This takes O(n log n) Then for each x in array A, use binary search to look for T-x. This will take O(nlogn). So, overall search is  O(n log n)

Complexity

  • ⏰ Time complexity: O(n log n) for sorting and O (n log n) ⇨ O(nlogn)
  • 🧺 Space complexity: O(1)

Pseudocode

Hers is how the pseudo code will look:

arr = {}; //some array
sortedArr = sort(arr);
for (i = 0; i < arr.length - 1; i++) {
    x = arr[i];
    bool found = binarySearch(sortedArr, T - x); //Search for T-x in sorted Arrary
    if (found)
        print "pair", x, T - x;
}

Problem with above approach is, what if x = T/2, then we will find the element, even though it will find the same element again.

Method 2B - Using Sorting and 2 Pointer Approach

Assuming array sorted in ascending order. Now we take first and last element, and sum them up. If sum is equal to T, we have found the pair, but if sum is greater than T, we reduce right pointer by 1, or increment left pointer otherwise.

Code

Java
private static int[] twoSum(int[] nums, int target) {
	Arrays.sort(nums);
	int left = 0;
	int right = nums.length - 1;
	while(left < right) {
		if(nums[left] + nums[right] == target) {
			return new int[] {nums[left], nums[right]};
		} else if (nums[left] + nums[right] < target) {
			left++;
		} else {
			right--;
		}
	}
	return new int[] {};
}

Complexity

  • ⏰ Time complexity: O(n log n) (From sorting it takes O(nlogn) time and for 2 pointer technique takes O(n) time)
  • 🧺 Space complexity: O(1)

Method 3 - Use Hash Table 🏆

I have already mentioned in problem in the application of hash table here. The best way would be to insert every element into a hash table (without sorting). This takes O(n) as constant time insertion. Then for every x, we can just look up its complement, T-x, which is O(1). Overall it takes will be O(n).

Pseudocode

Here is how the pseudocode will look.

Let arr be the given array.
And T be the given sum

hash = {}

for (i = 0 i < arr.length - 1; i++) { 
	// key is the element and value is its index.
	num = arr[i]
	complement = T - num
    if complement in hash and hash[complement] < i: 
	    print("Pair:", i, ",", hash[complement], "has sum", T)
	hash[num] = i
}

Code

Java

Here is the code which returns the index of the 2 numbers which add up to T:

public int[] twoSum(int[] nums, int target) {
	if (nums == null || nums.length < 2)
		return new int[] {
			-1,
			-1
		};

	Map<Integer, Integer> map = new HashMap<Integer, Integer>();

	for (int i = 0; i < nums.length; i++) {
		if (map.containsKey(nums[i])) {
			return new int[] {
				map.get(nums[i]), i
			};
		} else {
			map.put(target - nums[i], i);
		}
	}

	return new int[] {
		0,
		0
	};
}

Dry Run

For example, if we hash the example array we’ll have this hash table:

Key   Value
5        5 - 5 = 0
3        5 - 3 = 2
7        5 - 7 = -2
0        5 - 0 = 5
1        5 - 1 = 4
4        5 - 4 = 1
2        5 - 3 = 2

Here is also similar code:

private static int[] twoSum(int[] nums, int target) {
	Map<Integer, Integer> numMap = new HashMap<>();
	for (int i = 0; i < nums.length; i++) {
		int complement = target - nums[i];
		if (numMap.containsKey(complement)) {
			return new int[] { numMap.get(complement), i };
		} else {
			numMap.put(nums[i], i);
		}
	}
	return new int[] {};
}

Please let us know if you know any other approach. Thanks.

Video Explanation

Here is video explanation of same.