Find two elements in an array such that their sum equals ‘K’. (Method 2)

Question: Given an array of n elements. Find two elements such that their sum is equal to a given element ‘K’ ?

Input: arr [] = {42, 23, 15, 16, 8, 4} and element K = 58
Output: 16, 42

We discussed the approach to this problem using 2 loops in this post. But obviously this was not a good approach as it had a time complexity of O(n²). The time taken to solve such a problem if the array has elements in range of million will be very high. We need to optimize this approach.

The steps involved in this algorithm will be:-

• Sort the array. This operation takes a time of O(nlog(n))
• Now maintain a variable lowIndex = 0 and highIndex = size-1.
• Compute sum = arr[lowIndex] + arr[highIndex].
• If (sum == K), then simply return the two variable.
• If (sum < K), that means we need to add a bigger element to the sum, which can be obtained if we increment lowIndex, so

  if(sum<K)
      lowIndex++;
  

• If (sum>K), that means we need to add a smaller number, the smaller number can be found if we decrement highIndex, so

  if(sum>;K)
      highIndex--;
  

• We can repeat this process until we find the two digits. Else we return that no elements are found.

Here is an implementation of the above algorithm.

void twoElementsSumK(int arr[], int size, int K)
{
	//first sort the array
	quickSort(arr,size);

	//maintain the low and high index
	int lowIndex = 0;
	int highIndex = size-1;

	while(lowIndex < highIndex)
	{
		//get the sum
		int temp = arr[lowIndex] + arr[highIndex];

		//return if we find a match
		if(temp == K)
		{
			printf("The elements are :- %d %d",arr[lowIndex],arr[highIndex]);
			return;
		}

		//to change the low and high index
		if(temp < K)
			lowIndex++;
		else
			highIndex--;
	}
}

Time Complexity:- O(nlog(n))
Space Complexity:- O(1)

You can download the working example of code from here. Use your favorite text editor to open it (Notepad++, vim, gedit)

Method 3 – Use a hash table

We can also solve this problem using a hash table. Since out objective is to find two indexes of the array whose sum is K. Let us say those indexes are X and Y. That means arr[X] + arr[Y] = K.

What we need is, for each element of the input array arr[X], check whether K – arr[X] also exists in the input array. Now, let us simplify that searching with a hash table.

Algorithm:

• For each element of the input array, insert into the hash table. Let us say the current element is arr[X].
• Before proceeding to the next element we check whether K – arr[X] also exists in the hash table or not.
• Existence of such number indicates that we are able to find the indexes.
• Otherwise, proceed to the next input element.

Time Complexity:- O(n), considering the fact that searching in hash table takes time O(1).
Space Complexity:- O(n), to create and maintain the hash table.