LeetCode 16 - 3Sum Closest

The problem gives us an integer array nums and a target integer target. We must select exactly three elements from the array, using distinct indices, and compute their sum. Among all possible three-number sums, we want the one whose value is closest to the target.

leetcodemediumarraytwo-pointerssorting

LeetCode Problem 16

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Sorting

Solution

Problem Understanding

The problem gives us an integer array nums and a target integer target. We must select exactly three elements from the array, using distinct indices, and compute their sum. Among all possible three-number sums, we want the one whose value is closest to the target.

The important detail is that we are not trying to find a sum that exactly equals the target, although that may happen. Instead, we minimize the absolute difference:

$$|(\text{sum of three numbers}) - \text{target}|$$

The function should return the actual sum, not the indices and not the difference.

For example, if nums = [-1,2,1,-4] and target = 1, the possible three-number sums are:

  • -1 + 2 + 1 = 2
  • -1 + 2 + (-4) = -3
  • -1 + 1 + (-4) = -4
  • 2 + 1 + (-4) = -1

The value 2 is closest to 1, since:

$$|2 - 1| = 1$$

which is smaller than the differences for all other sums.

The constraints are important because they guide the algorithm choice:

  • 3 <= nums.length <= 500
  • Each value is between -1000 and 1000

An array size of 500 is large enough that a cubic brute-force solution may still pass in some languages, but it is inefficient and not ideal. Since this is a medium difficulty problem focused on arrays, sorting, and two pointers, we should expect a more optimized solution.

There are several edge cases worth considering immediately:

  • Arrays containing all identical values, such as [0,0,0]
  • Arrays containing many negative numbers
  • Arrays containing many positive numbers
  • Situations where the exact target can be achieved
  • Situations where multiple sums are equally close, although the problem guarantees exactly one valid answer
  • Smallest possible array size, which is exactly 3 elements

The problem guarantees that one solution always exists, so we never need to handle an impossible case.

Approaches

Brute Force Approach

The most direct solution is to examine every possible combination of three distinct indices.

We can use three nested loops:

  • The first loop selects the first number
  • The second loop selects the second number
  • The third loop selects the third number

For every triplet, we compute the sum and compare its distance from the target against the best result seen so far.

This approach is correct because it exhaustively checks every valid combination. Since every possible triplet is evaluated, the closest sum cannot be missed.

However, the time complexity is very expensive. With three nested loops, the complexity becomes:

$$O(n^3)$$

If n = 500, then:

$$500^3 = 125,000,000$$

That is far more work than necessary.

Optimal Approach, Sorting + Two Pointers

The key observation is that once the array is sorted, we can efficiently adjust sums using the two-pointer technique.

Suppose we fix one number at index i. Then we need to find two additional numbers whose sum gets us as close as possible to the target.

After sorting:

  • If the current sum is too small, we can move the left pointer rightward to increase the sum
  • If the current sum is too large, we can move the right pointer leftward to decrease the sum

Because the array is sorted, pointer movements become meaningful and deterministic.

Instead of checking every triplet independently, we intelligently eliminate large portions of the search space.

This reduces the complexity from:

$$O(n^3)$$

to:

$$O(n^2)$$

which is much more efficient.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(1) Checks every possible triplet
Optimal O(n²) O(1) or O(log n) depending on sorting Uses sorting and two pointers to reduce search space

Algorithm Walkthrough

  1. Sort the array in ascending order.

Sorting is essential because the two-pointer technique relies on ordered values. Once sorted, moving pointers left or right predictably changes the sum. 2. Initialize the closest sum.

A common strategy is to use the sum of the first three elements as the initial answer. This guarantees we start with a valid triplet. 3. Iterate through the array with index i.

At each position, nums[i] becomes the fixed first element of the triplet. 4. Set two pointers.

For each fixed index:

  • left = i + 1
  • right = len(nums) - 1

These pointers search for the best remaining pair. 5. Compute the current sum.

At every step:

$$\text{currentSum} = nums[i] + nums[left] + nums[right]$$ 6. Update the closest answer if needed.

Compare:

$$|\text{currentSum} - target|$$

