all articles

leetcode war 18 - 4Sum

2017-10-06 @sunderls

leetCode js

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

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

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
[-1,  0, 0, 1],
[-2, -1, 1, 2],
[-2,  0, 0, 2]
]

analysis

we've done the 3Sum version, maybe we can extend it to support 4-sum.

take a + b + c + d == 0 as a example: if we fix b and c each round the complexity would be:

O(nC2) + O(n*n) = o(n2)

let's do it

solution - two cursors

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
    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 < 4) {
        return result;
    }

    // try every number pair as the middle pair
    for (var i = 1, maxI = nums.length - 1 - 2; i <= maxI; i++) {
        for (var j = i + 1, maxJ = nums.length - 1 - 1; j <= maxJ; j++) {

            var p = 0;
            var q = nums.length - 1;

            // if encounter two same numbers
            // we can skip checking p < i - 1
            if (nums[i] === nums[i - 1]) {
                p = i - 1;
            }
            var sum = 0;
            while (p < i && q > j) {
                sum = nums[p] + nums[i] + nums[j] + nums[q];

                if (sum === target) {
                    result.push([nums[p], nums[i], nums[j], nums[q]]);

                    // 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[p] === nums[i]) {
                        while (i < maxI && nums[i + 1] === nums[i]) {
                            i++;
                        }
                    }
                }

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

                if (sum >= target) {
                    q--;
                    while (q > j && nums[q] === nums[q + 1]) {
                        q--;
                    }
                }
            }
        }
    }

    return result;
};

it failed to pass, because [i, j] may cause duplications

trial 2 - deduplicate

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
    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 < 4) {
        return result;
    }

    // try every number pair as the middle pair
    for (var i = 1, maxI = nums.length - 1 - 2; i <= maxI; i++) {
        for (var j = i + 1, maxJ = nums.length - 1 - 1; j <= maxJ; j++) {

            var p = 0;
            var q = nums.length - 1;

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

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

                if (sum === target) {
                    result.push([nums[p], nums[i], nums[j], nums[q]]);

                    // 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[p] === nums[i]) {
                        while (i < maxI && nums[i + 1] === nums[i]) {
                            i++;
                        }
                    }
                }

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

                if (sum >= target) {
                    q--;
                    while (q > j && nums[q] === nums[q + 1]) {
                        q--;
                    }
                }
            }

            // to avoid duplicate [nums[i], nums[j]]
            // move j to the next different number
            while(nums[j + 1] === nums[j]) {
                j++;
            }
        }
    }

    return result;
};

it passed, running bottom 30%. too slow, need to improve, but how?