Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Triplet Sum Close to Target

Problem Statement

Why this is a Two Pointers problem

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>

Why this is a Two Pointers problem

What the question saysThe signal it matches
"find a triplet in the array whose sum is as close to the target number as possible"you are asked for a triplet that meets a condition, here a comparison rather than an exact match
"an array of unsorted numbers", and the answer returned is a sumthe input can be sorted first, because no positions are reported
checking every triplet means three nested loopsyour first idea is nested loops

The shape is the same as Triplet Sum to Zero: an outer loop fixes one number and two pointers handle the rest, the fixed value plus a pair variant.

The closest alternative. A search feels like the alternative, because the question asks for the closest sum rather than an exact match. Sorting removes the search.

Once the numbers are in order, a sum below the target can only grow by moving the left pointer right. So every comparison tells you which pointer to move.

Solution

This is Triplet Sum to Zero with the condition relaxed. Instead of an exact sum we want the closest one.

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. The constraints promise at least three numbers, so a triplet always exists and no guard is needed. The Java version still opens with a defensive check for a missing or too short array; the other versions leave it out.

  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 the largest value the language can hold, so that the first triplet always beats it. It keeps track of the smallest difference found so far between the target sum and the sum of the 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 has at least 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 the largest value the language can hold.

  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.

Carol Lisbon

Carol Lisbon

· 4 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
Show 1 reply
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
Show 1 reply
Sachin Dev S

Sachin Dev S

· 6 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;
  }
}


``
Show 1 reply
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
Show 1 reply
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.

Show 1 reply
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)?

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
sealess

sealess

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

Vote for new content

On This Page

Problem Statement

Why this is a Two Pointers problem

Solution

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity