Leetcode – 15. 3sum (yes, threesum)

Problem

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Idea

Brute force

We all know the brute force solution. Loop inside a loop inside a loop. And yeah, it does not work because 100% it will cause time exceed error.

Two pointers solution

It takes me quite a lot of time to build the solution for this problem because it’s easy to get the time exceed error. The solution needs to be good enough to pass all the tests.

1. Sort the array to handle duplicates and simplify pointer logic.
2. Fix the first element nums[i], and use two pointers l and r to find two other numbers such that nums[i] + nums[l] + nums[r] == 0.
3. Skip duplicates for both the fixed and pointer elements to avoid repeated results.
4. Move pointers based on whether the sum is too small or too large.

const threeSum = function(nums) {
    let result = [];
    nums = nums.sort((a, b) => a - b);
    
    for (let i = 0; i < nums.length - 2; i++) {
        // ignore duplicates
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        
        let k = nums.length - 1;
        let j = i + 1;
        
        while (j < k) {
            const total = nums[i] + nums[j] + nums[k];
            if (total > 0) {
                k--;
                continue;
            } else if (total < 0) {
                j++;
                continue;
            } else {
                result.push([nums[i], nums[j], nums[k]]);
                // ignore duplicates
                while (j < k && nums[j] === nums[j + 1]) j++;
                while (j < k && nums[k] === nums[k - 1]) k--;
                j++;
                k--;
            }
        }
    }

    return result;
}