#16

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

3Sum Closest

Find the sum of three integers in an array that is closest to a given target using two-pointer scanning.

Problem Statement

Given an integer array nums of length n and an integer target, find three integers in nums such that their sum is closest to the target. Return the sum of the three integers that is closest to the target value. It is guaranteed that exactly one solution exists.

You are allowed to modify the array, but you need to minimize the absolute difference between the sum of three numbers and the target. By using a sorted array and applying a two-pointer technique, you can achieve an optimal solution that finds the closest sum efficiently.

Examples

Example 1

Input: nums = [-1,2,1,-4], target = 1

Output: 2

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Example 2

Input: nums = [0,0,0], target = 1

Output: 0

The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

Constraints

3 <= nums.length <= 500
-1000 <= nums[i] <= 1000
-104 <= target <= 104

Solution Approach

Sort the Array

First, sort the given array to make it easier to apply the two-pointer technique. This helps you eliminate duplicates and efficiently find pairs that sum to a target value. Sorting will be O(n log n), which is the most time-consuming part of the approach.

Use Two-Pointer Scanning

For each element in the sorted array, treat it as the first element of a triplet and then use the two-pointer technique to find the other two elements. The pointers will scan through the remaining elements to find a sum that is as close as possible to the target, adjusting based on the sum.

Track Closest Sum

Track the closest sum during each iteration and update it whenever a closer sum is found. The absolute difference between the current sum and target is minimized during this process. Since each input has one solution, the closest sum is guaranteed to be found at the end.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution is O(n^2), where n is the length of the array. Sorting the array takes O(n log n), and for each element, we scan through the remaining elements using the two-pointer approach in linear time. The space complexity is O(1) because we use only a constant amount of extra space aside from the input array.

What Interviewers Usually Probe

Do you know how to handle cases where the array has both negative and positive numbers?
Can you explain the two-pointer strategy and how it minimizes the difference to the target?
Will you discuss the trade-offs between time complexity and the accuracy of finding the closest sum?

Common Pitfalls or Variants

Common pitfalls

Forgetting to sort the array first, which can lead to inefficient solutions or missed results.
Not properly managing pointer updates, potentially leading to incorrect triplets being selected.
Overlooking edge cases such as when all numbers in the array are equal or when the target is very far from all possible sums.

Follow-up variants

3Sum problem, where you find an exact target sum with three numbers.
4Sum Closest problem, where you find four integers that sum closest to a given target.
3Sum with Multiplicity, where you find the number of distinct triplets that sum to the target.

FAQ

What is the core technique to solve 3Sum Closest?

The core technique involves sorting the array and using the two-pointer method to efficiently find a triplet that is closest to the target sum.

How do you minimize the difference between the sum and target?

You use two pointers to scan through the array, adjusting based on whether the current sum is too low or too high compared to the target.

What is the time complexity of this problem?

The time complexity is O(n^2) due to the two-pointer scanning for each element in the array after sorting it in O(n log n) time.

Can you handle arrays with negative numbers efficiently?

Yes, by sorting the array and applying the two-pointer technique, you can efficiently handle both negative and positive numbers while finding the closest sum.

Is there a more efficient solution than O(n^2) for this problem?

Currently, O(n^2) is the best achievable time complexity for solving this problem, as each number needs to be checked in combination with others.

terminal

Solution

Solution 1: Sorting + Two Pointers

We sort the array first, then traverse the array. For each element $nums[i]$, we use pointers $j$ and $k$ to point to $i+1$ and $n-1$ respectively, calculate the sum of the three numbers. If the sum of the three numbers equals $target$, we directly return $target$. Otherwise, we update the answer based on the difference from $target$. If the sum of the three numbers is greater than $target$, we move $k$ one place to the left, otherwise, we move $j$ one place to the right.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        ans = inf
        for i, v in enumerate(nums):
            j, k = i + 1, n - 1
            while j < k:
                t = v + nums[j] + nums[k]
                if t == target:
                    return t
                if abs(t - target) < abs(ans - target):
                    ans = t
                if t > target:
                    k -= 1
                else:
                    j += 1
        return ans

Continue Practicing

#15 3sum #18 4sum #75 sort colors