7
\$\begingroup\$

I am working on a problem "3Sum", in which, given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0. I must find all unique triplets in the array which gives the sum of zero.

I wrote my naive implementation which was \$O(n^3)\$ since it was checking for every possible combination:

public List<List<Integer>> threeSum(int[] num) {
    List<List<Integer>> res=new ArrayList<List<Integer>>();

        if(num.length<3) return res;

       Arrays.sort(num);

        for(int i=0;i<num.length;i++)
        {
         if(num[i]>0) break;
            for(int j=i+1;j<num.length;j++)
            {
                if(num[i]+num[j]>0 && num[j]>0) break;
                for(int k=j+1;k<num.length;k++)
                {
                    if(num[i]+num[j]+num[k]==0)
                      {
                          List<Integer> curr=new ArrayList<Integer>();
                          curr.add(num[i]);
                          curr.add(num[j]);
                          curr.add(num[k]);
                          res.add(curr);
                      }
                      while(k+1<num.length && num[k]==num[k+1]) k++;
                }
                 while(j+1<num.length && num[j]==num[j+1]) j++;
            }
            while(i+1<num.length && num[i]==num[i+1]) i++;
        }
        return res;

}

However, I am looking for a solution which is better than \$O(n^2)\$. Rather, is there a way I can bring the time complexity of my solution to \$O(n^2)\$ by removing any of the loops?

\$\endgroup\$
  • \$\begingroup\$ looks like you just changed the variable names and the incrementation variables inside the while loop declarations. \$\endgroup\$ – Malachi Oct 29 '14 at 18:45
  • \$\begingroup\$ @Malachi: No, thats my own solution which runs in O(n^3), this is a naive implementation of this problem. The solution I Posted before ran in O(n^2). \$\endgroup\$ – chmod766 Oct 29 '14 at 18:56
  • \$\begingroup\$ do you have any test Arrays that you can post along with their expected results? \$\endgroup\$ – Malachi Oct 29 '14 at 20:04
  • \$\begingroup\$ @Malachi: I submit my solutions to a website(Leetcode.com) then they run run various test cases to see if your program handle all the cases. My solution was accepted but I am looking for a better solution. \$\endgroup\$ – chmod766 Oct 30 '14 at 0:48
4
\$\begingroup\$

I don't have a solution better than yours (you can google for java 3Sum O(n^2) to find some examples), but I have some small comments on your code:

While loops

I would remove all the while loops. They make your code harder to read and don't really speed it up (in my tests, they actually slowed it down).

Minor performance improvements

  • array access costs time, if you save num[i], etc in local variables, it will slightly speed your code up.
  • move quicker checks to the beginning: nj > 0 && ni + nj > 0 instead of ni + nj > 0 && nj > 0 should be quicker, but only marginally so.

