clueless coding // TODO: be smarter

Sorted Three Sum: Explanation and C++ Solution

Problem Statement


Given an array input of N sorted, unique integers, are there elements a, b, c in input such that a + b + c == 0?

Find all unique triplets in the array which gives the sum of zero.

Function Signature:
  C++
    vector<vector<int>> threeSum(vector<int> input) {...}

Inputs:
  input = [-1, 0, 1, 2, -1, -4]

Outputs:
  [
    [-1, 0, 1],
    [-1, -1, 2]
  ]



Solution #1 (suboptimal): Linear Searching

O(N3) runtime, O(1) memory


A pretty natural idea is to put together every possible triplet, add up their members, and check if the sum is equal to 0. If we find that a triplet does in fact sum up to 0, we simply add it to our result set.

This approach is a simple translation of the requirements into code, in the most straightforward sense.

vector<vector<int>> threeSum(vector<int> input) {
    vector<vector<int>> result;
    for (int first = 0; first < input.size() - 2; first++) {
        for (int second = first + 1; second < input.size() - 1; second++) {
            for (int third = second + 1; third < input.size(); third++) {
                if (input[first] + input[second] + input[third] == 0) {
                    vector<int> triplet = { input[first], input[second], input[third] };
                    result.push_back(triplet);
                }
            }
        }
    }
    return result;
}

O(N3) runtime - we’re running 3 nested loops, with each running over the entire input.

We can also think of this as looking at each triplet in the set, which is an N3 problem.

O(1) memory - we aren’t storing anything of significance.




Solution #2 (optimal): Two pointers

O(N2) run time, O(1) memory


Unfortunately, in many cases, the most simple and straightforward isn’t necessarily the most optimal one. The issue with the above search, albeit a correct solution, is that it performs a dumb search. In creating triplets, it never really considers where in the input it currently is, or the information we’ve gathered in previous iterations.

Instead of checking every triplet, we can try to be a little smarter with how we construct the triplets. Again, we’ll use the very convenient fact that the input came to us sorted.

How can we intelligently create triplets, avoiding wasting our time on unnecessary combinations?

We’ll start by ‘pinning’ an element - the first one. Just as in the first solution, a triplet can start with any of the elements. For every pinned element, the only portion of the input we’re interested in is everything to the right of it.

vector<vector<int>> threeSum(vector<int> input) {
    vector<vector<int>> result;
    for (int pin = 0; pin < input.size() - 2; pin++) {
      // rest of our logic here
      // we'll only be looking at items to the right of pin
      // we'll be constructing triplets of the form { input[pin], x, y }
    }
    return result;
}

Next, we’ll employ the trusty two pointer approach. If you’ve never come across this approach, it’d be a good idea to click that link.

With the way we’ve defined our pin, the only elements we’re interested in are to the right. Keeping in line with the two pointer approach, we’ll set our left pointer to the leftmost of our ‘interesting’ data, i.e. at the position pin + 1. We’ll set the right pointer to the rightmost of our ‘interesting’ data, i.e. at the end of the array.

vector<vector<int>> threeSum(vector<int> input) {
    vector<vector<int>> result;
    for (int pin = 0; pin < input.size() - 2; pin++) {
      int left = pin + 1;
      int right = input.size();

      while (left < right) {
        // logic here!
      }
    }
    return result;
}

So - what do we do in our while loop?

Remember, we’re looking for sums that equal to 0. We can use our three elements and a simple equality to guide our search. Say we add our pinned, left, and right elements together:

If the sum is greater than 0, we know that we should move the right pointer down one - that’s the only way we can lower the sum and get closer to zero. Conversely, if our sum is less than 0, we should move our left pointer up one - that’s the only way we can increase our sum and get closer to 0.

This is a classic two pointer approach.

Essentially what we’ve done is boiled this problem down to a (two sum problem)[], with the added idea that our two-sum must be added to our pinned element.

vector<vector<int>> threeSum(vector<int> input) {
    vector<vector<int>> result;
    for (int pin = 0; pin < input.size() - 2; pin++) {
        int left = pin + 1;
        int right = input.size();

        while (left < right) {
            int sum = input[pin] + input[left] + input[right];
            if (sum > 0) {
               right--;
            }
            else if (sum < 0) {
                left++;
            }
            else {
                vector<int> triplet = { input[first], input[second], input[third] };
                result.push_back(triplet);
                left++;
                right--;
            }
        }
    }
    return result;
}

O(N2) runtime - we have an outer loop that runs through all N elements. For each of these iterations, we’re running through the rest of the array only once, thanks to our two pointer approach.

O(1) memory - we aren’t storing anything of significance.