3Sum

3Sum

#Leetcode #blind75 #array

Hint

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

In a simple word given an array, we need to find three numbers in the array that adds up to 0.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Before we dwelve to solve the problem. Let's first take time why is it important?

The why?

Why even bother to solve this problem?

1. Amazon:
2. Product recommendation algorithm might use a variation of three sum to suggest bundles of three complementary items.
3. Warehouse Logistics, it might be used to optimize the placement of three frequently co-ordered items.
4. Apple:
5. Apple musics could use this algorithm to create a playlist with 3 genre of music
6. Spotify:
7. Playlist generation algorithms might use similar concepts to balance song selection across tempo, genre, and popularity.
8. Game theory and strategy:
9. In multiplayer games, finding balanced team compositions or strategies involving three players

5. Uber:

1. Could use a variation for optimizing pickups/drop-offs for UberPool with three passengers.

This is why it's important to understand this algorithm.

first before we solve a three sum problem , let's revise how we can solve two sum problem.

function twoSum(nums, target){

  let map = {}

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

    if(map[nums[i]]){

      return [i, map[nums[i]]]

    }

    let desiredNum = target - nums[i]

    map[desiredNum] = i

  }

}

now's let see if we can break down any pattern to solve the 3 sum problem.

1. We need to compare three values
2. so we need 3 pointer
3. We need to store our results
4. We need to do some comparison
5. if a sum is greater than or lesser than or equal to 0

 function threeSumBruteForce(nums) {

  let results = [];

  let n = nums.length;

  for (let i = 0; i < n - 2; i++) {

    for (let j = i + 1; j < n - 1; j++) {

      for (let k = j + 1; k < n; k++) {

        if (nums[i] + nums[j] + nums[k] === 0) {

          results.push([nums[i], nums[j], nums[k]]);

        }

      }

    }

  }

  // Remove duplicates

  return results.filter((triplet, index) => 

    index === results.findIndex(t => 

      t[0] === triplet[0] && t[1] === triplet[1] && t[2] === triplet[2]

    )

  );

}

Next:

1. Here in order to search properly and optimize the O(N^3)
2. can we sort the array first before we do our calculation? YES
3. sorting allows us to use the two-pointer technique, which is more efficient than nested loops.
4. After sorting, we can fix one number and use two moving pointers to find the other two numbers that sum to the target.
5. Skips duplicates to avoid redundant triplets.

so now we can refactor our algorithm to

function threeSumSolved(nums){

  let results = []

  nums = nums.sort((a,b) => a-b)

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

    let l = i + 1

    let r = nums.length - 1

    while(l < r){

      let sum = nums[i] + nums[l] + nums[r]

      if(sum < 0) l++

      else if (0 < sum) r--

      else {

        results.push([nums[i], nums[l], nums[r]])

        // skips duplicate values for the 1st number in the triplet

        while(nums[i] === nums[i + 1])i++

        // skips duplicate values for the 2nd number in the triplet

        while(nums[l] === nums[l + 1])l++

        //Similarly, this skips duplicate values for the 3rd number in the triplet.

        while(nums[r] === nums[r + 1])r--

        //after we've found a valid triplet and skipped any duplicates, 

        //we need to move both pointers inward to look for the next potential triplet.

        l++

        r--

      }

    }

  }

  return results

}

This is how the problem can be solved.