Closest Triplet Sum

Problem

Given a target number and a list of numbers, find a triplet of numbers from the list such that sum of that triplet is the closest to the target. Return that sum.

Example 1

{
"target": 9,
"numbers": [2, 8, 3, 2]
}

Output:

7

Example 2

{
"target": 16,
"numbers": [11, -2, 17, -6, 9]
}

Output:

14

Solution

function find_closest_triplet_sum(target, numbers) {
    // Sort the array
    numbers.sort((a, b) => a - b);

    // To store the closest sum
    let closestSum = Number.MAX_VALUE;

    // Run three nested loops each loop for each element of triplet
    for (let i = 0; i < numbers.length; i++) {
        for (let j = i + 1; j < numbers.length; j++) {
            for (let k = j + 1; k < numbers.length; k++) {

                // Update the closestSum
                if (Math.abs(target - closestSum) >
                    Math.abs(target - (numbers[i] + numbers[j] + numbers[k])))
                    closestSum = (numbers[i] + numbers[j] + numbers[k]);
            }
        }
    }

    // Return the closest sum found
    return closestSum;
}

Time and Space Complexity

Time Complexity : O(N2)
Space Complexity: O(1)