Style

  • use correct indentation
  • in Java, the opening curly bracket commonly goes on the same line
  • use curly brackets, even for one-line statements
  • use more spaces (for example while(k+1<num.length && num[k]==num[k+1]) would be while (k + 1 < num.length && num[k] == num[k + 1])
\$\endgroup\$
  • \$\begingroup\$ Tim: Thanks a lot for your comments, especially on my style. I will try to write more readable code from next time onwards.However, I used the while loop to avoid duplicate set in an array.If I remove while loop, then my result arraylist will contain duplicate list of elements which adds up to 0. \$\endgroup\$ – chmod766 Oct 30 '14 at 0:53
4
\$\begingroup\$

A more efficient solution to this challenge lies in the way you structure the data.

Sorting the data before you start allows you to do a number of interesting things. Ordering the data is typically a \$O(n \log n)\$ operation. Now, with the data sorted, you can make some significant simplifications...

We will be looking for values where a + b + c is zero. From this we know that at least one of the values will be negative (or they will all be zero).

Now, if we start on the small end, loop over all the negative numbers only... and call this the a value, then we know that b + c = -a.

So we set up a nested loop that loops over the 'b' varables. For each value after a, we have b, and we know that c = -b -a So, we know what c will be, and, since the data is ordered, we also know that we can binary-search in to the data that comes after b (if the data contains duplicate values, we need to handle that specially....).

Arrays.sort(data);
for (int i = 0; i < data.length && data[i] <= 0; i++) {
    int a = data[i];
    for (int j = i + 1; j < data.length; j++) {
        int b = data[j];
        int c = -a - b;
        int k = Arrays.binarySearch(data, j + 1, data.length, c);
        // go backwards, there may be duplicates....
        if (k < 0 && (-k -1) <= j) {
            // c has to be smaller than any value we have,
            // which means there are no more possible solutions for any
            // values of b larger than what we have. We can end this b loop:
            break;
        }
        while (k > j + 1 && data[k - 1] == c) {
            k--;
        }
        while (k < data.length && data[k] == c) {
            // add a solution for a, b, and c, at positions i, j, and k.
            ....
        }
    }
}

What is the complexity of this solution?

The initial 'a' loop covers only negative values, and the 'b' loop covers about half the remainder. This is a worst-case \$O(n^2)\$ process. The 'c' check is a \$O(log n)\$ one.

Combining all these together, it is a \$O(n^2 \log n)\$ problem... ish. It will, in practice, be faster than the worst case.

\$\endgroup\$
4
\$\begingroup\$

Instead of While loops for more than one incrementation

while(k+1<num.length && num[k]==num[k+1]) k++;

And

 while(j+1<num.length && num[j]==num[j+1]) j++;

And

while(i+1<num.length && num[i]==num[i+1]) i++;

you should use an if statement inside the for loop right before the end bracket like this

if (i + 1 < num.length && num[i] == num[i + 1])  {
    i++;
}

Actually that is wrong, you should actually do it inside the for loop before the first block of code

I am thinking that it might save you an iteration or two by forcing it to iterate without doing the stuff inside the for loop so instead of what I have up there, it would look like this instead

if (k+1<num.length && num[k]==num[k+1]) {
    break;
}

for a final product of

public List<List<Integer>> threeSum(int[] num) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();

    if(num.length < 3) return res;

    Arrays.sort(num);

    for(int i = 0; i < num.length; i++)
    {
        if (i + 1 < num.length && num[i] == num[ i + 1]) {
            continue;
        }
        if(num[i] > 0) {
            break;
        }
        for(int j = i + 1; j < num.length; j++)
        {
            if (j + 1 < num.length && num[j] == num[j + 1]) {
                continue;
            }
            if(num[i] + num[j] > 0 && num[j] > 0) {
                break;
            }
            for(int k = j + 1; k< num.length; k++)
            {
                if (k + 1 < num.length && num[k] == num[ k + 1]) {
                    continue;
                }
                if(num[i] + num[j] + num[k] == 0)
                {
                    List<Integer> curr=new ArrayList<Integer>();
                    curr.add(num[i]);
                    curr.add(num[j]);
                    curr.add(num[k]);
                    res.add(curr);
                }
            }
        }
    }
    return res;
}

Notice that use proper Indentation and Egyptian Bracing style, and I give space to operators along with the mandatory space after a semi-colon

\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks for pointing out that extra "while" loops can be avoided by checking at the beginning of "for" loop. \$\endgroup\$ – chmod766 Oct 30 '14 at 1:06
  • \$\begingroup\$ As is, this code will not work. Replace all the break;s with continue;s and it will almost work. Example that fails for the current code: [-3,-3,2,1]. Example that fails for the modified code: [-2,-2,1,1]. This is because you are checking for duplicates first, instead of checking the first of the duplicates. And if you find any duplicates, you break the loop altogether, so the first example will enter the for loop and immediately break out entirely without checking anything. \$\endgroup\$ – Poik Nov 5 '14 at 19:52
  • \$\begingroup\$ @Poik so if I use continue in the new if statements then it will work because it will continue through the loop, Right? \$\endgroup\$ – Malachi Nov 5 '14 at 19:59
  • \$\begingroup\$ I think so. I've been debugging by eye, not with Java installed, so don't take my word for it. \$\endgroup\$ – Poik Nov 5 '14 at 20:15
  • \$\begingroup\$ @Poik, that sounds right though, to use continue instead of Break, what I wanted was for the code to be bypassed and the incrementation variable incremented and then run again, so this makes way more sense than a break in there. \$\endgroup\$ – Malachi Nov 5 '14 at 20:23
