3Sum Closest Solution

Problem

Given an array of integers and a target value, find any three numbers in the array whose sum is closest to the target and return that sum. You are guaranteed exactly one answer exists.

Input: nums = [-1, 2, 1, -4], target = 1
Output: 2
Explanation: The triplet [-1, 2, 1] sums to 2, which is closer to 1 than any other triplet (e.g. [-1, -4, 2] sums to -3, which is 4 away).

Intuition

Once the array is sorted, you can fix one element and use two pointers converging from both ends of the remaining subarray. When the current sum is too small, advancing the left pointer increases it; when it's too large, retreating the right pointer decreases it. This lets you scan all meaningful triplets for a fixed outer element in O(n) instead of O(n²), turning an O(n³) search into O(n²).

Approach 1 — Brute Force

Try every possible triplet and track the one whose sum is closest to the target.

Initialize closest_sum to the sum of the first three elements.
Use three nested loops over all distinct triples (i, j, k) with i < j < k.
If |current_sum - target| is smaller than |closest_sum - target|, update closest_sum.
Return closest_sum.

1def threeSumClosest(nums: list[int], target: int) -> int:
2    n = len(nums)
3    closest_sum = nums[0] + nums[1] + nums[2]
4
5    for i in range(n - 2):
6        for j in range(i + 1, n - 1):
7            for k in range(j + 1, n):
8                current_sum = nums[i] + nums[j] + nums[k]
9                if abs(current_sum - target) < abs(closest_sum - target):
10                    closest_sum = current_sum
11
12    return closest_sum

Time: O(n³) — three nested loops examine every distinct triplet. Space: O(1) — only a constant number of variables are used.

Approach 2 — Sort + Two Pointers

Sort the array, then fix each element as the first of the triplet and use two pointers on the remaining subarray. The sorted order guarantees that moving left right increases the sum and moving right left decreases it.

Sort nums.
Initialize closest_sum to the sum of the first three elements.
For each index i from 0 to n-3, set left = i+1 and right = n-1.
While left < right, compute current_sum = nums[i] + nums[left] + nums[right].
- If current_sum == target, return immediately — no triplet can be any closer.
- If |current_sum - target| < |closest_sum - target|, update closest_sum.
- If current_sum < target, increment left; otherwise decrement right.
Return closest_sum.

1def threeSumClosest(nums: list[int], target: int) -> int:
2    nums.sort()
3    n = len(nums)
4    closest_sum = nums[0] + nums[1] + nums[2]
5
6    for i in range(n - 2):
7        left, right = i + 1, n - 1
8
9        while left < right:
10            current_sum = nums[i] + nums[left] + nums[right]
11
12            if current_sum == target:
13                return current_sum  # exact match — nothing can be closer
14
15            if abs(current_sum - target) < abs(closest_sum - target):
16                closest_sum = current_sum
17
18            if current_sum < target:
19                left += 1   # sum too small, advance left to increase it
20            else:
21                right -= 1  # sum too large, retreat right to decrease it
22
23    return closest_sum

Time: O(n²) — sorting takes O(n log n); the two-pointer scan is O(n) per outer element over n elements. Space: O(log n) — the in-place sort uses O(log n) stack space.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n³)	O(1)	Only for tiny arrays (n < 20) where code simplicity matters more than speed
Sort + Two Pointers	O(n²)	O(log n)	All practical inputs; the standard interview solution

Common Mistakes

Forgetting to sort before using two pointers — the rule "advance left to increase the sum" only holds when the array is sorted; on an unsorted array, any pointer move can change the sum in either direction unpredictably.
Returning the minimum difference instead of the actual sum — the problem asks for the closest sum value (e.g., 2), not how far it is from the target (e.g., 1).
Initializing closest_sum to 0 or infinity — the initial value must be an actual triplet sum (e.g., the first three elements after sorting) so that the first distance comparison is meaningful; 0 can incorrectly dominate if the true closest sum is far from zero.
Using i < j < k with indices all starting at 0 — the brute-force loops must enforce strict ordering; starting all three at 0 and adding != guards is error-prone; nested range bounds range(i+1, n-1) and range(j+1, n) are cleaner.
Not short-circuiting on exact match — skipping the early return when sum == target is not wrong, but it misses an easy optimization and signals a shallow understanding of the algorithm.

3Sum Closest — Solution