against:

$$|\text{closestSum} - target|$$

If the current sum is closer, replace the stored answer. 7. Decide how to move pointers.

  • If currentSum < target, the sum is too small, so move left rightward to increase it.
  • If currentSum > target, the sum is too large, so move right leftward to decrease it.
  • If currentSum == target, we found the best possible answer and can immediately return it.
  1. Continue until pointers cross.

Once left >= right, all pairs for the current fixed element have been explored. 9. Return the closest sum.

Why It Works

The correctness relies on the sorted order of the array.

For a fixed first element:

  • Moving the left pointer right increases the sum
  • Moving the right pointer left decreases the sum

This guarantees that every relevant candidate pair is explored in a structured way without missing any potentially better result. Since we repeat this process for every possible first element, the globally closest triplet sum is guaranteed to be found.

Python Solution

from typing import List

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()

        closest_sum = nums[0] + nums[1] + nums[2]

        for i in range(len(nums) - 2):
            left = i + 1
            right = len(nums) - 1

            while left < right:
                current_sum = nums[i] + nums[left] + nums[right]

                if abs(current_sum - target) < abs(closest_sum - target):
                    closest_sum = current_sum

                if current_sum < target:
                    left += 1
                elif current_sum > target:
                    right -= 1
                else:
                    return current_sum

        return closest_sum

The implementation begins by sorting the array. This enables the two-pointer strategy because increasing or decreasing pointer positions now predictably affects the sum.

The variable closest_sum stores the best answer found so far. Initializing it with the first three numbers guarantees a valid starting value.

The outer loop fixes one element at index i. For each fixed value, the algorithm searches for the best pair using two pointers.

Inside the while left < right loop, the current triplet sum is calculated. If this sum is closer to the target than the previous best result, we update closest_sum.

The pointer movement logic is the core optimization:

  • If the sum is too small, move left rightward
  • If the sum is too large, move right leftward
  • If the sum equals the target exactly, return immediately

This process systematically explores all useful combinations in quadratic time.

Go Solution

package main

import (
	"math"
	"sort"
)

func threeSumClosest(nums []int, target int) int {
	sort.Ints(nums)

	closestSum := nums[0] + nums[1] + nums[2]

	for i := 0; i < len(nums)-2; i++ {
		left := i + 1
		right := len(nums) - 1

		for left < right {
			currentSum := nums[i] + nums[left] + nums[right]

			if math.Abs(float64(currentSum-target)) <
				math.Abs(float64(closestSum-target)) {
				closestSum = currentSum
			}

			if currentSum < target {
				left++
			} else if currentSum > target {
				right--
			} else {
				return currentSum
			}
		}
	}

	return closestSum
}

The Go implementation closely mirrors the Python version. The main differences are language-specific.

Go requires explicit sorting using sort.Ints(nums).

The math.Abs function operates on float64, so integer differences must be converted before comparison.

Slices in Go already behave similarly to dynamic arrays, so no special handling is needed for indexing.

Integer overflow is not a concern here because the constraints are small. The maximum possible sum magnitude is well within Go's integer range.

Worked Examples

Example 1

Input:

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

Step 1: Sort the Array

[-4, -1, 1, 2]

Initial Closest Sum

-4 + -1 + 1 = -4

So:

closest_sum = -4

Outer Loop, i = 0

Fixed value:

nums[i] = -4

Pointers:

left = 1
right = 3
i left right Triplet Current Sum Closest Sum
0 1 3 (-4, -1, 2) -3 -3

Difference from target:

|-3 - 1| = 4

Previous best:

|-4 - 1| = 5

Update:

closest_sum = -3

Current sum is less than target, so move left.

i left right Triplet Current Sum Closest Sum
0 2 3 (-4, 1, 2) -1 -1

Difference:

|-1 - 1| = 2

Update:

closest_sum = -1

Current sum is still less than target, move left.

Now left == right, stop.

Outer Loop, i = 1

Fixed value:

nums[i] = -1

Pointers:

left = 2
right = 3
i left right Triplet Current Sum Closest Sum
1 2 3 (-1, 1, 2) 2 2

