Flex Coder

Table of Contents

Three Sum Problem in Javascript

Given an array of integers nums, your task is to find all unique triplets [nums[i], nums[j], nums[k]] such that nums[i] + nums[j] + nums[k] == 0.

Note: The solution set must not contain duplicate triplets.

Examples

Example 1:
Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]

Example 2:
Input: nums = []
Output: []

Example 3:
Input: nums = [0]
Output: []

Solution

There can be two approaches to solve this problem:

  1. Brute Force Approach
  2. Sort + Two Pointers Approach

Approach 1: Brute Force

This brute force method checks every possible triplet in the array to see if their sum is equal to zero. The time complexity is O(n³), and the space complexity is O(1).


const threeSum_BruteForce = function(nums) {
    let res = [];
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            for (let k = j + 1; k < nums.length; k++) {
                const sum = nums[i] + nums[j] + nums[k];
                if (sum === 0 && i !== j && i !== k && j !== k) {
                    let triplet = [nums[i], nums[j], nums[k]].sort();
                    if (!res.some(e => e[0] === triplet[0] && e[1] === triplet[1] && e[2] === triplet[2])) {
                        res.push(triplet);
                    }
                }
            }
        }
    }
    return res;
};

• Time Complexity:O(n³), where n is the size of the array. We check all triplets.

• Space Complexity:O(1), as we only use a constant amount of space.



Approach 2: Sort + Two Pointers

This approach first sorts the array, then uses two pointers to find pairs that sum with the selected number to zero. The time complexity is O(n²) due to the nested loop and sorting, and the space complexity is O(1).


var threeSum = function(nums) {
    const results = [];
    if (nums.length < 3) return results;
    
    nums.sort((a, b) => a - b);
    let target = 0;

    for (let i = 0; i < nums.length - 2; i++) {
        if (nums[i] > target) break;
        if (i > 0 && nums[i] === nums[i - 1]) continue;

        let l = i + 1, r = nums.length - 1;

        while (l < r) {
            let sum = nums[i] + nums[l] + nums[r];
            if (sum === target) {
                results.push([nums[i], nums[l], nums[r]]);
                while (nums[l] === nums[l + 1]) l++;
                while (nums[r] === nums[r - 1]) r--;
                l++;
                r--;
            } else if (sum < target) {
                l++;
            } else {
                r--;
            }
        }
    }
    return results;
};

• Time Complexity:O(n²), where n is the size of the array due to the nested loop.

• Space Complexity:O(1), as we only use a constant amount of space.

Back to Posts