# 3Sum 2 Different implementations complexity

These are 2 implementations for the http://en.wikipedia.org/wiki/3SUM problem,
The first one is mine.
and in the second one I implemented Wiki's pseudo code.

Can someone please tell me if there is a difference between the two in complexity of runtime and memory space?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication2
{

//the 3SUM problem asks if a given set of n integers,
//each with absolute value bounded by some polynomial in n, contains three elements that sum to zero
public class ThreeSum
{
public ThreeSum()
{
List<int> array = new List<int> { 25, -10, -7, -3, 2, 4, 8, 10 };
List<int> res = SolveThreeSum(array);
res = SolveThreeSumWiki(array);
}

public List<int> SolveThreeSum(List<int> array)
{
for (int i = 0; i < array.Count - 2; i++ )
{
for (int j = i + 1; j < array.Count -1; j++)
{
for (int k = i + 2; k < array.Count ; k++)
{
if ((array[i] + array[j] + array[k]) == 0)
{
return new List<int> { array[i], array[j], array[k] };
}
}
}
}
return null;
}

public List<int> SolveThreeSumWiki(List<int> array)
{
array.Sort();
for (int i = 0; i < array.Count - 3; i++)
{
int a = array[0];
int start = i + 1;
int end = array.Count - 1;
while (start < end)
{
int b = array[start];
int c = array[end];
if ((a + b + c) == 0)
{
return new List<int> { a, b, c };
}
else if (a+b+c > 0)
{
end = end - 1;
}
else
{
start = start + 1;
}
}
}
return null;
}
}
}

• Your version's time complexity is $O(n^3)$; Wiki's is $O(n^2)$. The space complexity is constant for both (unless you consider a logarithmic stack usage for sort. – vnp Dec 15 '14 at 20:48
• yes that's what i thought i was doing. becuase i'm not using any sort, therefor i need to do it brute force. – Gilad Dec 15 '14 at 20:51

You have a bug in your three-loop implementation. This sort of bug creeps in when you use copy/paste to code without being diligent about checking what's useful. In your 'k' loop you have:

for (int k = i + 2; k < array.Count ; k++)


But that should loop from j + 1 and not i + 1. You should have:

for (int k = j + 1; k < array.Count ; k++)


This will significantly improve your performance for large lists.

The performance of this option will scale in terms of $O(n^3)$ which means each time you double the input data size, you will take 8 times longer to compute a result.

## Wiki Version

The second method uses the wiki algorithm, which is also the base of the algorithm I would recommend....

The Sort will take $O(n \log{n})$ time. For largeish lists the log(n) can be effectively ignored....

What's interesting here, is that you loop to the array size still in the i loop. You can actually limit the outer loop to valeus less than or equal to 0.

At least one of the values has to be 0 or less in order for there to be a zero-sum.

Similarly, once you have a second number, chosen from values after i, you should then be able to do a binary-search for the third number.