All The Ways That I Failed At "Sum 3"

I have a problem in my life and it's name is Leetcode.

While trying to think of topics to write about on DEV, I kept reading all these posts from talented developers who write so authoritatively about coding and I couldn't help be think, "I definitely cannot do that."

It seems like most coders' solutions and strategies to coding problems come so clearly. In the meantime, I approach solving problems like a monkey slapping at buttons until a banana pops up in my console so I can scream in delight.

But most importantly is to just enjoy the process. Coding is so much fun, so I thought I'd share my coding failures (and sometimes successes).

Sum 3

Sum 3 is a mean-spirited twist on another Leetcode problem called Sum 2. Where in Sum 2 you loop through an array adding two elements until they equal to a target number, Sum 3 uses three.

Oh, and with the caveat that of only using each element once per 3 array pairing.

var sum3 = (array, target) => {
  // magic
}

var nums = [-1, 0, 1, 2, -1, -4]

sum3(nums, 0) // [ [-1, 0, 1], [-1, -1, 2] ]

Attempt 1: Hitting It With A Hammer

My first, and totally useless attempt at a problem like this, is to shove it into a meat grinder, turn the crank, and hope sausage comes out at the end.

In this case, its about running as many for loops as humanly possible praying that there's some kind of solution in it, and then maniacally laughing as my browser catches fire and melts my hard drive into a puddle of plasticy goo.

Attempt 1:

var nums = [-1, 0, 1, 2, -1, -4]

var threeSum = (nums, target = 0) => {
    var solution = []

    for(let a = 0; a < nums.length; a++) {
        for(let b = 0; b < nums.length; b++) {
            for(let c = 0; c < nums.length; c++) {
                let sum = nums[a] + nums[b] + nums[c]
                if (sum === target) solution.push([nums[a], nums[b], nums[c]])
            }
        }
    }
    return solution
}

Alright, straight to the point. No muss. No fuss.

Let's check the output.

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

Oh boy. Yeah, this isn't good.

What went wrong? Right off the back, I can see two major problems:

1. We use the same element in the array over and over again.
2. There's duplicates all over the place.

Alright, we're going to implement something like this to address issue 1:

if (a !== b && b !== c && a !== c) {
  let sum = nums[a] + nums[b] + nums[c]
  if (sum === target) solution.push([nums[a], nums[b], nums[c]])   
}

I'm going to wrap the core of the algorithm in a conditional where if any of the variables are in the same position in the array, then the sum array won't push into the solution array.

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

The duplication issue is a bit trickier.

To stick with the theme of this attempt, let's lob a grenade and see how the pieces fall in the exact right place we need them to.

First, let's sort the sum array, so that we can make sure it's in the same order no matter where it's found in the the nums array.

if (a !== b && b !== c && a !== c) {
  let sum = nums[a] + nums[b] + nums[c]
  let sumArray = [nums[a], nums[b], nums[c]].sort((a, b) => a - b)
  if (sum === target) solution.push(sumArray)   
}

Ok great. And what does that give us?

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

Unfortunately JavaScript doesn't allow arrays to be directly compared, so something like this [] === [] won't work.

That means writing a helper function to check if the new array is in the solution array.

var isInSolution = (newArray, solutionArray) => {
    let dup = false
    let [a, b, c] = newArray

    solutionArray.forEach(array => {
        let [d, e, f] = array
        if (a === d && b === e && c === f) dup = true
    })

    return dup
}

And then we have to adjust the core to something like this:

if (a !== b && b !== c && a !== c) {
  let sum = nums[a] + nums[b] + nums[c]
  let sumArray = [nums[a], nums[b], nums[c]].sort((a, b) => a - b)
  if (sum === target && !isInSolution(sumArray, solution))
    solution.push(sumArray)
}

Let's fired up this bad boy.

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

Boom! Now that's how you get some Leetcoding done.

Here's the complete code for Attempt 1:

var threeSum = (nums, target = 0) => {
    var solution = []

    for(let a = 0; a < nums.length; a++) {
        for(let b = 0; b < nums.length; b++) {
            for(let c = 0; c < nums.length; c++) {
                if (a !== b && b !== c && a !== c) {
                    let sum = nums[a] + nums[b] + nums[c]
                    let sumArray = [nums[a], nums[b], nums[c]].sort((a, b) => a - b)
                    if (sum === target && !isInSolution(sumArray, solution))
                        solution.push(sumArray)   
                }
            }
        }
    }
    return solution
}

var isInSolution = (newArray, solutionArray) => {
    let dup = false
    let [a, b, c] = newArray

    solutionArray.forEach(array => {
        let [d, e, f] = array
        if (a === d && b === e && c === f) dup = true
    })

    return dup
}

