Grokking the Coding Interview: Patterns for Coding Questions

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
. . . .
Mark as Completed
H

hj3yoo

· 4 years ago

On line 19 of Python solution, why is it overriding smallest_difference if the new target_diff is BIGGER rather than smaller than the existing value?

If the target_sum = 2, smallest_difference = 1, target_diff = 3, shouldn't smallest_difference continue to be 1? The problem statement mentions to return the smallest sum for tie-breaker.

Show 1 reply
Landon Brown

Landon Brown

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

Anthony DiFede

· 4 years ago

Any feedback for this solution?

Image

Show 2 replies
L

Learner

· 5 years ago

// the second part of the following 'if' is to handle the smallest sum when we // have more than one solution

Isn't the second part unnecessary? Smallest is smallest, nothing changes even if they are the same. Can you please explain with an example if I have misunderstood?

Show 6 replies
Bruno Ely

Bruno Ely

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

C

CaptainKidd

· 3 years ago

As a side note for this question as well. arr.length - 2 in the initial for loop is unnecessary. While technically correct as you will get the correct answer you need only look at earlier examples of the 3 sum style problem to see that it works fine without.

Technically you are narrowing down the number of times the for loop needs to iterate but it's such a small amount that any savings would be safely ignored in simplified time complexity analysis.

E

Edu

· 4 years ago

Given that MDN says that the sort method on the Array prototype is in place, wouldn't the space complexity be O(1)? If that's not correct, could you explain why the space complexity is O(N), please?

Show 4 replies
A

Ada

· 4 years ago

What is the point of " i < arr.length - 2" in the JS solution? I've been writing my solutions in Swift from the JS answers. I tried "

Show 2 replies
A

Abhinav Gupta

· 4 years ago

Can you please help me in explaining the if condition '(Math.abs(targetDiff) == Math.abs(smallestDifference) && targetDiff > smallestDifference)'

Also, can you please help me with an example?

Thanks

Show 3 replies

On This Page

Problem Statement

Try it yourself