Discussion on: All The Ways That I Failed At "Sum 3"

[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.