Interview series II: sum of two elements

I was asked such an interview question.

Given an unsorted array of positive integers, and also a target value K, find two elements that sum up to K.

So I suggested, sort the array first, and then start from the last (maximum) element that is smaller than K, x_max and then use binary search to find K-x_max. Well the complexity for sorting is O(n log n) and for finding is another O(n log n). Any improvement if the array is sorted? I stuck there, 5 seconds later, he tipped me with something like how about using two index pointers. WOW, great hint. Now the complexity for this step is O(n). Below is one solution.

#include <iostream>

using namespace std;

void quickSort(int *arr, int left, int right) {
	if(left>=right) {return;}
	int Start=left;
	int End = right;
	int pivot=(left+right)/2;
	int pivotV=*(arr+pivot);
	int tmp;

	while(left<right) {
		if(*(arr+left) <= pivotV) {
			left++;
		}
		if(*(arr+right)>=pivotV) {
			right--;
		}
		if(*(arr+left)>pivotV && *(arr+right)<pivotV) {
			tmp=*(arr+left);
			*(arr+left)=*(arr+right);
			*(arr+right)=tmp;
			left++;
			right--;
		}
	}
	*(arr+pivot)=*(arr+right);
	*(arr+right)=pivotV;
	quickSort(arr, Start, left-1);
	quickSort(arr, right+1, End);
}

void ksum(int *arr, int len, int k) {
	int left, right, ktmp;
	left=0;
	right=len-1;
	while(left<right) {
		ktmp=*(arr+left)+*(arr+right);
		if(ktmp==k) {
			cout << *(arr+left) << " + " << *(arr+right) << " = " << k << endl;
			return;
		} else if(ktmp>k) {right--;} else {left++;}
	}
	cout << "Couldn't find the two elements!\n";
	return;
}

int main() {
	int a[10]={10,3,4,9,8,7,2,1,5,6};
	quickSort(a, 0, 9);
	ksum(a, 10, 12);
	return 0;
}

Comments are closed.