Ggtcf

How can I make use of binary search for improving my algorithms time complexity?

I'm reviewing time complexity for some interviews & I'm having trouble making my algorithm more time efficient. This is my brute force solution for the 3-Sum problem: how many triples sum to exactly 0? Background: I don't have a CS degree.

//BRUTE FORCE SOLUTION: N^3
var threeSum = function(list)
 var count = 0;

 //checking each triple
 for(var i = 0; i < list.length; i++)
 for(var j = i+1; j < list.length; j++)
 for(var k = j+1; k < list.length; k++)

 if(list[i] + list[j] + list[k] === 0)count++;
 
 
 
 return count;
;

//binary search code
var binarySearch = function(target, array)
 var lo = 0;
 var hi = array.length - 1;
 //base case
 while(lo <= hi)
 var mid = Math.floor( lo + (hi - lo) / 2 );
 if(target === array[mid]) return mid;
 if(target < array[mid])
 hi = mid - 1;
 
 if(target > array[mid])
 lo = mid + 1;
 
 
 // value not found
 return -1;

I was reviewing an algorithms course online from Princeton & the professor noted that this algorithm could be made more efficient with use of a binary search algorithm.

According to the professor we would:

• sort the list


• for each pair of numbers array[ i ] & array[ j ] binary search for -(array[ i ] + array[ j ])

However, I'm having trouble understanding how binary search comes in to solve the problem. Here is a slide from the lecture, which I'm still trying to understand, but maybe useful to others:

I'm sure there a several efficient solutions out there: feel free to chime in with your implementation as it may help me and other future readers. Thanks

However, I'm having trouble understanding how binary search comes in to solve the problem.

This is how the n^2 log(n) algorithm works:

1. Sort the list in O(nlogn) time


2. Find all pairs of numbers (i,j), which is O(n^2) runtime.


3. Then, for each pair (i,j), it finds a number k where k = sum - j - i. This is constant time O(1)


4. The algorithm checks to see if each k exists, since the tuple (i,j,k) would sum to sum. To do this, do a binary search which takes log(n) time.

The final runtime would be O(nlogn) + O(logn * n^2) = O(n^2logn)

An alternative (and faster) solution would be to replace the sorting portion with a hashtable. Then, lookup of value k would take O(1) time instead of logn

The problem that the binary search approach is trying to solve is reducing the complexity of a cubic algorithm (this is your brute force algorithm) into a ~ N^2 log N algorithm.

As other commenters pointed out we know that when the following statement: list[i] + list[j] + list[k] == 0 is true than we found a 3SUM result. This is the same as saying that -(list[i] + list[j]) == list[k]. So the goal of the algorithm is to check for each i index and j index pair that there is a corresponding k index which satisfies the previous equation. Binary search can find those k indices in ~log N time. Hence the overall order of growth being ~N^2 log N (the outer for loops correspond to the N^2 part).

As for the implementation in javascript I would do it like this:

var threesum = function(list) 
 list.sort(function(a,b)return a - b);
 console.log(list);
 var cnt = 0;
 for(var i=0; i<list.length; i++) 
 for(var j=i+1; j<list.length; j++) 
 var k = bsearch(-(list[i]+list[j]), list);
 if (k!= null && k > j) 
 console.log("[i=%d], [j=%d], [k=%d]", i,j,k);
 cnt++;
 
 
 
 return cnt;
;

var bsearch = function(key, a) 
 var lo = 0;
 var hi = a.length-1;
 while (lo <= hi) 
 var mid = lo + Math.floor((hi - lo) / 2);
 if (a[mid] < key) 
 lo = mid + 1;
 else if (a[mid] > key) 
 hi = mid - 1;
 else 
 return mid;
 
 
 return null;
;

threesum([41, 48, 31, 32, 34, 38, 1, -9, 12, 13, 99, 5, -65, 8, 3, -3])

The algorithm basically works in the following way:

• Sort the array (worst-case O(n ^ 2), depending upon sorting algorithm)


• Generate all pairs of numbers - takes O(n ^ 2)
  


• for each pair (i , j), there might exist k, such that 0 = i + j + k.kis simply-(i + j), thus we can easily look it up by binary search inO(log n). Cases wherei < k < j` doesn't hold are avoided to exclude duplicates.

Thus total time-complexity is O(n ^ 2 log n).

const threeSum =(array,target)=>
 
 let result =[]
 
 array = array.sort((a,b)=> a-b)
 
 for(let i=0; i < array.length-2; i++)
 
 let left = i+1;
 let right = array.length -1;
 
 while(left < right)
 
 let sum = array[i]+ array[left]+ array[right];
 
 if(sum === target)
 result.push([array[i],array[left], array[right]]);
 
 left++;
 right--
 else if(sum < target)
 
 //sum is lower than target so increment left pointer 
 left++;
 else if(sum > target)
 //sum is greater than target so increment right pointer 
 right--;
 
 
 
 
 
 //return the list 
 return result;


let a = [12, 3, 1, 2, -6, 5, -8, 6];
console.log(threeSum(a, 0));

 Time Complexity: O(n^2) 
 Space Complexity: O(1)