Difference:

|2 - 1| = 1

Previous best:

|-1 - 1| = 2

Update:

closest_sum = 2

Current sum is greater than target, move right.

Pointers cross, loop ends.

Final answer:

2

Example 2

Input:

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

Sorted Array

[0,0,0]

Initial Closest Sum

0 + 0 + 0 = 0

Outer Loop

Only one possible triplet exists.

i left right Triplet Current Sum
0 1 2 (0,0,0) 0

Difference:

|0 - 1| = 1

No better triplet exists.

Final answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n²) Sorting costs O(n log n), then each index uses a linear two-pointer scan
Space O(1) or O(log n) Only a few variables are used, sorting implementation may use stack space

The dominant operation is the nested structure formed by the outer loop and the two-pointer scan. Although there is a loop inside another loop, the inner pointers move only linearly across the array for each fixed index, resulting in quadratic complexity overall.

The algorithm uses constant auxiliary memory aside from sorting overhead.

Test Cases

from typing import List

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()

        closest_sum = nums[0] + nums[1] + nums[2]

        for i in range(len(nums) - 2):
            left = i + 1
            right = len(nums) - 1

            while left < right:
                current_sum = nums[i] + nums[left] + nums[right]

                if abs(current_sum - target) < abs(closest_sum - target):
                    closest_sum = current_sum

                if current_sum < target:
                    left += 1
                elif current_sum > target:
                    right -= 1
                else:
                    return current_sum

        return closest_sum

solution = Solution()

assert solution.threeSumClosest([-1, 2, 1, -4], 1) == 2  # provided example
assert solution.threeSumClosest([0, 0, 0], 1) == 0  # all zeros
assert solution.threeSumClosest([1, 1, 1, 1], 3) == 3  # exact match exists
assert solution.threeSumClosest([-5, -2, -1, -10], -7) == -8  # all negatives
assert solution.threeSumClosest([5, 2, 7, 1], 10) == 10  # exact positive match
assert solution.threeSumClosest([1, 2, 4, 8, 16], 15) == 14  # closest below target
assert solution.threeSumClosest([-1, 0, 1, 1, 55], 3) == 2  # large outlier
assert solution.threeSumClosest([0, 1, 2], 3) == 3  # minimum array length
assert solution.threeSumClosest([-1000, -1000, 1000, 1000], 1) == 1000  # extreme values
assert solution.threeSumClosest([3, 0, -2, -1, 1, 2], 1) == 1  # exact achievable target

Test Summary

Test Why
[-1,2,1,-4], target=1 Validates the provided example
[0,0,0], target=1 Tests identical values
[1,1,1,1], target=3 Tests exact match behavior
[-5,-2,-1,-10], target=-7 Tests all negative numbers
[5,2,7,1], target=10 Tests exact positive combination
[1,2,4,8,16], target=15 Tests closest sum below target
[-1,0,1,1,55], target=3 Tests handling of outlier values
[0,1,2], target=3 Tests minimum valid array size
[-1000,-1000,1000,1000], target=1 Tests constraint extremes
[3,0,-2,-1,1,2], target=1 Tests mixed positive and negative values

Edge Cases

One important edge case is the minimum valid input size, where the array contains exactly three elements. In this situation, there is only one possible triplet, so the algorithm must immediately return that sum. Since the implementation initializes closest_sum using the first three elements and still correctly executes the loops, this case works naturally without requiring special handling.

Another important case involves arrays where all numbers are identical, such as [0,0,0]. Some implementations accidentally move pointers incorrectly or fail to update the answer properly when sums remain unchanged. Here, the algorithm correctly computes the only available sum and returns it.

A third critical edge case occurs when the exact target can be formed. Since no sum can be closer than an exact match, continuing the search would waste time. The implementation handles this efficiently by immediately returning when current_sum == target.

Arrays containing large positive and negative values are also important. These cases can expose bugs in pointer movement logic because the sum may swing dramatically as pointers move. Since the array is sorted and pointer adjustments are based entirely on whether the sum is too small or too large, the implementation remains correct regardless of value distribution.