Find unique triplet closest to target in an array

0 / 161
Triplet sum closest

Problem Statement

 

Given an array of unsorted numbers and a target number, find a triplet in the array whose sum is as close to the target number as possible, return the sum of the triplet. If there are more than one such triplet, return the sum of the triplet with the smallest sum.

 

Example 1:

 

Input: [-2, 0, 1, 2], target=2

Output: 1

Explanation: The triplet [-2, 1, 2] has the closest sum to the target.

 

 

Example 2:

 

Input: [-3, 1, 1, 2], target=1

Output: 0

Explanation: The triplet [-3, 1, 2] has the closest sum to the target.

 

Example 3:

 

Input: [1, 0, 1, 1], target=100

Output: 3

Explanation: The triplet [1, 1, 1] has the closest sum to the target.

 

 

Solution

 

This problem follows the Two Pointers pattern and is quite similar to Triplet Sum to Zero.

We can follow a similar approach to iterate through the array, taking one number at a time. At every step, we will save the difference between the triplet and the target number, and at each step we will compare it with the minimum target difference so far, so that in the end, we can return the triplet with the closest sum.

 

Javascript code below:-

 

<script>

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
function threeSumClosest(nums, target) {
	var low = 0,
		high = 0;
	var smallest_target_diff = Infinity;

	nums.sort((a, b) => a - b);

	for (var i = 0; i < nums.length - 2; i++) {
		low = i + 1;
		high = nums.length - 1;

		while (low < high) {
			var triplet_sum = nums[i] + nums[low] + nums[high];
			var target_diff = target - triplet_sum;

			if (target_diff === 0) {
				return target - target_diff;
			}

			if (Math.abs(target_diff) < Math.abs(smallest_target_diff)) {
				smallest_target_diff = target_diff;
			}


			if (target_diff < 0) {
				high--;
			} else {
				low++;
			}

		}

	}

	return target - smallest_target_diff;
};

document.write(threeSumClosest([-2, 0, 1, 2], 2)+'<br/>');
document.write(threeSumClosest([-3, -1, 1, 2], 1)+'<br/>');
document.write(threeSumClosest([1, 0, 1, 1], 100)+'<br/>');

</script>

 

 

Time complexity

 

Sorting the array will take O(N* logN). Overall threeSumClosest() will take O(N * logN + N^2), which is asymptotically equivalent to O(N^2).

 

 

Space complexity

 

The space complexity of the above algorithm will be O(N) which is required for sorting.

 

 

 

Comments

comments


An avid reader, responsible for generating creative content ideas for golibrary.co. His interests include algorithms and programming languages. Blogging is a hobby and passion.

Related Posts