all articles

leetcode war 15 - 3Sum

2017-09-26 @sunderls

leetCode js

https://leetcode.com/problems/3sum/description/

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

analysis

loop all integers, which leads to O(n3) complexity and it is not ideal.

for a + b + c === 0, they cannot be all positives or negatives, so, maybe we can do some sorting first.

sorting cost us (On2).

the possible improvable part is that maybe we can avoid do something extreme.

after we sort the numbers, let's focus on the middle one b.

  1. a and c must be seperated by b
  2. if we select some triple, and the sum is larger than 0, then we must choose some integer smaller than c.

this is the same as leetcode war 11 - Container With Most Water.

so try every number to the middle one O(n), and O(n) for each round, this leads to O(n2).

in total `O(n2).

trial 1

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

    // first lets sort the array
    nums.sort(function(a, b) {
        if (a < b) {
            return -1;
        }

        if (a > b) {
            return 1;
        }

        return 0;
    });

    if (nums.length < 3) {
        return result;
    }
    // try every number as the middle one
    for (var i = 1, max = nums.length - 1; i < max; i++) {
        var j = 0;
        var k = nums.length - 1;
        while (j < i && k > i) {
            var sum = nums[j] + nums[i] + nums[k];
            if (sum === 0) {
                result.push([nums[j], nums[i], nums[k]]);
                j++;
                k--;
            } else if (sum < 0) {
                j++;
            } else {
                k--;
            }
        }
    }

    return result;
};

and it faild for duplicate patterns.

trial 2 - deduplicate

the error leading input is [0, 0, 0, 0]. since we are traversing based on the number in the middle, so if some triple is duplicated, the middle one must be the same. (because array is sorted).

let's say we move i to i+1, if num[i] === num[i + 1], we can ignore the start in [0, i - 1], because for [0, i - 1], it is already checked for i.

and when we are moving j, k we must skip the same number also.

if there is a duplications, say

a[j], a[i], a[l]

a[p], a[q], a[n]

it must be this order

a[j] a[p] a[i] a[q] a[l] a[n]

because a[i] === a[q], so we have skipped p < i, so p must equal i.

so a[j] === a[p] === a[i].

which means duplicate triple in our algorythm must have the first two numbers at the same.

so we shoud skip this case when we encounter it.

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

    // first lets sort the array
    nums.sort(function(a, b) {
        if (a < b) {
            return -1;
        }

        if (a > b) {
            return 1;
        }

        return 0;
    });

    if (nums.length < 3) {
        return result;
    }

    // try every number as the middle one
    for (var i = 1, max = nums.length - 1; i < max; i++) {
        var j = 0;
        var k = nums.length - 1;

        // if encounter two same numbers
        // we can skip checking j < i - 1
        if (nums[i] === nums[i - 1]) {
            j = i - 1;
        }

        while (j < i && k > i) {
            var sum = nums[j] + nums[i] + nums[k];

            if (sum === 0) {
                result.push([nums[j], nums[i], nums[k]]);

                // for case like -1 -1 2
                // we should move the middle number just right to the next different value
                // because the triple is already collected    
                if (nums[j] === nums[i]) {
                    while (i < max && nums[i + 1] === nums[i]) {
                        i++;
                    }
                }
            }

            if (sum <= 0) {
                j++;
                while (j < i && nums[j] === nums[j - 1]) {
                    j++;
                }
            }

            if (sum >= 0) {
                k--;
                while (k > i && nums[k] === nums[k + 1]) {
                    k--;
                }
            }
        }
    }

    return result;
};

at it passed, beating 80% submission.

how can we improve?