DEV Community

Cover image for All The Ways That I Failed At "Sum 3"

All The Ways That I Failed At "Sum 3"

Ricardo Delgado on September 07, 2019

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 ...
Collapse
 
curtisfenner profile image
Curtis Fenner • Edited

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
Collapse
 
rdelga80 profile image
Ricardo Delgado

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

Collapse
 
curtisfenner profile image
Curtis Fenner • Edited

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;
};
Thread Thread
 
rdelga80 profile image
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.

Collapse
 
steveochoa profile image
Steve O • Edited

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.