Question

As mentioned in the class, the modern 3Sum conjecture states that there is no 3Sum algo- rithm that runs in time O(n) for fixed e0. Show this bound, if true, is almost tight. More precisely, provide an algorithm which answers the 3Sum problem in time O(n2). You can described your algorithm either in English words or using a pseudocode. If you use a pseudo-code, provide a short justification for the correctness of your algorithm.

Answer 1

// NOTE: I have useds comments in pseudocode for illustration you can remove it.

The Naive Approach:
We can generate all possible triplets and compare the sum if its equal to zero. THe Naive approach will require 3 loops having time complexity of
O(N^3)

Optimized solution
We can optimize the solution if we sort the given input, Sorting gives us advantage of ordering of elements.

Approach:

Sort the input.
Iterate over loop on input
Fix the first element as a = A[i]
Iterate over loop again to find b and c such that a + b + c = 0
as given in this pseudocode

sort(input); // O(NlogN)
for i=0 to n-2 do // O(N)
    // fix first element and initialize two varailbes to find b and c
    a = input[i];
    begin = i+1; // left index
    end = n-1;    // right index
    while (begin < end) do // O(N)
       b = input[begin]
       c = input[end];
       // if we found the sum print the values
       if (a + b + c == 0) then
          print (a,b,c)
          // increase left index
          begin = begin + 1;
          // decrease right index // do this to find remaining pairs
          end = end - 1;
       // Our goal here is to get sum as 0, so we can reduce the value of c by decreasing right index    
       else if (a + b + c > 0) then
          end = end - 1;
       // a + b + c < 0, we need to increase the total value, increase left index
       else
          begin = begin + 1;  
    end
end

total complexity O(NlogN) + O(N)* O(N) = O(N^2)

Algorithm correctness:
For given input we are sorting the input before processing.
Suppose we have a solution a + b + c = 0 and a < b < c
now a is fixed in first loop, and we are finding b and c.
We are using left index for b and right index for c

Case 1: if a + b + c > 0 then there will be no solution if we increase right index further as sum will always be greater than 0
Case 2: if a + b + c < 0 then there will be no solution if we dcrease left index further as sum will always be less than 0
Case 3: if a + b + c = 0, we found the solution. as total sum is equal to 0