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(n2). 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.