## Microsoft Interview Question

- 0of 0 votes
Can we do 3 sum problem on unsorted array in time (n logn) ?

3 sum problem : given unsorted array you have to find 3 numbers such that their sum is zero.

The algorithm to solve 3 sum problem is explained beautifully in youtube, watch it at

youtu.be/hLabfN0zjeU

```
package results;
import java.util.HashMap;
import java.util.Iterator;
import java.util.*;
public class Main {
public int B[];
public int N;
Hashtable tbl;
int count;
Main() {
B = new int[N+1];
tbl = new Hashtable();
count=0;
}
public void threeSum(){
int A[] = {0, -25, -10, -7, -3, 2, 4, 8, 10};
int N =8;
for ( int i = 1; i <=N; i++){
for (int j =i; j <=N; j++){
tbl.put(A[i]+A[j],1);
}
}
Enumeration e= tbl.keys();
while ( e.hasMoreElements()){
System.out.printf("%d ",(Integer)e.nextElement());
}
for ( int k = 1; k <= N; k++){
int temp = -A[k];
if ( tbl.get(temp)!=null){
System.out.println("3 sum 0 exists"+temp);
}
}
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Main o = new Main();
o.threeSum();
}
}
```

Can we take advantage of the fact that atleast one number must be negative.

say a + b + c = 0 and a = - (b+c);

say a is negative here. Then we search for combination of b and c such that summation is equal to negative of a. However our search is limited only for number of -ve number in the list. If list does not contain any negative number we probably can exit at start.

I am thinking we first sort the list

Then for each negative number do a search in nlog(n) time for the two number

O(n log n) + O(number of negative numbers * nlog(n))

= O(number of negative numbers * nlog(n))

For less number of negative numbers, this should work even better as O(nlogn), for large number of negative it should be O(n2)

Any comment

Hey, I have my code here, the solution is O(NlgN), any comments will be appreciated!

import java.util.ArrayList;

import java.util.Arrays;

public class Solution {

public static void main(String args[]){

int [] num = {-1, 0, 1, 2, -1, -4};

threeSum(num);

}

public static ArrayList<ArrayList<Integer>> threeSum(int[] num) {

// Start typing your Java solution below

// DO NOT write main() function

if(num.length<3 || num.length == 0 || num ==null)

return null;

Arrays.sort(num);

int i=0, j=num.length-1;

ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();

ArrayList<Integer> result;

while(i<j-1){

int v = 0 - num[i] - num[j];

if(binarySearch(num, i+1, j-1, v)){ //do binary search in between

result = new ArrayList<Integer>();

result.add(new Integer(num[i]));

result.add(new Integer(v));

result.add(new Integer(num[j]));

results.add(result);

if(num[i] == num[i+1]&&num[j-1]!=num[j]){ // handle the case when duplicates happens on the left

i++;

}

else if(num[i]!= num[i+1]&&num[j-1]==num[j]){// handle the case when duplicates happens on the right

j--;

}

else{ // if duplicates happens on both or neither happens

i++; j--;

}

}

else if(v > 0) // move to larger ones

i++;

else // move to slower ones

j--;

}

return results;

}

public static boolean binarySearch(int[] a, int lo, int hi, int key){

while (lo <= hi) {

// Key is in a[lo..hi] or not present.

int mid = lo + (hi - lo) / 2;

if (key < a[mid]) hi = mid - 1;

else if (key > a[mid]) lo = mid + 1;

else return true;

}

return false;

}

}

If only this algorithm were correct, it would be a pioneering research breakthrough, as solving this in subquadratic time is an important open research problem. Unfortunately, there's no reason to do i++ or j-- when you don't find the number in the binary search. You need a binary search for every *combination* of i and j, so making this correction, you'd end up taking O(n^2 logn) time.

```
public static void main(String arg[]){
int arr[]={-25, -1, -7, -3, 2, 4, 10, 10};
int length = arr.length;
for(int i=0; i<length; i++){
int a = arr[i];
int bInd = i + 1;
int cInd = length-1;
while( bInd<length ){
int b = arr[bInd];
int c = arr[cInd];
if( a+b+c ==0 ){
System.out.println( ""+a+"/"+b+"/"+c );
System.exit(0);
}
else if( a+b+c>0 ){
cInd--;
}
else{
bInd++;
}
}
}
System.out.println("not found");
}
```

At best we we do it in O(n^2).

- Arup Upapadhayay on June 27, 2012 Edit | Flag Reply