Facebook Interview Question
Country: United States
for a sorted array, 3 sum problem can be done in O(n):
1 # !/usr/bin/python
2 # -*- encoding: utf-8 -*-
3
4 array = [1, 2, 3, 4, 5, 6, 7, 8, 9]
5
6 three_sum = 15
7
8 start = 0
9 end = 8
10 while start <= end:
11 if array[start] + array[end] == three_sum:
12 print '%d\t%d\t=\t%d' % (array[start], array[end], three_sum)
13 break
14 elif array[start] + array[end] > three_sum:
15 end -= 1
16 elif array[start] + array[end] < three_sum:
17 start += 1
The complexity doesn't make any sense. First you say best known is O(n^2) and then you claim that a sorted array can be done in O(n)... Sorting takes O(n log(n)) which would then give an upper bound instead of O(n^2)
O(nlogn) + O(n^2) = O(n^2). Constant memory! Can be done using a set also but I am not sure if the time complexity can be reduced.
public static int[] zerosum(int[] array) {
if(array == null) return null;
int n = array.length;
if(n < 3) return null;
Arrays.sort(array);
for(int i = 0; i < n - 1; i++) {
int j = i + 1;
int k = n - 1;
while(k > j) {
int sum = array[i] + array[j] + array[k];
if(sum == 0) return new int[] {array[i], array[j], array[k]};
if(sum < 0) j++; else k--;
}
}
return null;
}
Well, constant memory with the caveat that you will destroy the original array. For most situations, destroying inputs is undesirable, and so this needs linear space to make a copy of the array. Still, the constant factor on the linear space is less than for a set.
what about
- if all the numbers are zero,
- if all numbers are positive,
- if all numbers are negative,
- it there are multiple sets that sum to zero,
In above while loop if sum > 0 then we are in infinite loop
I guess this works but just one suggestion. As the array is sorted, when a[i] is a positive number you could return from the function because a[j] and a[k] would anyway be positive number (again as they are sorted) and a sum of 3 positive numbers can never be 0
Also, your program will only return 1 combination of i,j,k (if exists) and return from there but there could be multiple combinations of i,j,k that could be the answers (not a big deal, you gave the idea but just saying)
vijay, i believe you need to change one variable; instead of decrementing k(k=n-1), increment(k=i+2). suppose array contains 6 number and leads to 2 0's it will miss the first pair. see modified code
int main(){
int array[] = {-2,-1,3,20,-30,10};
//int n=sizeof(array[]);
int n = sizeof(array)/sizeof(int);
printf("\n Length-- %d --i\n",n);
for(int i = 0; i < n - 1; i++) {printf("\n\ni %d",i);
int j = i + 1; printf("\nj %d",j);
int k = i + 2;//n - 1;
printf("\nk %d",k);
while(k > j) {
int sum = array[i] + array[j] + array[k];
if(sum == 0) printf("\n %d %d %d\n",array[i], array[j], array[k]);
if(sum < 0) j++; else k--;
}
}
// return null;
}
Hi,
How about we use a hashtable.
We take every two elements in the original array and check of the negative of their sum is there in the hash table. This is also O(n^2) and we dont destroy the original array.
Yes, this is a quadratic time and linear space algorithm; without sorting. Count the occurrence of each number then check each pair of numbers and see whether the third number is in the map. You need the occurrence for inputs like {-4, 2, 100} where there is no result if you (correctly) don't use a number more than once (if you would just simply use a Set then you might use up a number more than once and the above input would give a false result like {-4, 2, 2}).
private static List<Integer> find(int[] arr) {
Map<Integer, Integer> occs = new HashMap<>();
for (int i : arr) {
Integer occ = occs.get(i);
if (occ == null) {
occ = 0;
}
occ++;
occs.put(i, occ);
}
for (int i = 0; i < arr.length; i++) {
occs.put(arr[i], occs.get(arr[i]) - 1);
for (int j = 0; j < arr.length; j++) {
if (j == i) {
continue;
}
occs.put(arr[j], occs.get(arr[j]) - 1);
int third = -(arr[i] + arr[j]);
Integer thirdOcc = occs.get(third);
if (thirdOcc != null && thirdOcc > 0) {
List<Integer> res = new ArrayList<>();
res.add(arr[i]);
res.add(arr[j]);
res.add(third);
return res;
}
occs.put(arr[j], occs.get(arr[j]) + 1);
}
occs.put(arr[i], occs.get(arr[i]) + 1);
}
return null;
}
Well you need to compute N sets of 3 elements where N is P(n, 3) and while creating them sum up the elements. You need one pass through the array to create N sets of 3. For e.g. if you have array of 3 elements (2, 0, -2) and you want to find 2 elements with 0 sum then you would have the following sets after one pass (2, 0) (2, -2) (0, -2) and you can figure that the second set is 0 sum.
This requires more space but is faster than O(n^2)
This turns out to be a combination problem.
In general given "N" elements and asked to find a subset of "R" elements, it is required to find all the combinations of ( R-1) size from (n-1) elements, and compare with "N" element which is taken as reference and this happens "N" times.
Hence for any give problem to find out the subset of " R " elements it takes O( N^r+1) time complexity.
3SUM hard problem. O(n^2) is the best known.
- Anonymous January 15, 2012First sort, then for each number x in the array, check if two numbers in the array exists whose sum is -x.
Sorting: O(nlogn).
For given x, checking if two numbers in array exist whose sum is -x : O(n), by the standard two pointers method.
So total O(n^2).