javascript - What is the Time and Space Complexity of the 3Sum problem with the following algorithm? - Stack Overflow

admin管理员组

文章数量:1278947

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]))

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 plexity 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 plexity, but intuitively I guess that's an O(n).

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

• javascript
• algorithm
• time-plexity
• puter-science
• space-plexity

Share Improve this question Follow edited Aug 24, 2019 at 20:04 user1984 asked Aug 24, 2019 at 19:36 user1984user1984 6,82822 gold badges1616 silver badges3333 bronze badges 0

Add a ment  | 

4 Answers 4

Sorted by: Reset to default 6

This looks like the standard approach to solving 3SUM in quadratic time. However, I disagree with the other answers concerning space plexity 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 plexity 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²).

I agree on your thoughts about time plexity. You have a loop in the loop and you always move a pointer in the inner loop by at least 1 (left or right). So it is, like you said, O(n^2 / 2) or O(n^2)

EDIT: For space plexity I agree with Tassle's answer

For space plexity analysis following the derivation in Tassle's answer, we can consider triplets of the form (-x, 0, x) and input as [-3, -2, -1, 0, 1, 2, 3] in sorted form where (n = 7). Each of said triplets is unique, and can be identified by selecting its left most element. We observe there are up to n/2 of these distinct left-most elements (in the left half of the sorted input, growing linearly with input, i.e., O(n)). We can then further set the remaining two elements to sum to x, of which we again have up to n/2 distinct pairs (in the right half of the sorted input, growing linearly with input, i.e., O(n)) as "x" is just negating every "-x" (in the triplet). So O(n) selections of the left most triplet element are matched with O(n) selections of the remaining 2 triplet elements, leading to O(n^2) unique triplets in the worst case. For the visually inclined, we can expand the example twice (here, from x to x+2, to x+4) and chart the resulting growth of triplet count - specified explicitly below.

Unique Triplets Found in the original example input:

(-3, 0, 3)
(-3, 1, 2)
(-2, -1, 3)
(-2, 0, 2)
(-1, 0, 1)

Total Triplets = 5 for n = 7

We now increase n to 11:

[-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5]  (n = 11)

Unique Triplets Found

(-5, 0, 5)
(-5, 1, 4)
(-5, 2, 3)
(-4, -1, 5)
(-4, 0, 4)
(-4, 1, 3)
(-3, -2, 5)
(-3, -1, 4)
(-3, 0, 3)
(-3, 1, 2)
(-2, -1, 3)
(-2, 0, 2)
(-1, 0, 1)

Total Triplets = 13 for n = 11

Now, we increase n to 15:

[-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7]  (n = 15)

Unique Triplets Found

(-7, 0, 7)
(-7, 1, 6)
(-7, 2, 5)
(-7, 3, 4)
(-6, -1, 7)
(-6, 0, 6)
(-6, 1, 5)
(-6, 2, 4)
(-5, -2, 7)
(-5, -1, 6)
(-5, 0, 5)
(-5, 1, 4)
(-5, 2, 3)
(-4, -3, 7)
(-4, -2, 6)
(-4, -1, 5)
(-4, 0, 4)
(-4, 1, 3)
(-3, -2, 5)
(-3, -1, 4)
(-3, 0, 3)
(-3, 1, 2)
(-2, -1, 3)
(-2, 0, 2)
(-1, 0, 1)

Total Triplets = 25 for n = 15

Array Size (n) vs. Total Triplets Found
7   5
11  13
15  25

We can see that the number of triplets grows quadratically.

Yes, time plexity is O(n^2) where n = nums.length and your explanation for the same itself is sufficient.

Coming on the space plexity O(n) is also correct because of the merge sort algorithm used in the sort() method which has this space plexity. Space plexity refers to the extra elements/variables space that you are writing in your code apart from the given problem specific variables. For the code apart from the sort() method, there are two variables 'left' and 'right' along with an array result so this loop has space plexity of O(n+2), and then corresponding to them in internal while loop is also having a variable 's', then please observe that in every iteration there are 2 possibilities:-

1. it's the same container(i.e. memory location) whose contents(i.e. variable's value) gets changed and thus overall it's only 3 containers which have been used which concludes the Space plexity as O(constant) or simply O(1)
2. Every time different container is allocated to the variable for it's contents; however, this will be always acpanied by clearing the hold on previous container. Thus, overall we have only 3 extra containers at a time which will again lead to space plexity as O(1).

Now overall space plexity of the program would be O(n)+O(n+2)+O(1) which results in final solution of O(n).

Hope it helps!

本文标签：