Road to Genius: superior #64

Each day I solve several coding challenges and puzzles from Codr's ranked mode. The goal is to reach genius rank, along the way I explain how I solve them. You do not need any programming background to get started, and you will learn a ton of new and interesting things as you go.

function threeSum(nums) {
  if (nums.length < 3) return [];
  const list = [];
  nums.sort((a, b) => a - b);
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] > 0) break;
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    let left = i;
    let right = nums.length - 1;
    while (left < right) {
      if (left === i) {
        left++;
      } else if (right === i) {
        right--;
      } else if (nums[left] + nums[right] + nums[i] === 0) {
        list.push([nums[left], nums[right], nums[i]]);
        while(nums[left] === nums[left + 1]) {
          left++;
        }
        left++;
        while(nums[right] === nums[right - 1]) {
          right--;
        }
        right--;
        continue;
      } else if (nums[left] + nums[right] + nums[i] > 0) {
        right--;
      } else {
        left++;
      }
    }
  }
  return list;
};

let A = threeSum([-0,1,-1,1,-0,0]);
A = A.length;

// A = ? (number)

In today's challenge we are dealing with a function threeSum, I have no clue what it does but is has something to do with three and sums.

The challenge wants us to solve for A which is the length of the output of threeSum. This function returns list which is an array.

We have no clue what this function does, but we know its output. Let's figure out how this list array is being filled. The only place where we find an operation adding items to this array is here:

} else if (nums[left] + nums[right] + nums[i] === 0) {
   list.push([nums[left], nums[right], nums[i]]);
   ...
}

As we can see, it pushes an item (array) into list when the sum of three numbers from nums (the input) is equal to zero. In a nutshell this algorithm is designed to find triplets whose sum is zero.

When we analyze the code fully, we see that the input array nums is sorted in ascending order; the outer most for-loop iterates over each number in nums indexed by i; followed by left and right pointers which are to the right of i. In this fashion the algorithm is searching for only unique triplets whose sum is zero. Here's some pseudo-code to illustrate the process:

nums = [-0, 1, -1, 1, -0, 0]
-> sort
nums = [-1, -0, -0, 0, 1, 1]

----------
    i = 0
 left = 0
right = 5
...
(-0) + 1 + (-1) = 0  --> push
    i = 0
 left = 1
right = 5
----------
    i = 1
 left = 1
right = 5
...
(-0) + 0 + (-0) = 0  --> push
    i = 1
 left = 2
right = 3
----------

for all other attempts:
i + left + right !== 0

list.length == 2

By solving these challenges you train yourself to be a better programmer. You'll learn newer and better ways of analyzing, debugging and improving code. As a result you'll be more productive and valuable in business. Get started and become a certified Codr today at https://nevolin.be/codr/