Look at all that beautiful code. There's functions calling functions, there's a couple of instances of one liner sort functions, arrow functions, logic tests... now that's some verbose coding there!

It's the equivalent of driving a Ford F-150 with mudding tires, chrome rims, flames painted across the sides, a big American flag, and Garth Brooks blasting on the radio just to go pick up a half gallon of milk from the Seven Eleven around the corner.

This is gonna be amazing.

.

.

.

.

.

TIME LIMIT EXCEEDED

Well... I guess throwing three loops together isn't going to efficiently get the job done.

Attempt 2: If I Only Had A Brain

Since hammers won't work, it's time to use a little finesse and actually think about what this problem is asking.

The core question boils down to this: a + b + c = 0.

And if you really think about it, we only need to know two of the numbers, and make sure the third one exists.

Let's try this whole thing from a different angle:

var threeSum = (nums) => {
    var solution = []

    for(let i = 0; i < nums.length; i++) {
        var newArray = [...nums]
        var firstNum = newArray.splice(i, 1)[0]

        for(let j = 0; j < newArray.length; j++) {
            var secondNum = newArray[j]
            let diff = (firstNum + secondNum) * -1
            if (newArray.indexOf(diff) > -1 && newArray.indexOf(diff) !== j)
                solution.push([firstNum, secondNum, diff])
        }
    }

    return solution
}

The most biggest difference in this attempt is this:

let diff = (firstNum + secondNum) * -1

