15. 3Sum

https://leetcode.com/problems/3sum/description/

Optimal Space & Time Complexity

- Time complexity: O(n^2)
- Space complexity: O(1)

---

Solutions

東

Hao

function threeSum(nums) {
  const results = [];

  if (nums.length < 3) return results;

  // having the numbers in ascending order will make this problem much easier.
  // also, knowing the overall problem  will take at least O(N^2) time, we can
  // afford the O(NlogN) sort operation
  nums = nums.sort((a, b) => a - b);

  let target = 0;

  for (let i = 0; i < nums.length - 2; i++) {
    if (nums[i] > target) break;
    if (i > 0 && nums[i] === nums[i - 1]) continue;

    let j = i + 1;
    let k = nums.length - 1;

    while (j < k) {
      let sum = nums[i] + nums[j] + nums[k];

      if (sum === target) {
        results.push([nums[i], nums[j], nums[k]]);

        while (nums[j] === nums[j + 1]) j++;
        while (nums[k] === nums[k - 1]) k--;

        j++;
        k--;
      }
      else if (sum < target) j++;
      else k--;
    }
  }

  return results;
}

YC

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    if(nums.length < 3) return []; //early return
    nums.sort((a,b) => a-b);
    const ans = []
    for(let i = 0; i < nums.length; i++){
        let left = i + 1;
        let right = nums.length - 1;
        if(nums[i] > 0) return ans; //early return because the array is sorted
        if(nums[i] === nums[i-1]) continue;
        while(left < right){
            const sum = nums[i] + nums[left] + nums[right];
            if(sum < 0) left++;
            else if(sum > 0) right--;
            else{
                ans.push([nums[i], nums[left], nums[right]]);
                left++;
                right--;
                while(nums[left] === nums[left-1]) left++;
                while(nums[right] === nums[right+1]) right--;
            }
        }
    }
    return ans;
};

SOL

---

Supplement / Discussion

東

Hao

JavaScript with lots of explanatory comments!

"Three" pointers: employ indexs i, j, k to indicate the number. Iterate i with the following steps:

1. Fix i first, and so we have only two pointers j, k left.
2. Sum up i, j, k to see if reach targetSum while move j and k closer to each other
3. Add early break/continue during iterations
   • When nums[i] > targetSum
   • When nums[i] === nums[i - 1]
   • When nums[j] === nums[j - 1]
   • When nums[k] === nums[k - 1]

YC

1. sort the array
2. set three variables: i, left, right
   • i is a for-loop variable
   • left and right serve as left-right pointer
3. remove duplicate triplets
   • nums[i] === nums[i-1]
   • nums[left] === nums[left-1]
   • nums[right] === nums[right+1]
4. (nice to have) early return
   • nums.length < 3
   • nums[i] > 0: because the array is sorted

SOL

3 loops 👎🏻👎🏻👎🏻

[-1,0,1,2,-1,-4]

1. Sort the input array in ascending order

[-4,-1,-1,0,1,2,]

2. Loop through each value in the array.
3. Calculate the target value needed for two additional elements to sum up to zero.
4. Iterate through each value in sub-array1 (remaining elements after current value).

-4, [-1,-1,0,1,2,] find a + b = 4

5. Calculate the value needed for the third element to complete the triplet sum.
6. Iterate through each value in sub-array2 (remaining elements after current value).
7. Search for the value in the sub-array2 that matches the calculated target value.
8. Add the triplet [a, b, c] to the result array if found.

-1, [,-1,0,1,2,] find 1
…

var threeSum = function(nums) {
    const result = []
    nums.sort((a,b)=>a-b)
    let preNum1;
    nums.forEach((a, index)=>{
        if( preNum1 !== a ){
            const target = 0 - a;
            const rest = nums.slice(index+1)
            let preNum2;
            rest.forEach((b, index)=>{
                if(preNum2 !== b){
                    const target2 = target - b;
                    const rest2 = rest.slice(index+1)
                    const find = rest2.find((c)=> c === target2)
                    if(find || find === 0){
                        result.push([a, b,find])
                    };
                }
                preNum2 = b
            })
        }
        preNum1 = a 
    });
    return result;
};

two poniters 👍👍👍

1. Sort the input array in ascending order.
2. Loop through the array, excluding the last two elements.
3. Skip duplicates.
4. Use a two-pointers approach (left-right pointers) that move toward each other.
5. Calculate the sum
   • If the sum === target:
     a. Add the triplet to the result array.
     b. Eliminate duplicate pointers by moving them.
     c. Move both pointers.
   • If sum < target, move leftPointer.
   • If sum > target, move rightPointer.

var threeSum = function(nums) {
    const result = []
    const target = 0;
    nums.sort((a,b)=>a-b)
    for (let i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        let leftPointer = i+1;
        let rightPointer = nums.length -1;
        while( leftPointer < rightPointer ){
            const sum = nums[i] + nums[leftPointer] + nums[rightPointer]
            if(sum === target){
                result.push([nums[i], nums[leftPointer], nums[rightPointer] ])
                while(nums[leftPointer + 1] === nums[leftPointer]) leftPointer++;
                while(nums[rightPointer - 1] === nums[rightPointer]) rightPointer--;
                leftPointer++;
                rightPointer--;
            } else if(sum<target){
                leftPointer++;
            } else {
                rightPointer--;
            }
        }
    }
    return result;
};

---

Supplement (psuedo code from YC)

/*
 * 3 variables: i, j, k for-loop 3 times: O(n^3)
 * j, k -> left, right: O(n^2)
 * remove duplicate triplet: i, left, right
 * */

var threeSum = function(nums) {
    // sort
    const ans = []
    for(let i = 0, ...){
        if(nums[i]>0) return ans;
        let left = i+1;
        let right = nums.length - 1;
        while(left < right){
            const sum = ...
            if(sum < 0) left++
            else if (sum > 0) right--;
            else{
                ans.push([i,left,right])
                left++;
                right--;
                while(left === left-1) left++;
                while(right === right+1) right--;
            }
        }
    }
    return ans;
    
}