Flex Coder

Table of Contents

Three Sum Closest Problem in Javascript

Given an array of integers nums and an integer target, your task is to find the sum of three integers in nums such that the sum is closest to target.

Note: The solution set must not contain duplicate triplets.

Examples

Example 1:
Input: nums = [-1, 2, 1, -4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

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 which sum is closest to the target. The time complexity is O(n³), and the space complexity is O(1).


const threeSumClosest_BruteForce = function(nums, target) {
    let minDiff = Number.MAX_VALUE; // Minimum difference from target
    let closestSum = 0; // Closest sum found

    for (let i = 0; i < nums.length - 2; i++) {
        for (let j = i + 1; j < nums.length - 1; j++) {
            for (let k = j + 1; k < nums.length; k++) {
                let currentSum = nums[i] + nums[j] + nums[k];
                let currentDiff = Math.abs(currentSum - target);
                if (currentDiff < minDiff) {
                    minDiff = currentDiff;
                    closestSum = currentSum;
                }
            }
        }
    }
    return closestSum;
};

• 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 closest to the target. The time complexity is O(n²) due to the nested loop and sorting, and the space complexity is O(1).


var threeSumClosest = function(nums, target) {
    nums.sort((a, b) => a - b);
    let closestSum = Infinity; // Have to find the closest sum

    for (let i = 0; i < nums.length - 2; i++) {
        let leftPointer = i + 1, rightPointer = nums.length - 1;

        while (leftPointer < rightPointer) {
            let currentSum = nums[i] + nums[leftPointer] + nums[rightPointer];
            let currentDiff = Math.abs(currentSum - target);

            if (currentDiff < Math.abs(closestSum - target)) {
                closestSum = currentSum; // Update closest sum
            }

            if (currentSum > target) rightPointer--;
            else leftPointer++;
        }
    }
    return closestSum;
};

• 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