Pair with given sum in array

Pair with given sum in array

Given an array a[] and a number X, find two elements or pair in array whose sum is equal to X. This problem is known as find pair of given sum in array For example:

Given array : [3,4,5,1,2,6,8] X = 10
Answer could be (4,6) or (2,8).

Please do not jump to solution directly. Ask a few question. First question one must ask about this question is that if order of elements in array is sorted or not.  If answer is NO, then solution needs to changed.
Second question should be if duplicates in array is allowed? Third question is whether returning first pair is enough or all such pairs with sum equal to X are to be returned. Fourth is to ask if there can be negative numbers in array?

Well, above four question will give you a time to think about the solution too and calm your nerves too.
Before going to solution, let me clarify what interviewer is looking for in solution of this question.
1.First of all, he wants to understand if you can traverse array properly, with both lower and higher bounds.
2. Second, he wants to check, if you can think of way where input is not modified and solution is given?
3. Third, to understand if you can think of and use hash or any other data structure?

Solutions to find a pair with given sum in array

Method 1
This method is very simple and idea comes from first question we asked to interviewer that is if array is sorted or not. If array is sorted follow below steps and you are done.

1. Initialize left = 0 and right = n-1 (n is number of elements in array)
2. While left < right
   2.a get currentSum = a[left] + a[right]
   2.b if currentSum > X, then decrement right, right--;
   2.c if currentSum < X,then increment left, left++;
   2.d if currentSum == X, then return the pair.

Now if array is not sorted then? Above method works with sorted array only. No problem. Before applying method, sort the array using quick sort or merge sort.
Complexity of method 1 to find a pair with given sum in array with sum X is dependent on sorting algorithm used. If it is merge sort, complexity is O(log n) with added space complexity of O(n). If quick sort is used, worst case complexity is O(n2) and no added space complexity.

Pair with give sum in array implementation

#include <stdio.h>
#include <stdlib.h>

int cmpfunc (const void * a, const void * b)
{
   return ( *(int*)a - *(int*)b );
}
void find_pair(int a[], int n, int sum){
	int i = 0;
	int j = n-1;
 
	qsort(a,n, sizeof(int), cmpfunc);
 
	while(i<j){
		int currentSum = a[i] + a[j];
		if(currentSum == sum){
			printf("%d, %d", i,j);
			return;
		}
		else if(currentSum < sum) i++;
		else j--;
	}
	printf("No pair found");
 
}
int main(void) {

	int a[] = {3,6,5,2,7,1,8};
	int n = sizeof(a)/sizeof(a[0]);
	find_pair(a,n,10);
	return 0;
}

Method 2 

In first method, we are modifying the input and also complexity of solution is dominated by preprocessing step (sorting) and not the actual solution.Can we do better than O(n log n)?

This method satisfies third need of interviewer, that is solution without modifying the input. Let’s use hash.Algorithm is very simple as given below:

1. Create an hash with sufficient size (explain on this) 
2. Start from index 0 of array
3. For each element of array
   3.a Check if that number in hash. 
   3.b If yes, return pair of current number and number in hash
   3.c.If not, then subtract number from X and store result in hash

In this method, we are scanning array only once and not changing the input. Complexity is O(n), however there is added space complexity of hash. What should be maximum size of hash in this part. One way is that we declare hash with size equal to largest element in array. There is slightly better option is we get the difference between lowest and highest elements and define hash with that size.  In short, space complexity of this solution depends on range of numbers in input.

If there are negative numbers in array, hash method will not work in C. Will work in languages which have HashMaps in-built. Or we have to do some preprocessing like adding a absolute of smallest negative number to all elements. That’s where our fourth question above helps us to decide.

Code for finding pair with sum using hash

#include <stdio.h>
#define SENTINEL -1
 
void find_pair(int a[], int n, int sum){
	int hash[sum+1];
	for(int i=0; i<=sum; i++){
		hash[i] = SENTINEL;
	}
	for(int i=0; i<n;i++){
		int val = sum - a[i];
		if(a[i] <= sum){
			if(hash[a[i]] != SENTINEL){
			    printf("%d, %d", val, a[i]);
			    return;
		    }
		    hash[val] = i;
		}
	}
}
 
int main(void) {
 
	int a[] = {3,6,5,2,7,1,8};
	int n = sizeof(a)/sizeof(a[0]);
 
	find_pair(a,n,10);
 
	return 0;
}

Please share if there is some error or suggestion to improve. We would love to hear what you have to say. Sharing is caring.