4
\$\begingroup\$

Here's what you do:

  1. Sort the numbers and keep at most 3 zeros and two of any other value. Let the numbers be called \$a_i\$ so that \$a_i \le a_{i+1}\$.
  2. Construct a HashMap of all \$a_i\$ with their multiplicity.
  3. Set \$k=0\$
  4. If \$a_k > 0\$ you're done.
  5. For each \$i\gt k\$ construct the pair: \$(a_k, a_i)\$.
    1. See if the HashMap contains \$c=-a_k -a_i\$.
    2. If it does, add \$-a_k -a_i\$, \$a_k\$ and \$a_i\$ as a tuple to the list of found tuples.
    3. If there are \$i\$ left to try, go to step 5.1, otherwise set \$k=k+1\$ and go to step 4.

Also add some checking to see if you have enough "free" numbers of the type in the hashmap.

The time complexity is amortized \$\mathcal{O}(n^2)\$ as lookup in HashMap is amortized \$\mathcal{O}(1)\$.

\$\endgroup\$
2
\$\begingroup\$

The simplest \$O(n^2)\$ code I can think of off the top of my head stems from your code. I tried to modify it as little as possible for your reference.

public List<List<Integer>> threeSum(int[] num) {
    List<List<Integer>> res=new ArrayList<List<Integer>>();

    if(num.length<3) return res;

    Arrays.sort(num);

    //First loop, linear number of loops, O(n).
    for(int i=0;i<num.length-2;i++)
    {
        if(num[i]>0) break;
        int j = i + 1; //Added this
        int k = num.length; //Added this
        //for(int j=i+1;j<num.length;j++) //Your code for reference

        //Second loop increments j or decrements k until they meet for a
        //total of i possible loops, or linear loops, O(n).
        while (j<k) //Added this
        {
            //if(num[i]+num[j]>0 && num[j]>0) break; //Your code for reference
            //for(int k=j+1;k<num.length;k++) //Your code for reference
            //{ //Your code for reference
                if(num[i]+num[j]+num[k]==0)
                {
                    List<Integer> curr=new ArrayList<Integer>();
                    curr.add(num[i]);
                    curr.add(num[j]);
                    curr.add(num[k]);
                    res.add(curr);
                }
                if(num[i]+num[j]+num[k]>0) { //Added this
                    k--; //Added this
                } else { //Added this
                    j++; //Added this
                } //Added this
                //Third loop
                while(k>j && num[k]==num[k-1]) k--; //Changed this
            //} //Your code for reference
            //Fourth loop
            while(j<k && num[j]==num[j+1]) j++; //Changed this
        }
        //Fifth loop
        while(i+1<num.length && num[i]==num[i+1]) i++;
    }
    return res;

}

This is by not necessarily optimal, but it is easy. As for why this works, that takes a bit of math. It's late so I'll come back and edit later, but the argument boils down to being able to know all lower j values will not work with any lower k values or that iteration's k value, when the sum is negative as that would make the sum even lower, and a similar argument for the higher k values in conjunction with higher j values and that iteration's j value.

This algorithm runs \$O(n)\$ loops of \$O(n)\$ complexity computations after a \$O(n \log n)\$ sort, making it \$O(n^2)+O(n \log n)\$ or \$O(n^2)\$. Why is the second loop linear in complexity when it has the third and fourth loops inside it? The second loop iterates \$l-m-p\$ times, where \$m\$ and \$p\$ are the number of times the third and fourth loop executes during all iterations of the second loop respectively and \$l\$ is the number of entries higher than the \$i\$th index. Thus, for each iteration of the first loop, there is a complexity of \$O(l-m-p+m+p)=O(l)\$ where \$l\$ is linearly related to the number of entries, or \$n\$, making this \$O(n)\$. Otherwise, for each second loop iteration, the number of computations will be less than some constant multiplied by the number of entries passed in. The fifth loop is linear at worst, so it would add to the linear complexity of the second loop, resulting in a linear complexity.

