3Sum Algorithm

#javascript #beginners #algorithms #ruby

3Sum Problem - No Duplicates

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

No duplicates.

The trickiest part of this problem is duplicates (language depending). At first glance it makes sense to iterate in three loops for the brute force method.

for (i = 0; i < nums.length - 2; i++) {
   for (j = i + 1; j < nums.length - 1; j++) {
      for (k = j + 1; k < nums.length; k++) {
       ///additional code here
      }
   }
}

This results in O(n^3) time complexity and removing the duplicates is difficult because the goal is to return an array of arrays.

The way I recommend doing this problem is by using two pointers reducing the complexity to O(n^2).

In layman's terms we are going to have one number that we are going to go put through all the pertinent combinations by moving two pointers around to see if they match the target.

To do this the first thing we need to do is sort the array.

nums = nums.sort()

This should work right?

let nums = [0,5,2,-5,-2]
nums.sort()
Array(5) [ -2, -5, 0, 2, 5 ]

Nope the default sort in javascript does it alphabetically.

So instead we have to change the sort method. If you want to read up I recommend the documentation here

let nums = [0,5,2,-5,-2]
nums.sort(function(a,b) {return a-b})
Array(5) [ -5, -2, 0, 2, 5 ]

Success!

Now we can get down to finding our unique triplets

So after sorting we need to create a for loop. This loop is going to represent a number that we are comparing everything to.

i = number we aren't changing
j = low pointer start spot
k = high pointer start spot

[ i:-5, j:-2, 0, 2, k:5 ]

and the next iteration of the loop (i = 1)

[ -5, i:-2, j:0, 2, k:5 ]

and then

[ -5, -2, i:0, j:2, k:5 ]

so the low pointer j will always start at i + 1 and the high pointer k will always start at nums.length - 1.

So far we have

var threeSum = function(nums) {

    let result = []

    nums = nums.sort(function(a,b) {return a-b})

    for (let i = 0; i < nums.length - 2; i++) {

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


    }      

    return result
};

Since j should always be lower than k we can put most of the rest of the code into a while loop that specifies this.

and then just go through the rest of the logic.

If the sum of the three numbers is equal to the target (0 in the leetcode problem) then push it onto the array, otherwise increment or decrement the appropriate pointer to bring us closer to the target number.

var threeSum = function(nums) {

    let result = []

    nums = nums.sort(function(a,b) {return a-b})

    for (let i = 0; i < nums.length - 2; i++) {

        let j = i + 1
        let k = nums.length - 1
        while (j < k) { 
            let sum = nums[i] + nums[j] + nums[k]

            if(sum === 0) {
                result.push([nums[i], nums[j], nums[k]])
                j++
                k--
            } else if (sum < 0) {
                j++
            } else {
                k--
            }

        }


    }      

    return result
};

This mostly works except it allows for some duplicates and of course we are currently ignoring our base cases.

To ensure no duplicates once we find triplet we need to move the pointers to the next unique number else we could end up with the same triplet.

for example [0,0,0,1,1,1,2,2,2] will result in lots of duplicated triplets.

So we add the following after we add to the result array.

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

This concept also applies to 'i' so but we use continue to let it go to the next loop are properly handle the variables.

if (i > 0 && nums[i] === nums[i - 1]) continue

And the base cases. There are lots of ways to write these. I thought reduce would be fun to practice.

    if (nums.length < 3) {return [] }
    if (nums.length === 3) {
      let sum = nums.reduce(function(acc, cv) {
            return acc + cv
        }, 0)
      return sum === 0 ? [nums] : []
    }

Here is the full code in JS

var threeSum = function(nums) {

    let result = []

    if (nums.length < 3) {return [] }
    if (nums.length === 3) {
      let sum = nums.reduce(function(acc, cv) {
            return acc + cv
        }, 0)
      return sum === 0 ? [nums] : []
    }

    nums = nums.sort(function(a,b) {return a-b})

    for (let i = 0; i < nums.length - 2; i++) {

        let j = i + 1
        let k = nums.length - 1
        if (i > 0 && nums[i] === nums[i - 1]) continue

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

            if(sum === 0) {
                result.push([nums[i], nums[j], nums[k]])
                while (nums[k] === nums[k - 1]) k--
                while (nums[j] === nums[j + 1]) j++
                k--
                j++
            } else if (sum < 0) {
                j++
            } else {
                k--
            }


        }

    }      

    return result
};

and here it is in Ruby. In Ruby the duplicates are much easier to handle because .uniq will remove them so we don't have to have the while loops.

def three_sum(nums)
  result = []

  return result if (nums.length < 3)

  return [nums] if (nums.length === 3 && nums.sum === 0)
  nums.sort!
  for i in 0..nums.length - 3
    j = i + 1
    k = nums.length - 1

    while j < k
      sum = nums[i] + nums[j] + nums[k]
      if sum < 0
        j += 1
      elsif sum > 0
        k -=1
      else
        result.push([nums[i],nums[j],nums[k]])
        j += 1
        k -= 1
      end

    end
  end

  return result.uniq
end