What is the Time and Space Complexity of the 3Sum problem with the following algorithm?

Question

There was this problem that asked to return all unique triplets of elements of an array which add up to zero (swapping two elements' places in the triplet does not count as unique).

I came up with the following code:

function threeSum(nums) {
  nums.sort((a, b) => a - b);
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    // skipping duplicates
    if (i !== 0 && nums[i] === nums[i - 1]) continue;
    let left = i + 1;
    let right = nums.length - 1;
    while (left < right) {
      const s = nums[i] + nums[left] + nums[right];
      // too small; move to the right
      if (s < 0) left++;
      // too big; move to the left
      else if (s > 0) right--;
      // bingo
      else {
        result.push([nums[i], nums[left], nums[right]]);
        //skipping duplicates
        while (left + 1 < right && nums[left] === nums[left + 1]) left++;
        while (right - 1 > left && nums[right] === nums[right - 1]) right--;
        left++;
        right--;
      }
    }
  }
  return result;
};
// expected output: [[-4,-2,6],[-4,0,4],[-4,1,3],[-4,2,2],[-2,-2,4],[-2,0,2]]
console.log(threeSum([-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6]))

I think the time complexity is O(n^2). There is a sort at the beginning that we assume is O(n log n) and the nested loop works approximately (n^2)/2 times which translates to O(n^2). So, at the end, we are left with O(n log n + n^2) and since n log n is of lesser degree it is removed, leaving us with O(n^2).

I'm not quite sure about the space complexity, but intuitively I guess that's an O(n).

Can you please, correct/confirm my reasoning/guess about the time- and space complexity?

Answer 1

This looks like the standard approach to solving 3SUM in quadratic time. However, I disagree with the other answers concerning space complexity and believe it is quadratic as there can be quadratically many distinct triples summing to 0.

---

Consider the following example:

[1, -1, 2, -2, ..., n-1, 1-n, n, -n], where n is even.

In this particular case, there are n²/4 - n/2 distinct triplets summing to 0 (see derivation of this result below). That's quadratically many in the size of the array (the array being 2*n elements long). Because you store all these solutions, that means you need a quadratic amount of memory, and a linear O(n) won't cut it.

Thus, worst case space complexity is also quadratic (it is easy to show that there can not be more than quadratically many distinct triplets summing to 0).

---

Derivation of the result :

For any positive number a in this sequence, we can pick b = k and c = -(a+k) to get a triplet where a is the smallest element in absolute value, provided that k > a and a+k <= n i.e. a < k <= n-a. That gives us n-2*a choices for k (we never count any twice as b is always positive and c always negative).

Summing over all possible a's, we get a total of : sum((n-2*a) for a in 1...n/2) = n²/4 - n/2 = Ω(n²).