MediumArrayTwo PointersSorting

3Sum Closest

1 approach, code in every language

You are given an integer array and a target value. Pick exactly three elements from three different positions so that their sum lands as near to the target as possible.

Return that closest achievable sum. The inputs are chosen so that exactly one closest sum exists.

Example 1

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

Output: 2

The triplet (-1, 2, 1) totals 2, which is the nearest value to the target of 1.

Example 2

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

Output: 0

The only triplet sums to 0, so that becomes the closest reachable total.

Constraints

3 ≤ nums.length ≤ 5 * 10^2
-10^3 ≤ nums[i] ≤ 10^3
-10^4 ≤ target ≤ 10^4

Sort + Two Pointers

Sort the array, fix one element, and slide two pointers inward while tracking the sum with the smallest distance to the target.

Loading animation…

Intuition

After sorting, fixing the first element lets the two remaining pointers respond to feedback: when the current sum is below the target we shift the left pointer up to raise it, and when it is above we shift the right pointer down to lower it. Along the way we compare the absolute gap between each sum and the target, remembering whichever total sits closest. If a sum ever equals the target exactly, no closer value can exist, so we can stop immediately.

Algorithm walkthrough

1Sort the array so pointer moves change the sum in a predictable direction.
2Initialize the best answer with the first three elements' sum.
3For each fixed index i, place left just after i and right at the end.
4Update the best answer whenever the current three-way sum is nearer to the target than the stored one.
5Move left up if the sum is below target, right down if above, and return early on an exact match.

Implementation

from typing import List

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        closest = nums[0] + nums[1] + nums[2]
        for i in range(n - 2):
            left, right = i + 1, n - 1
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                if abs(total - target) < abs(closest - target):
                    closest = total
                if total < target:
                    left += 1
                elif total > target:
                    right -= 1
                else:
                    return total
        return closest

Time

O(n^2)

Space

O(1)

Sorting is O(n log n); the fixed-element loop with a two-pointer sweep is O(n^2) overall.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Arrays

After the pattern

Now solve one you haven't seen.

Three-Weight Ballast Trim is our own problem on the technique behind 3Sum Closest: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free