15% off all plans & roadmaps Use code

See plans

3Sum Closest

Updated

TL;DR: Sort the array, fix the first number of the triple, then move two pointers inward over the rest. Each move discards candidates that cannot beat the current best, which brings the search down to O(n^2).

Problem

Given an integer array nums of length n and an integer target, find three integers in nums whose sum is as close as possible to target.

Return the sum of those three integers.

You may assume that each input has exactly one solution.

Example 1

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum closest to the target is 2. (-1 + 2 + 1 = 2).

Example 2

Input: nums = [0,0,0], target = 1
Output: 0
Explanation: The sum closest to the target is 0. (0 + 0 + 0 = 0).

Constraints

  • 3 <= nums.length <= 500
  • -1000 <= nums[i] <= 1000
  • -10^4 <= target <= 10^4

Constraints that matter

  • n up to 500 means there are about 2 * 10^7 triples (500 choose 3 is 20,708,500). Checking every triple is too slow to be the intended answer, so the solution must skip most of them.
  • Values stay between -1000 and 1000, so any triple sum lies between -3000 and 3000. Plain 32-bit integers hold every sum with room to spare, and overflow is not a concern.
  • n is at least 3, so the first three values always form a valid triple. You can seed the best answer with that sum instead of an arbitrary number.
  • Because the answer is a sum and not indices, the order of the array does not matter. Sorting is allowed, and it does not change the answer.

View on LeetCode

Hints

Hint 1

The problem asks for a triple whose sum lands near a target.

Hint 2

Try every triple of distinct positions.

Solution

Intuition

The problem asks for a triple whose sum lands near a target. Checking all triples costs cubic time. The useful observation is that the answer depends only on the values, not on their positions. You can sort the array without losing any candidate.

Picture bags sorted by weight on a shelf, with one hand on the lightest bag and one on the heaviest. The hands are the left and right pointers, and each move discards a bag that cannot bring the total closer.

After sorting, fix the first number nums[i]. The rest of the problem becomes a pair search: find two later numbers whose sum is closest to target - nums[i]. A converging Two Pointers scan solves that pair search in linear time, because the sorted order tells you which pointer to move.

Recognise this pattern by its shape. You see a sorted array, a target sum, and a question about a fixed-size group of values. Sorting followed by converging pointers is the standard answer for 3Sum, 3Sum Closest and Two Sum II.

Watch the pattern animation

Worked example

Input: nums = [-1, 2, 1, -4], target = 1
Output: 2
Explanation: Four triples exist. Their sums are 2, -3, -4 and -1. The sum 2 is 1 away from the target, and no other triple is that close, so 2 is the answer.

Approach 1: Brute force

Try every triple of distinct positions. For each triple, compute its sum and keep the sum whose distance to the target is smallest. The loops never use the sorted order, so every triple gets checked, and most of the work lands far from the target.

Steps

  1. Set best to the sum of the first three numbers.
  2. Loop i from 0 to n - 1.
  3. Inside that, loop j from i + 1 to n - 1.
  4. Inside that, loop k from j + 1 to n - 1.
  5. Compare the distance |target - sum| with the best distance. Keep the sum that is closer.
  6. Return best.

Dry run

Start with best = -1 + 2 + 1 = 2, which is distance 1 from the target.

Triple (indices)ValuesSumDistanceBest after
(0, 1, 2)-1, 2, 1212
(0, 1, 3)-1, 2, -4-342
(0, 2, 3)-1, 1, -4-452
(1, 2, 3)2, 1, -4-122

No later triple gets closer than distance 1, so the trace ends at 2.

Complexity

TimeO(n^3)
SpaceO(1)

Let n be the length of nums. The loops pick i < j < k, which gives n(n-1)(n-2)/6 triples, so the work is proportional to n^3. Each triple does constant work: one sum, two absolute values and one comparison. The code stores only best and the three indices, so the extra space is O(1).

PythonTested in our runner

from typing import List, Optional

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        n = len(nums)
        best = nums[0] + nums[1] + nums[2]
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    s = nums[i] + nums[j] + nums[k]
                    if abs(target - s) < abs(target - best):
                        best = s
        return best

The Converging (Sorted Array Target Sum) infographic is part of Pro

A one-page visual of the pattern: when it applies, the steps and the invariant to keep.

Unlock the infographic

Solution pattern

Converging (Sorted Array Target Sum)

Part of Two Pointers

Approach 2: Sort, then converging two pointersOptimalConverging (Sorted Array Target Sum)

What's slow: the brute force checks about n^3 / 6 triples, and nearly all of them are far from the target. It never uses the fact that nearby values are grouped together after sorting.

The insight that fixes it: after sorting, fix i and search the pairs to its right with left at i + 1 and right at the last index. If the sum is below the target, any pair using the same left with a smaller right has an even smaller sum, so left must move right. If the sum is above the target, any pair using the same right with a larger left has an even larger sum, so right must move left.

Each move throws away one index that cannot beat the current best. That means each first number needs only a linear scan, and the whole search takes O(n^2) after the sort.

Steps

  1. Sort nums in ascending order.
  2. Seed best with the sum of the first three sorted values.
  3. Loop i from 0 to n - 3.
  4. Set left to i + 1 and right to n - 1.
  5. While left < right, compute the sum. Keep it if its distance to the target is smaller than the best distance.
  6. If the sum equals the target, return it. If the sum is below the target, move left right. Otherwise move right left.
  7. After all values of i are checked, return best.

