Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Triplet Sum Close to Target (medium)

Problem Statement

Try it yourself

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: [-1, 0, 2, 3], target=3 
Output: 2
Explanation: The triplet [-1, 0, 3] has the sum '2' which is closest to the target.

There are two triplets with distance '1' from the target: [-1, 0, 3] & [-1, 2, 3]. Between these two triplets, the correct answer will be [-1, 0, 3] as it has a sum '2' which is less than the sum of the other triplet which is '4'. This is because of the following requirement: 'If there are more than one such triplet, return the sum of the triplet with the smallest sum.'

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.

Example 4:

Input: [0, 0, 1, 1, 2, 6], target=5
Output: 4
Explanation: There are two triplets with distance '1' from target: [1, 1, 2] & [0, 0, 6]. Between these two triplets, the correct answer will be [1, 1, 2] as it has a sum '4' which is less than the sum of the other triplet which is '6'. This is because of the following requirement: 'If there are more than one such triplet, return the sum of the triplet with the smallest sum.'

Constraints:

  • 3 <= arr.length <= 500
  • -1000 <= arr[i] <= 1000
  • -10<sup>4</sup> <= target <= 10<sup>4</sup>

Try it yourself

Try solving this question here:

Python3
Python3
. . . .
Carol Lisbon

Carol Lisbon

· 3 months ago

import math

class Solution:
  def searchTriplet(self, arr, target):
    closest_sum = math.inf
    arr.sort()

    for i in range(len(arr)-2):
      left_i = i+1
      right_i = len(arr)-1
      while left_i < right_i:
        curr_triple_sum = arr[i] + arr[left_i] + arr[right_i]
        if target == curr_triple_sum:
          return curr_triple_sum
        
        curr_diff = abs(target - curr_triple_sum)
        closest_diff = abs(target - closest_sum)
        if curr_diff < closest_diff or (curr_diff == closest_diff and curr_triple_sum < closest_sum):
          closest_sum = curr_triple_sum

        if curr_triple_sum < target:
          left_i += 1
        else:
          right_i -= 1
        
        
    
    return closest_sum
Harsh Kapadia

Harsh Kapadia

· 4 months ago

def find_closest_triplet_sum(nums, target):
    # Step 1: Sort the array
    nums.sort()
    
    # Initialize with a very large difference or a starting sum
    closest_sum = float('inf')
    
    for i in range(len(nums) - 2):
        left = i + 1
        right = len(nums) - 1
        
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            
            # Perfect match! Return immediately
            if current_sum == target:
                return current_sum
            
            # Logic for updating the 'closest_sum'
            curr_diff = abs(target - current_sum)
            best_diff = abs(target - closest_sum)
            
            # TIE-BREAKER LOGIC:
            # 1. If current_sum is closer to target than closest_sum
Sachin Dev S

Sachin Dev S

· 5 months ago

simpler to understand solution

import java.util.*;

class Solution {

  public int searchTriplet(int[] arr, int targetSum) {
    int minDiff = Integer.MAX_VALUE, minSum = Integer.MAX_VALUE;

    int n = arr.length;

    Arrays.sort(arr);
    
    for(int i = 0; i < n-2; i++) {
      int left = i+1, right = n-1;
      while(left < right) {
        int sum = arr[i] + arr[left] + arr[right];

        if(targetSum - sum == 0) return sum;

        // sum < target sum
        int diff = Math.abs(sum-targetSum);
        if(diff < minDiff) {
          minDiff = diff;
          minSum = sum;
        } else if (diff == minDiff) {
          minSum = Math.min(minSum, sum);
        }

        if(sum < targetSum) left++;
        else right--;
      }
    }

    return minSum;
  }
}


``
Durgance Gaur

Durgance Gaur

· 9 months ago

<p>```python import math class Solution: def searchTriplet(self, arr, target_sum): # TODO: Write your code here arr.sort() score = float('inf') for i in range(len(arr)): target = arr[i] left = i+1 right = len(arr)-1 while left= abs(target_sum-total): score = min(score,abs(target_sum-total)) ans = total left += 1 elif total &gt; target_sum: if score &gt; abs(target_sum-total): score = min(score,abs(target_sum-total)) ans = total right -= 1 else: return target_sum return ans ``` ## In the the approach.. I have used a score variable to check for the difference between the target_sum and total and then compared it with previous score and used = sign only in the case when the total is less then the target_sum so that we can update the ans variable even when the score is already the same as the
M

mananpat

· a year ago

Input: [1, 0, 1, 1], target=100 Output: 3 Explanation: The triplet [1, 1, 1] has the closest sum to the target.

V F

V F

· 2 years ago

if (Math.abs(targetDiff) < Math.abs(smallestDifference)
            || (Math.abs(targetDiff) == Math.abs(smallestDifference)

Can't this be written as Math.abs(targetDiff) <= Math.abs(smallestDifference)?

Eric Imho Jang

Eric Imho Jang

· 2 years ago

import math

class Solution:
  def searchTriplet(self, arr, target_sum):
    arr.sort()
    
    smallestDiff = math.inf
    closestSum = math.inf
    for i in range(len(arr) - 1):
      fix = i
      left = i+1
      right = len(arr)-1
      
      while left < right:
        currentSum = arr[fix] + arr[left] + arr[right]
        if currentSum == target_sum:
          return currentSum
        elif currentSum < target_sum:
          left += 1
        else:
          right -= 1
        
        diff = currentSum - target_sum
        if abs(diff) < abs(smallestDiff):
          smallestDiff = diff
          closestSum = currentSum
        elif abs(diff) == abs(smallestDiff):
          closestSum = min(currentSum, closestSum)
    return closestSum
Show 1 reply
sealess

sealess

· 2 years ago

import math

class Solution:
  def searchTriplet(self, arr, target_sum):
    # TODO: Write your code here
    arr.sort()
    curr = arr[0] + arr[1] +arr[2]
    gap = abs(curr - target_sum)
    for i in range(len(arr)):
      l, r = i+1, len(arr)-1
      while l < r:
        newcurr = arr[i] + arr[l] + arr[r]
        newgap = abs(newcurr - target_sum)
        if newgap<gap:
          gap= newgap
          curr = newcurr
        elif newgap == gap and newcurr < curr:
          gap= newgap
          curr = newcurr
        if newcurr > target_sum:
          r-=1
        elif newcurr < target_sum:
          l +=1
        else:
          return target_sum
    return curr
Bruno Ely

Bruno Ely

· 3 years ago

Should be [1, 1, 2] (sum == 4) as shown in the example 4 in problem statement, not [0, 0, 6] (sum == 6) as shown in visualization, since problem asks for smallest sum if distance to target is the same.

Landon Brown

Landon Brown

· 3 years ago

import math

class Solution:
  def searchTriplet(self, arr, target_sum):
    # TODO: Write your code here
    arr.sort()
    smallest_diff = math.inf
    closest_sum = math.inf
    l = 0
    while l < len(arr):
      m = l + 1
      r = len(arr)-1
      while m < r:
        val_sum = arr[l] + arr[m] + arr[r]
        if val_sum == target_sum:
          return val_sum
        if abs(target_sum-val_sum) < abs(smallest_diff) or val_sum < closest_sum:
          smallest_diff = target_sum-val_sum
          closest_sum = val_sum
        if val_sum > target_sum:
          r -= 1
        else:
          m += 1
      l += 1
    return target_sum-smallest_diff
Show 1 reply

Reading Progress

0%

On This Page

Problem Statement

Try it yourself