2
\$\begingroup\$

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;
        }
    }
}
\$\endgroup\$
2
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – vnp Dec 15 '14 at 20:48
  • \$\begingroup\$ yes that's what i thought i was doing. becuase i'm not using any sort, therefor i need to do it brute force. \$\endgroup\$ – Gilad Dec 15 '14 at 20:51
3
\$\begingroup\$

Your version

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.