3Sum Closest LeetCode

Key takeaways:
The problem asks to find three integers in an array whose sum is closest to a given target.
The input is an array of integers and a target value.
The task is to return the sum of three integers that is closest to the target.
Sorting the array simplifies finding the closest sum.
Two pointers are used after fixing one element to find the other two elements that sum closest to the target.
Time complexity is $O(n log n)$ for sorting, with an additional $O(n)$ for the two-pointer approach.

The 3Sum Closest problem involves finding the triplet of integers in an array whose sum is closest to a given target value. This problem is significant because it helps in scenarios where we need to approximate a desired sum with minimal deviation. For instance, in financial forecasting, identifying the closest sum can aid in making accurate predictions.

Consider an example where we have an array [-1, 2, 1, -4, 5] and a target value of 1. By finding the triplet with the closest sum to 1 (e.g., -1 + 1 + 2 = 2), we can visualize this sum in the following illustration:

Problem statement

Find three integers in a given integer array numbers of length n and an integer target, such that their sum is closest to the target value.

Return the sum of the three integers that are closest to the target.

Assume that each input array numbers has exactly one solution.

Explanation

The task is to find three numbers in a given list of integers (array) so that their sum is as close as possible to a specified target value. The goal is to return the sum of those three numbers. It’s assumed that there is exactly one solution for each input list.

Expected Input:

A list of integers numbers, which represents the input array.
An integer target, indicating the target value.

Expected Output:

An integer representing the sum of three integers in the array numbers that is closest to the target value target.

Examples

Let’s discuss some examples to understand the concept of three sum closest:

Example 1:

Sort the array: After sorting, the array becomes [-20, 10, 15, 25].
Initialize res: Initialize res to the sum of the first three numbers: -20 + 10 + 15 = 5.
Iterate through the array: Start iterating through the array elements.
For i = 0:
1. Initialize pointers start = 1 and end = 3.
2. While loop:
  1. Calculate current_sum = -20 + 10 + 25 = 15.
  2. Adjust pointers: Decrement end.
  3. Calculate current_sum again: -20 + 10 + 15 = 5.
  4. Update res to current_sum.
For i = 1:
1. Initialize pointers start = 2 and end = 3.
2. While loop:
  1. Calculate current_sum = 10 + 15 + 25 = 50.
  2. Adjust pointers: Decrement end.
  3. Calculate current_sum again: 10 + 15 + 15 = 40.
  4. No update to res.
For i = 2:
1. Initialize pointers start = 3 and end = 3.
2. While loop:
  1. Calculate current_sum = 15 + 25 + 25 = 65.
  2. Adjust pointers: Decrement end.
  3. No update to res.
Return res: The function returns 5, as it represents the closest sum to the target.
The closest sum of three integers in the array numbers to the target value 5 is 5.

Code

We already discussed the process and algorithm to solve the problem. Now, let’s code it!

def threeSumClosest(nums, target):
    nums.sort()
    res = sum(nums[:3])
    for i in range(len(nums) - 2):
        start = i + 1
        end = len(nums) - 1
        
        while start < end:
            current_sum = nums[i] + nums[start] + nums[end]
            if current_sum > target:
                end -= 1
            else:
                start += 1
            if abs(current_sum - target) < abs(res - target):
                res = current_sum
    return res
# Example usage:
numbers = [10, -20, 15, 25]
target = 5
result = threeSumClosest(numbers, target)
print("Closest sum of three integers:", result)

3 sum closest

Educative 99 helps you solve complex coding problems by teaching you to recognize patterns and apply the right algorithms.

Explanation

Here’s a detailed explanation of the code:

Line 2: We sort the input array nums in ascending order to simplify the process of finding the closest sum.
Line 3: We initialize the variable res to the sum of the first three numbers in the sorted array. This provides an initial approximation for the closest sum.
Line 4-7: We iterate through the array elements using a loop. For each element nums[i], initialize two pointers start and end to find the remaining two numbers in the triplet.
Line 9–15: Inside the nested while loop, we calculate the sum of the current triplet (current_sum = nums[i] + nums[start] + nums[end]). Adjust the pointers start and end based on the comparison of current_sum with the target value. Update res if the absolute difference between current_sum and the target is less than the absolute difference between res and the target.
Line 16: After iterating through all possible triplets, we return the closest sum found stored in the variable res.
Line 20–22: We define the example input array numbers and target value target. Then call the threeSumClosest function with the provided input array and target value, and print the result, which is the closest sum of three integers in the array to the target value.

Time complexity

Sorting the input array takes $O(n log n)$ time, where $n$ is the length of the input array.
The main loop iterates through each element of the array once, and for each element, it performs a two-pointer approach that takes $O(n)$ time in the worst case.
Within the loop, the two-pointer approach moves the start and end pointers toward each other until they meet, which takes $O(n)$ time in the worst case.
Overall, the time complexity is dominated by the sorting step and the main loop, resulting in $O(n log n) + O(n^2) = O(n^2)$ time complexity.

Space complexity

The space complexity is primarily determined by the space used for storing the sorted array, which requires $O(n)$ additional space.
Other variables, such as res, start, end, and current_sum require constant space, regardless of the size of the input array.
Therefore, the space complexity is $O(n)$ due to the sorted array.

Free Resources

3Sum Closest LeetCode

Problem statement

Explanation

Examples

Knowledge test

Algorithm to solve 3Sum Closest problem

Code

Explanation

Time complexity

Space complexity