To better show the complexity, this all can be reordered so that the exact same computation to take place by unrolling the third, fourth, and fifth loops into the loops that contain them respectively. They still are called as many times as the loops above would have, but instead of incrementing the indexes as a part of their own loop, they increment the index and skip the rest of the iteration of the containing loop. The branching in the code here is a little more digestible and orderly in software, but ultimately the same computation wise.

public List<List<Integer>> threeSum(int[] num) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();

    if(num.length <3) return res;

    Arrays.sort(num);

    //First loop, linear number of loops, O(n).
    for (int i = 0; i < num.length - 2; i++)
    {
        //Fifth loop, unrolled.
        if (i > 0 && num[i] == num[i-1])
        {
            i++;
            continue;
        }
        if (num[i] > 0) break;
        int j = i + 1;
        int k = num.length;

        //Second loop increments j or decrements k until they meet for a
        //total of i possible loops, or linear loops, O(n).
        while (j < k)
        {
            //Third loop, unrolled
            if (k < num.length && num[k] == num[k+1])
            {
                k--;
                continue;
            }
            //Fourth loop, unrolled
            if (j > i+1 && num[j] == num[j-1])
            {
                j++;
                continue;
            }
            if(num[i] + num[j] + num[k] == 0)
            {
                List<Integer> curr = new ArrayList<Integer>();
                curr.add(num[i]);
                curr.add(num[j]);
                curr.add(num[k]);
                res.add(curr);
            }
            if(num[i] + num[j] + num[k] > 0) {
                k--;
            } else {
                j++;
            }
        }
    }
    return res;

}

The important thing to take here is complexity stems from what happens, not from certain code construct. A for loop doesn't necessarily introduce more complexity, as it may not even run, or it may only run a few times out of all the times it is reached in the code. Unfortunately, this means that complexity is a little more complex than just looking for key words and curly brackets.

This solution requires as little memory as your solution (no hashmap), but . For the rest of the code review, what other people are recommending style-wise I agree with, but remember readability over style for style's sake. The wonky spacing makes it very hard to read, so that was the first thing I changed. It's your code, though, so if there's something stylistically you prefer, and you are consistent (this is important), some deviation is allowed. (Unless your boss or team tells you otherwise.) For instance, if there's a less than sign followed by a three, it's totally okay to omit the space between them.

\$\endgroup\$
  • \$\begingroup\$ Poik: Thanks for writing an \$O(n^2)\$ but I am little skeptical about the running time complexity of the algorithm since inner "while" loop (which checks for duplicates) could make it \$O(n^3)\$. However, this is my understanding of the algorithm. Do let me know if I am missing out on any detail while computing the running time. \$\endgroup\$ – chmod766 Oct 30 '14 at 19:34
  • \$\begingroup\$ The inner while loop removes iterations of the outer while loop. Any complexity added by the inner while loop is removed from the outer while loop. In all, i iterations of the outer while loop plus the inner while loop will happen on each iteration of the for loop. \$\endgroup\$ – Poik Oct 30 '14 at 19:58
  • \$\begingroup\$ If you're still skeptical, remove both while loops and add the conditions (with minor adjustments to account for the fact that it's a pre-loop check instead of a post-loop check, of course) as if statements at the beginning of each loop, that if true execute the increment or decrement and then call continue. This will operate exactly the same as the above code, but has the inner while loops unrolled into the outer while loop. \$\endgroup\$ – Poik Oct 30 '14 at 20:01
  • \$\begingroup\$ Poik: Its a good idea to check in the beginning of loop for duplicates. But, can you clarify that algorithm will take O(n^3) if we don't remove inner while loop? I am trying to understand the time complexity with and without inner while" loop. Thanks for your previous comment and answer. \$\endgroup\$ – chmod766 Oct 30 '14 at 20:08
  • \$\begingroup\$ Do you mean your original inner while loop? Because the while loop here is fine for \$O(n^2)\$. I can update my answer to give more detail about the considerations I made in editing your code. However, that will have to wait until I get out of work. \$\endgroup\$ – Poik Oct 30 '14 at 20:11

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.