Problem 1: Given an increasingly sorted array and a number s, please find two numbers whose sum is s. If there are multiple pairs with sum s, just output any one of them.
For example, if the inputs are an array {1, 2, 4, 7, 11, 15} and a number 15, please out two numbers 4 and 11 since 4+11=15.
Analysis: Let us firstly have a try to select two numbers (denoted as num1 and num2) of the input array. If their sum equals to s, we are fortunate because the required numbers have been found. If the sum is less than s, we may replace num1 with its next number, because the array is increasingly sorted and its next number should be greater. If the sum is greater than s, num2 can be replaced with its previous number in the sorted array, which should be less than num2.
Take the array {1, 2, 4, 7, 11, 15} and number 15 as an example. We define two pointers. At the first step, they point to the first number (also the least one) 1 and the last number (also the greatest one) 15. We move the second pointer forward to number 11, since their sum 16 and it is greater than 15.
At the second step, the two numbers are 1 and 11, and their sum 12 is less than 15. Therefore, we can move the first pointer afterward and let it point to 2.
The two numbers are 2 and 11 accordingly at the third step. Since their sum 13 is less than 15, we move the first pointer afterward again.
Now the two numbers are 4 and 11, and their sum is 15 which is the expected sum. Therefore, we have found two numbers whose sum is 15.
The process is summarized as in Table 1:
Step

Num1

Num2

Sum

Comparing with s

Operation

1

1

15

16

Greater

Select the previous number of Num2

2

1

11

12

Less

Select the next number of Num1

3

2

11

13

Less

Select the next number of Num1

4

4

11

15

Equal

Table 1: Find a pair of numbers with sum 15 out of array {1、2、4、7、11、15}
After interviewers approve our solution, we can begin to write code. The following is a piece of sample code:
bool FindNumbersWithSum(int data[], int length, int sum,
int* num1, int* num2)
{
bool found = false;
if(length < 1  num1 == NULL  num2 == NULL)
return found;
int ahead = length  1;
int behind = 0;
while(ahead > behind)
{
long long curSum = data[ahead] + data[behind];
if(curSum == sum)
{
*num1 = data[behind];
*num2 = data[ahead];
found = true;
break;
}
else if(curSum > sum)
ahead ;
else
behind ++;
}
return found;
}
In the code above, ahead is the index of the first number, and behind is the index of the second number. Since we only need to scan the input array once, its time complexity is O(n).
Problem 2: Given an array, please determine whether it contains three numbers whose sum equals to 0.
Analysis: This problem is also required to find some numbers with a given array and sum, it is similar to the first problem. We may get some hints from the solution above.
Since the input of the previous problem is an increasingly sorted array, we can also firstly sort the input array increasingly. Secondly we scan the array. When we reach the ith number with value n, we try to find whether there are two numbers whose sum is –n in the array excluding the ith number.
It is time for us to write some code. We modify the function FindNumbersWithSum above a little bit:
bool FindNumbersWithSum(int data[], int length, int sum, int excludeIndex)
{
bool found = false;
int ahead = length  1;
int behind = 0;
while(ahead > behind)
{
if(ahead == excludeIndex)
ahead ;
if(behind == excludeIndex)
behind ++;
long long curSum = data[ahead] + data[behind];
if(curSum == sum)
{
found = true;
break;
}
else if(curSum > sum)
ahead ;
else
behind ++;
}
return found;
}
It determines whether there are two numbers whose sum is sum in array data excluding the number with index excludeIndex. We can determine whether there are three numbers in an array with sum 0 based on this function:
bool HasThreeNumbersWithSum0(int data[], int length)
{
bool found = false;
if(data == NULL  length < 3)
return found;
std::sort(data, data + length  1);
for(int i = 0; i < length; ++i)
{
int sum = data[i];
int num1, num2;
found = FindNumbersWithSum(data, length, sum, i);
if(found)
break;
}
return found;
}
It contains two steps in function HasThreeNumbersWithSum0. It costs O(nlogn)time to sort n numbers at its first step. At its second step it costs O(n) time for each number to call FindNumberWithSum, so it costs O(n^{2}) time in the for loop. Therefore, its overall time complexity is O(n^{2}).
The discussion about these two problems is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.
The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.
What if the numbers of the array in the first question are not sorted ??
ReplyDeleteWhen numbers are not sorted, we have sort them firstly.
ReplyDeleteIs any better way than O(n^2)? I haven't figure it out.
DeleteIt would be O(nlogn) because that's how long it takes to sort.
DeleteIf it is unsorted the order will still be n^2. Because, O(nlogn + n^2)=O(n^2)
Deletecan we find all the pairs whose sum < x in o(n) ??
ReplyDelete@Harry:
ReplyDeleteIn the first case if the numbers are not sorted we can still do it in O(n) but we also need O(n) space. Get a set containing numbers (target  number[i]) and then scan the array again to see if it contains number[i]. If there can be duplicated you need to change the set to a map.
insert n elements into hashtable takes nlogn time
Deleteinsert n elements into a hashtable takes n time
Deletenlgn is possible
ReplyDeleteHa, I just interviewed this question by facebook.
ReplyDeleteI think a more intuitive way of doing Problem 2 would be 3 nested for loops.
ReplyDeleteThis is the code in Python that explains my idea:
def facebook(array):
if len(array) < 3:
return False;
else:
for i in range(0, len(array)  2):
for j in range(1, len(array)  1):
for k in range(2, len(array)):
if array[i] + array[j] + array [k] == 0:
return True
return False
This solution in not correct, and it costs O(n^3) time. It is not correct because it is possible for i=j=k, so you might be counting the same entry more than once.
DeleteAbout the method [FindNumbersWithSum] in problem2, I think we can initiate behind = excludeIndex + 1, instead of 0;
ReplyDeleteFor Problem 1, We need to short the array (nlogn). how could be your complexity is O(n)
ReplyDeleteWe only need to scan the array once, so the complexity is O(n).
DeleteFrom the sorted array, take an element Xn one by one. The problem becomes searching for another number (SXn) in the array. Overall, complexity is O(nlogn), but it gives all the pairs
ReplyDeletehere a O(n) solution: http://ideone.com/bfSkv1
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteProblem 2 can be optimized further.
ReplyDeleteFirst time through the for loop, we call FindNumbersWithSum
with excludeIndx = 0. If we cannot find a pair, it means
that the number with index 0 will never be in the final soln.
Second time through the for loop, we call FindNumbersWithSum
with excludIdx = 1. Here we should be excluding all indices
<= 1, instead of just excluding 1.
The time complexity will still be O(n^2) though