Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Triplet Sum Close to Target

Problem Statement

Solution

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity

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: 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>

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, so that in the end, we can return the triplet with the closest sum.

Here's a detailed walkthrough of the algorithm:

  1. Initially, the method checks whether the input array arr is null or its length is less than 3. If either condition is true, the method throws an IllegalArgumentException, as it is impossible to find a triplet in these cases.

  2. The input array arr is then sorted in ascending order. Sorting is important as it allows us to move our pointers based on the sum we are getting and how close we are to the target sum.

  3. The smallestDifference variable is initialized to Integer.MAX_VALUE, which will keep track of the smallest difference we have found so far between our target sum and the sum of our current triplet.

  4. The function then iterates through arr using a for loop, stopping when it is two positions from the end of arr (arr.length - 2). This is because we are always looking for triplets and thus don't need to consider the last two positions in this loop.

  5. Inside the for loop, two pointers, left and right, are initialized. left is set to i + 1 (one position to the right of our current position) and right is set to the last index of the array (arr.length - 1).

  6. We start a while that continues as long as left is less than right. Inside this loop, we calculate the difference between the target sum and the sum of the numbers at our current positions in the array (targetDiff). This allows us to see how close the current triplet sum is to our target sum.

  7. If targetDiff equals 0, that means the sum of our current triplet exactly matches the target sum, and we return the targetSum immediately as our result.

  8. Otherwise, we check if the absolute value of targetDiff is less than the absolute value of smallestDifference (meaning we've found a closer sum), or if it's equal but targetDiff is greater (meaning it's a larger sum that is equally close). If either condition is true, we update smallestDifference with targetDiff.

  9. Next, we check if targetDiff is greater than 0. If it is, we increment left to try and increase our current triplet sum (since the array is sorted, moving left to the right will increase the sum). If targetDiff is not greater than 0, we decrement right to decrease our triplet sum.

  10. This while loop continues until left and right cross, at which point we have examined all possible triplets for our current value of i.

  11. The for loop continues until we have tried every possible starting point for our triplet.

  12. Once all possible triplets have been considered, the function returns targetSum - smallestDifference. This is the sum of the triplet that was closest to our target sum.

Algorithm Walkthrough

Let's walk through the algorithm step by step using the example array [0, 0, 1, 1, 2, 6] with a target sum of 5.

  1. Initial Check:

    • The array is not null and has more than 3 elements, so we proceed.

  2. Sorting the Array:

    • The sorted array is [0, 0, 1, 1, 2, 6].

  3. Initialization:

    • smallestDifference is set to Integer.MAX_VALUE.

  4. Iterating through the Array:

    • We start with i = 0, so the fixed element is 0.

  5. Setting Pointers:

    • left is set to 1, right is set to 5.

  6. First Iteration (i = 0):

    • Calculating Target Difference:
      • targetDiff = 5 - 0 - 0 - 6 = -1.
      • Math.abs(targetDiff) < Math.abs(smallestDifference) is true.
      • Update smallestDifference = -1.
      • Since targetDiff < 0, move the right pointer to 4.
    • Next Calculation:
      • targetDiff = 5 - 0 - 0 - 2 = 3.
      • Math.abs(targetDiff) < Math.abs(smallestDifference) is false.
      • smallestDifference = -1.
      • Since targetDiff > 0, move the left pointer to 2.
    • Next Calculation:
      • targetDiff = 5 - 0 - 1 - 2 = 2.
      • Math.abs(targetDiff) < Math.abs(smallestDifference) is false.
      • smallestDifference = -1 .
      • Since targetDiff > 0, move the left pointer to 3.
    • Next Calculation:
      • targetDiff = 5 - 0 - 1 - 1 = 3.
      • Math.abs(targetDiff) < Math.abs(smallestDifference) is false.
      • Since targetDiff > 0, move the left pointer to 4.
    • Pointers Meet:
      • left pointer is now equal to right, so end the inner loop.

  7. Second Iteration (i = 1):

    • left is set to 2, right is set to 5.
    • Calculating Target Difference:
      • targetDiff = 5 - 0 - 1 - 6 = -2.
      • Math.abs(targetDiff) < Math.abs(smallestDifference) is false.
      • Since targetDiff < 0, move the right pointer to 4.
    • Next Calculation:
      • targetDiff = 5 - 0 - 1 - 2 = 2.
      • Math.abs(targetDiff) < Math.abs(smallestDifference) is false.
      • Since targetDiff > 0, move the left pointer to 3.
    • Next Calculation:
      • targetDiff = 5 - 0 - 1 - 1 = 3.
      • Math.abs(targetDiff) < Math.abs(smallestDifference) is false.
      • Since targetDiff > 0, move the left pointer to 4.
    • Pointers Meet:
      • left pointer is now equal to right, so end the inner loop.

  8. Third Iteration (i = 2):

    • left is set to 3, right is set to 5.
    • Calculating Target Difference:
      • targetDiff = 5 - 1 - 1 - 6 = -3.
      • Math.abs(targetDiff) < Math.abs(smallestDifference) is false.
      • Since targetDiff < 0, move the right pointer to 4.
    • Next Calculation:
      • targetDiff = 5 - 1 - 1 - 2 = 1.
      • Math.abs(targetDiff) == Math.abs(smallestDifference) && targetDiff > smallestDifference is true.
      • Update smallestDifference = 1.
      • Since targetDiff > 0, move the left pointer to 4.
    • Pointers Meet:
      • left pointer is now equal to right, so end the inner loop.

  9. Fourth Iteration (i = 3):

    • left is set to 4, right is set to 5.
    • Calculating Target Difference:
      • targetDiff = 5 - 1 - 2 - 6 = -4.
      • Math.abs(targetDiff) < Math.abs(smallestDifference) is false.
      • Since targetDiff < 0, move the right pointer to 4.

  10. End of Iteration:

    • The for loop ends as i is now equal to 3.

  11. Result:

    • The closest triplet sum to the target is 5 - smallestDifference = 5 - 1 = 4.

Let's visualize example 4 via the below diagram.

Image

Code

Here is what our algorithm will look like:

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • Sorting the array: The algorithm first sorts the input array, which takes O(N \log N) time, where N is the number of elements in the array.

  • Outer loop: The main loop runs N - 2 times (from index 0 to N-3), which gives us O(N).

  • Two-pointer search: For each iteration of the outer loop, the two-pointer search runs O(N) to find the closest sum. Hence, the time complexity for the two-pointer search is O(N) for each iteration of the outer loop.

Overall time complexity: The total time complexity is O(N \log N + N^2), and since N^2 dominates N \log N, the overall time complexity is O(N^2).

Space Complexity

  • Sorting the array: Sorting the array requires additional space, and this adds O(N) space complexity.

  • Constant extra space: Apart from the space used by sorting, the algorithm only uses a few variables (left, right, smallestDifference), which take constant space O(1).

Overall space complexity: O(N) due to the space required by the sorting operation.

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

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

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

C

CaptainKidd

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

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

Solution

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity