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
. . . .
A

Anonymous

· 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
A

Anonymous

· 3 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
A

Anonymous

· 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.

A

Anonymous

· 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
A

Anonymous

· 3 years ago

The smallest_differencevalue should be -1 not 1 initially for the triplate of [0,0,6]. It changes to 1 when the triplate is [0,2,2]. This can be slightly confusing...

A

Anonymous

· 3 years ago

In solution by JavaScript i found some initial parameters, with which solution becomes incorrect. This parameters are: Input: [91, 74, 73, 85, 73, 81, 87], target: 230. Current solution returns 231, which is not right because it is bigger than target. Replacing this fragment from solution:

if (Math.abs(target_diff) < Math.abs(smallest_difference) || (Math.abs(target_diff) === Math.abs(smallest_difference) && target_diff > smallest_difference)) { smallest_difference = target_diff; // save the closest and the biggest difference

}

with this fragment:

if ( targetDiff >= 0 && (Math.abs(targetDiff) < Math.abs(smallestDifference) || ( Math.abs(targetDiff) === Math.abs(smallestDifference) && targetDiff > smallestDifference ))) { smallestDifference = targetDiff; }

mak

Show 1 reply
A

Anonymous

· 3 years ago

C# Solution is missing.

Show 1 reply
A

Anonymous

· 3 years ago

Why are we mentioning the second triplet with a sum less than 3, the output is 2 because the sum of the first triplet -1,0,3 is 2 which is as close as possible (distance of 1) to the target of 3.

The second triplet in the example wouldn't even be considered because our algorithm always tries to move closer to the target so it will not consider that triplet.

@Design Gurus guys please fix this

A

Anonymous

· 3 years ago

Variable names in this exercise are distracting, they may be more intuitive.

A

Anonymous

· 3 years ago

The explanation to this seems to be written for a java solution. The first point is wrong as the code is not checking the array length at all???

Reading Progress

0%

Vote for new content

On This Page

Problem Statement

Try it yourself