*2.2K*

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^{2}). 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.