Dry run

The array sorts to [-4, -1, 1, 2]. The table tracks the state after each step. Distance means |target - sum| with target = 1.

StepileftrightSumDistanceBestAction
0sort, seed-----4Array is [-4, -1, 1, 2]
1013-34-3Sum is below 1, move left right
2023-12-1Sum is below 1, move left right
3033---1Left equals right, next i
4123212Sum is above 1, move right left
5122--2Left equals right, loop ends

The loop ends with best = 2, which matches the expected output.

Complexity

TimeO(n^2)
SpaceO(1) beyond the sort

Let n be the length of nums. Sorting costs O(n log n), and the outer loop runs about n - 2 times. For a fixed i, left and right only move toward each other, so they take at most n - i - 1 steps in total. Summing over all i gives about n^2 / 2 steps, so the scan is O(n^2), and the whole algorithm is O(n^2) because n^2 dominates n log n. Extra space is constant for the pointers and best, plus whatever stack or buffer the sort uses.

PythonTested in our runner

from typing import List, Optional

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        arr = sorted(nums)  # copy, so the caller's list is untouched
        n = len(arr)
        best = arr[0] + arr[1] + arr[2]
        for i in range(n - 2):
            left, right = i + 1, n - 1
            while left < right:
                s = arr[i] + arr[left] + arr[right]
                if abs(target - s) < abs(target - best):
                    best = s
                if s == target:
                    return s
                if s < target:
                    left += 1
                else:
                    right -= 1
        return best

Common mistakes

  • Comparing raw sums with if s < best instead of distances. The result can sit far from the target. Compare abs(target - s) with abs(target - best).
  • Seeding best = 0 with a fixed value. For [1, 1, 1] and target 100 the answer is 3, and 0 is never a reachable sum. Seed best with the sum of a real triple, such as the first three values.
  • Writing right = n instead of right = n - 1. The first read of nums[right] falls off the end of the array. Keep right on the last valid index.
  • Moving the wrong pointer, as in if s < target: right -= 1. A sum below the target needs a larger value, so left moves right. Moving right left only lowers the sum further.
  • Reusing indices in the brute force loops, such as for j in range(n) inside the loop over i. That counts one element twice. Start j at i + 1 and k at j + 1.
  • Skipping the sort, or sorting after the pointer loop starts. The pointer moves depend on sorted order, so the scan can miss the closest triple.

Edge cases

  • Array of length 3, such as [5, 9, 1] with target 0. There is only one triple, so the answer is its sum, 15, whatever the target.
  • All values equal, such as [0, 0, 0] with target 1. Every triple sums to 0, so the answer is 0.
  • Target below every possible sum, such as [1, 2, 3, 4] with target -100. The closest sum is the smallest triple, 1 + 2 + 3 = 6.
  • Target above every possible sum, such as [1, 2, 3, 4] with target 100. The closest sum is the largest triple, 2 + 3 + 4 = 9.
  • Exact match early in the scan, such as [-1, 2, 1, -4] with target 2. The triple (-1, 2, 1) sums to 2, so the algorithm returns 2 as soon as it finds it.
  • Duplicates with negatives, such as [-1, -1, -1, 2] with target 0. The triples sum to -3 and 0, so the answer is 0. Duplicate values need no special handling here.

Follow-ups interviewers ask

What if the array is already sorted?
Skip the sort, which saves O(n log n) work. The pointer scan still costs O(n^2), so the overall bound stays the same and only the constant factor changes. The brute force cannot use the sorted order in the same way, so it stays O(n^3).
Can you do it in O(1) extra space?
The pointers and best already use O(1) extra space. The sort is the part that matters. Heapsort sorts in place with O(1) extra space, but it is slower in practice. Python's sort and Java's object sorts use O(n) buffer space in the worst case, and Java's primitive sort uses O(log n) stack space.
What if the array does not fit in memory?
Sort the data with an external merge sort, which writes a sorted file in chunks and merges them. Each value of i then needs one pass that reads from both ends of the sorted file with two cursors. The work becomes I/O bound, with about n sequential passes, so read the file in large buffered blocks to keep the passes cheap.

3Sum Closest FAQ

What is the time complexity of 3Sum Closest?

The sorted two pointer solution runs in O(n^2) time, where n is the array length. The sort costs O(n log n), and the scan over all first numbers costs O(n^2) in total. The brute force triple loop is O(n^3).

Why use two pointers for 3Sum Closest?

Sorting makes the pair search monotone. When the sum is below the target, the current right cannot help with this left, so left moves right. Each move discards one candidate, which lets every first number finish in linear time.

Can 3Sum Closest be solved in O(1) extra space?

Partly. The pointers and the best sum use O(1) extra space, but the sort may not. Heapsort keeps the sort at O(1) extra space, while typical library sorts use O(log n) or O(n) extra space. If the space bound is strict, use heapsort.

Is 3Sum Closest the same as 3Sum?

No. 3Sum looks for triples that sum to exactly zero and must skip duplicate triples in the output. 3Sum Closest looks for the single sum nearest a target, so it needs no duplicate handling.

Does Python's sort change the input list in 3Sum Closest?

Yes, nums.sort() sorts the caller's list in place. sorted(nums) returns a new list and leaves the input alone. Both give the same answer, but use sorted if the caller reuses the list.

Asked at

See which companies ask this — Pro

Practise it