This should speed things up by letting us cut out one of the for loops in the previous attempt (spoiler alert: it doesn't).

When we run our first test run, we get this result:

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

This is all starting to look a bit too familiar.

So we go through the same steps as before, checking for duplication, yadda yadda yadda.

TIME LIMIT EXCEEDED

Well, if there's anything I've learned so far, if you need a very slow algorithm written, then I am your man (DM if interested).

Attempt 3: Being Clever

I can't decide if these questions are specifically made so that you have to think your way out of a proverbial Labyrinth of excessive thinking, or if I loved knocking over my Lego towers with my He-Man action figures too much as a kid.

There was definitely something to the a + b + c = 0 way of thinking. There's also something to the idea of avoiding walking through loops too much.

While thinking things over, something popped into my head; the old tried and true merge sort algorithm. The key to merge sort is to keep cutting the data down into more and more manageable pieces, until it's as easy as comparing two values.

So let's try this...

Like the line of thinking to add a + b + c = 0, if an array is ordered, then the two extremes should be able to set the parameters of what could possibly equal to 0.

Take our sample array: [-1, 0, 1, 2, -1, -4]

When organized it becomes: [2, 1, 0, -1, -1, -4] which means that the sum of the two most extreme numbers are: 2 + (-4) = -2.

Walking closer to the center will bring the number closer to zero.

Since the extremes currently add to -2 then moving the last element closer to the center will increase the total, and vice-versa if the sum is positive.

The biggest benefit of this is that we've cut two loops in half.

So let's get started.

var threeSum = nums => {
    const solutionArray = []

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

First things first, we're going to sort the nums array in a descending order (highest to lowest).

Next, we're going to add a couple of fail safes - you know, just in case Leetcode tries and trick us like the sneaky jerks they can be.

var threeSum = nums => {
    const solutionArray = []

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

    if (nums.length < 3) {
        return solutionArray
    }

    if (nums.length < 4) {
        if(nums[0] + nums[1] + nums[2] === 0) return [nums]
        return []
    }

Then we get to the meat of the algorithm.

First we want to iterate through the array.

    nums.forEach((num, i) => {
        let j = i + 1
        let k = nums.length - 1

The magic here is in the two variables we assign:

• j, which will be the beginning of our first half-loop
• k, which is the end of our second half-loops

"J" is the next element in the array after the the current forEach element, and that "k" is the last element in the array.

We're going to be walking the two ends of our array together, and seeing how many add to our target number of 0, until j and k meet (aka j < k).

while (j < k) {
  let sum = num + nums[j] + nums[k]
  if (sum === 0) {
    solutionArray.push([num, nums[j], nums[k]].sort((a, b) => a - b))
  }

  sum > 0 ? j++ : k--
}

As i iterates through, then the amount of elements j and k have to travel gets shorter on each iteration.

It's simplicity is annoying. And certainly nothing that I would've ever realized on first seeing the problem.

This is the complete code, including a few more adjustments to cover a few other special cases:

var threeSum = nums => {
    const solutionArray = []

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

    if (nums.length < 3) {
        return solutionArray
    }

    if (nums.length < 4) {
        if(nums[0] + nums[1] + nums[2] === 0) return [nums]
        return []
    }

    nums.forEach((num, i) => {
        let j = i + 1
        let k = nums.length - 1

        if (i !== j && num !== nums[i - 1]) {
            while (j < k) {
                let sum = num + nums[j] + nums[k]
                if (sum === 0) {
                    solutionArray.push([num, nums[j], nums[k]].sort((a, b) => a - b))
                    // this step is to skip duplicate numbers in the array
                    while(nums[j] === nums[j + 1]) j++
                    while(nums[k] === nums[k - 1]) k--
                }

                sum > 0 ? j++ : k--
            }
        }
    })
    return solutionArray
}

Click submit and SUCCESS

This is definitely not something that I would have just been able to figure out. But probing the problem from different directions led to certain insights that gave way to a solution.

And if anything, that's what I'd like to get across. I don't know how other programmers do it, but I'm certain wrong way more than I am right.

But it's perfectly ok, because there is always insight from each failure, and you never know what'll lead to a break through to solve the problem.

Onto the next challenge, and onto the next failure!

Comments

[Curtis Fenner]

There's actually a much simpler algorithm, which is also quadratic, that looks much more like the solution to "2SUM". It requires a lot less 'cleverness', and is more obviously correct:

1. Find all the solutions with only one distinct element (i.e., [0, 0, 0]). This can be done in linear time (count how many 0s are in the input)

2. Find all solutions with only two distinct elements (i.e., [x, x, -2*x]). This can be done in linear time, and is basically the same as "2SUM".

3. Find all solutions with three distinct elements.

   1. First, sort and throw away duplicates (we don't care about duplicates, because they would be captured in steps (1) and (2)
   2. For every (increasing) pair of elements, for (let a = 0; a < nums.length; a++) { for (let b = a + 1; b < nums.length; b++) {
   3. check if the value -(a + b) is in the array (like "2SUM"), and -(a + b) is bigger nums[b]. If so, we found a solution

[Ricardo Delgado]

I'd be curious how you'd write that. Seems like it would Timeout, but what do I know?

[Curtis Fenner]

The algorithm takes time proportional to the square of nums.length, just like your solution. Most programming problems on sites allow a fairly generous constant multiple of the fastest possible solution because they are usually just trying to get you on the right algorithmic solution and don't care so much about fine details.

On this particular problem, it looks like most solutions take around 160ms, but this one takes about 200ms.

// Returns a mapping of
// value => [first index `value` appears, last index `value` appears]
function buildIndex(nums) {
    let indexesByValue = {};
    for (let i = 0; i < nums.length; i++) {
        let num = nums[i];
        indexesByValue[num] = indexesByValue[num] || [i, i];
        indexesByValue[num][1] = i;
    }
    return indexesByValue;
}

function unique(list) {
    let out = [];
    for (let n of list) {
        if (out[out.length - 1] !== n) {
            out.push(n);
        }
    }
    return out;
}

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    let solution = [];

    // Find all solutions with only one distinct element (ie, all zero):
    if (nums.filter(x => x === 0).length >= 3) {
        solution.push([0, 0, 0]);
    }

    // Find all solutions with only two distinct elements (ie, x, and -2x):
    let indexesByValue = buildIndex(nums);
    for (let n in indexesByValue) {
        if (n == 0) continue;
        if (indexesByValue[n][1] != indexesByValue[n][0]) {
            if (indexesByValue[-2 * n]) {
                solution.push([n, n, -2*n]);
            }
        }
    }

    // Find all solutions with three distinct elements:
    nums.sort((a, b) => a - b);
    nums = unique(nums);
    indexesByValue = buildIndex(nums);
    for (let a = 0; a < nums.length; a++) {
        for (let b = a + 1; b < nums.length; b++) {
            let difference = -(nums[a] + nums[b]);
            if (difference > nums[b] && indexesByValue[difference]) {
                solution.push([nums[a], nums[b], difference]);
            }
        }
    }
    return solution;
};

[Ricardo Delgado]

Yeah, definitely runs a bit slower, but you know, lots of ways to open a banana.

I just think "more obviously correct" is a little off base, but you know, whatever works for you.

[Steve O]

I loved your thorough explanation!

I did find an issue in your final code which you posted:

When you iterate over the array, you use this conditional here:
if (i !== j && num !== nums[i - 1])

This will instantly fail. On the first iteration, i=0, therefore nums[i-1] is immediately OOB.
You can use a proxy in JS to allow negative indices fwiw.
Also, i will never equal j.