Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Solution: Triplet Sum Close to Target
Table of Contents

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.

Mark as Completed

Table of Contents

Problem Statement

Solution

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity