0016. 3Sum Closest¶

Table of Contents¶

1. Problem
2. Problem Breakdown
3. Approach 1: Brute Force
4. Approach 2: Sort + Two Pointers
5. Complexity Comparison
6. Edge Cases
7. Common Mistakes
8. Related Problems
9. Visual Animation

Problem¶

Description¶

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Examples¶

Example 1:
Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: 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
Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

Example 3:
Input: nums = [1,1,1,0], target = 3
Output: 3
Explanation: The sum that equals the target is 3. (1 + 1 + 1 = 3).

Constraints¶

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

Problem Breakdown¶

1. What is being asked?¶

Given an array of integers and a target value, find the triplet whose sum is closest to the target. Unlike 3Sum (which finds exact matches equaling zero), here we need the minimum distance between any triplet sum and the target. Return the actual sum, not the distance.

2. What is the input?¶

Important observations about the input: - The array is not sorted - Elements can be negative, zero, or positive - The array always has at least 3 elements - Exactly one solution is guaranteed (no ties)

3. What is the output?¶

• A single integer — the sum of the three integers closest to target
• The closeness is measured by |sum - target|

4. Constraints analysis¶

5. Step-by-step example analysis¶

Example 1: nums = [-1, 2, 1, -4], target = 1¶

All possible triplets:
  (-1, 2, 1)  = 2   → |2 - 1| = 1
  (-1, 2, -4) = -3  → |-3 - 1| = 4
  (-1, 1, -4) = -4  → |-4 - 1| = 5
  (2, 1, -4)  = -1  → |-1 - 1| = 2

Closest sum: 2 (distance = 1)
Result: 2

Example 2: nums = [0, 0, 0], target = 1¶

Only one triplet:
  (0, 0, 0) = 0  → |0 - 1| = 1

Closest sum: 0
Result: 0

Example 3: nums = [1, 1, 1, 0], target = 3¶

All possible triplets:
  (1, 1, 1) = 3  → |3 - 3| = 0  ← exact match!
  (1, 1, 0) = 2  → |2 - 3| = 1
  (1, 1, 0) = 2  → |2 - 3| = 1
  (1, 1, 0) = 2  → |2 - 3| = 1

Closest sum: 3 (exact match)
Result: 3

6. Key Observations¶

1. Distance metric — We minimize |sum - target|, where sum = nums[i] + nums[j] + nums[k].
2. Sorting helps — After sorting, we can use two pointers to efficiently search for the closest sum. If the current sum is too small, move the left pointer right; if too large, move the right pointer left.
3. Early termination — If we find an exact match (sum == target), we can return immediately since distance is 0.
4. Relationship to 3Sum — This is a generalization of 3Sum. Instead of checking sum == 0, we track the minimum |sum - target|.

7. Pattern identification¶

Chosen pattern: Sort + Two Pointers Reason: Sorting the array allows us to use two pointers that move directionally based on whether the current sum is above or below the target. This reduces the inner search from O(n^2) to O(n), giving an overall O(n^2) solution.

Approach 1: Brute Force¶

Thought process¶

The simplest idea: check every possible triplet and track which sum is closest to the target. Using three nested loops, compute the sum for all C(n,3) triplets. Track the closest sum found.

Algorithm (step-by-step)¶

1. Initialize closest = nums[0] + nums[1] + nums[2]
2. Outer loop: i = 0 to n-3
3. Middle loop: j = i+1 to n-2
4. Inner loop: k = j+1 to n-1
5. Calculate sum = nums[i] + nums[j] + nums[k]
6. If |sum - target| < |closest - target|, update closest = sum
7. Return closest

Pseudocode¶

function threeSumClosest(nums, target):
    closest = nums[0] + nums[1] + nums[2]
    for i = 0 to n-3:
        for j = i+1 to n-2:
            for k = j+1 to n-1:
                sum = nums[i] + nums[j] + nums[k]
                if |sum - target| < |closest - target|:
                    closest = sum
    return closest

Complexity¶

Implementation¶

Go¶

// threeSumClosestBruteForce — Brute Force approach
// Time: O(n^3), Space: O(1)
func threeSumClosestBruteForce(nums []int, target int) int {
    n := len(nums)
    closest := nums[0] + nums[1] + nums[2]

    for i := 0; i < n-2; i++ {
        for j := i + 1; j < n-1; j++ {
            for k := j + 1; k < n; k++ {
                sum := nums[i] + nums[j] + nums[k]
                if abs(sum-target) < abs(closest-target) {
                    closest = sum
                }
            }
        }
    }

    return closest
}

Java¶

class Solution {
    // threeSumClosest — Brute Force approach
    // Time: O(n^3), Space: O(1)
    public int threeSumClosest(int[] nums, int target) {
        int n = nums.length;
        int closest = nums[0] + nums[1] + nums[2];

        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    int sum = nums[i] + nums[j] + nums[k];
                    if (Math.abs(sum - target) < Math.abs(closest - target)) {
                        closest = sum;
                    }
                }
            }
        }

        return closest;
    }
}

Python¶

class Solution:
    def threeSumClosest(self, nums: list[int], target: int) -> int:
        """
        Brute Force approach
        Time: O(n^3), Space: O(1)
        """
        n = len(nums)
        closest = nums[0] + nums[1] + nums[2]

        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                for k in range(j + 1, n):
                    current_sum = nums[i] + nums[j] + nums[k]
                    if abs(current_sum - target) < abs(closest - target):
                        closest = current_sum

        return closest

Dry Run¶

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

Initial: closest = -1 + 2 + 1 = 2

i=0 (-1):
  j=1 (2):
    k=2 (1):  sum = -1+2+1 = 2   |2-1|=1  < |2-1|=1  → no change
    k=3 (-4): sum = -1+2-4 = -3  |-3-1|=4 > 1         → no change
  j=2 (1):
    k=3 (-4): sum = -1+1-4 = -4  |-4-1|=5 > 1         → no change

i=1 (2):
  j=2 (1):
    k=3 (-4): sum = 2+1-4 = -1   |-1-1|=2 > 1         → no change

Total triplets checked: 4 (C(4,3) = 4)
Result: 2

Approach 2: Sort + Two Pointers¶

The problem with Brute Force¶

Brute Force checks all C(n,3) triplets — that's O(n^3). With n = 500, that's ~20 million operations — it might pass, but is slow. Question: "Can we reduce the search space using sorting?"

Optimization idea¶

Sort the array first. Then for each fixed element nums[i], use two pointers left and right to find the best pair.

Since the array is sorted: - If sum < target, moving left right increases the sum - If sum > target, moving right left decreases the sum - If sum == target, we found an exact match and return immediately

This way, for each i, we scan the remaining elements in O(n) instead of O(n^2).

Algorithm (step-by-step)¶

1. Sort the array
2. Initialize closest = nums[0] + nums[1] + nums[2]
3. For each i from 0 to n-3: a. Skip if nums[i] == nums[i-1] (optional optimization) b. Set left = i+1, right = n-1 c. While left < right:
   • Calculate sum = nums[i] + nums[left] + nums[right]
   • If sum == target, return target
   • If |sum - target| < |closest - target|, update closest = sum
   • If sum < target, move left++
   • Else move right--
4. Return closest

Pseudocode¶

function threeSumClosest(nums, target):
    sort(nums)
    closest = nums[0] + nums[1] + nums[2]

    for i = 0 to n-3:
        if i > 0 and nums[i] == nums[i-1]: continue
        left = i + 1, right = n - 1

        while left < right:
            sum = nums[i] + nums[left] + nums[right]
            if sum == target: return target
            if |sum - target| < |closest - target|:
                closest = sum
            if sum < target: left++
            else: right--

    return closest

Complexity¶

Implementation¶

Go¶

// threeSumClosest — Sort + Two Pointers approach
// Time: O(n^2), Space: O(log n)
func threeSumClosest(nums []int, target int) int {
    sort.Ints(nums)
    n := len(nums)
    closest := nums[0] + nums[1] + nums[2]

    for i := 0; i < n-2; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }

        left, right := i+1, n-1

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

            if sum == target {
                return target
            }

            if abs(sum-target) < abs(closest-target) {
                closest = sum
            }

            if sum < target {
                left++
            } else {
                right--
            }
        }
    }

    return closest
}

Java¶

class Solution {
    // threeSumClosest — Sort + Two Pointers approach
    // Time: O(n^2), Space: O(log n)
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        int closest = nums[0] + nums[1] + nums[2];

        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int left = i + 1, right = n - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum == target) return target;

                if (Math.abs(sum - target) < Math.abs(closest - target)) {
                    closest = sum;
                }

                if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        return closest;
    }
}

Python¶

class Solution:
    def threeSumClosest(self, nums: list[int], target: int) -> int:
        """
        Sort + Two Pointers approach
        Time: O(n^2), Space: O(log n)
        """
        nums.sort()
        n = len(nums)
        closest = nums[0] + nums[1] + nums[2]

        for i in range(n - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            left, right = i + 1, n - 1

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

                if current_sum == target:
                    return target

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

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

        return closest

Dry Run¶

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

Step 0: Sort → [-4, -1, 1, 2]
        closest = -4 + (-1) + 1 = -4

i=0 (nums[i]=-4), left=1, right=3:
  Step 1: sum = -4 + (-1) + 2 = -3   |-3-1|=4 < |-4-1|=5 → closest = -3
          sum < target → left++ → left=2

  Step 2: sum = -4 + 1 + 2 = -1      |-1-1|=2 < |-3-1|=4 → closest = -1
          sum < target → left++ → left=3

  left == right → inner loop ends

i=1 (nums[i]=-1), left=2, right=3:
  Step 3: sum = -1 + 1 + 2 = 2       |2-1|=1 < |-1-1|=2 → closest = 2
          sum > target → right-- → right=2

  left == right → inner loop ends

i=2 → i >= n-2, outer loop ends

Total operations: 3 inner steps (vs Brute Force: 4 triplets)
Result: 2

Complexity Comparison¶

Which solution to choose?¶

• In an interview: Approach 2 (Sort + Two Pointers) — demonstrates knowledge of sorting + two-pointer pattern
• In production: Approach 2 — optimal time complexity
• On Leetcode: Approach 2 — O(n^2) comfortably passes for n=500
• For learning: Both — Brute Force to understand the problem, Sort + Two Pointers to learn the optimization

Edge Cases¶

Common Mistakes¶

Mistake 1: Forgetting to sort the array before using two pointers¶

# WRONG — two pointers on unsorted array gives incorrect results
def threeSumClosest(self, nums, target):
    closest = nums[0] + nums[1] + nums[2]
    for i in range(len(nums) - 2):
        left, right = i + 1, len(nums) - 1
        while left < right:
            # Two pointers logic won't work on unsorted array!
            ...

# CORRECT — sort first
def threeSumClosest(self, nums, target):
    nums.sort()  # Essential!
    ...

Reason: The two-pointer technique relies on the sorted order to decide which pointer to move. Without sorting, moving left or right has no predictable effect on the sum.

Mistake 2: Using wrong distance comparison¶

# WRONG — comparing sums instead of distances
if current_sum < closest:
    closest = current_sum

# CORRECT — compare absolute distances to target
if abs(current_sum - target) < abs(closest - target):
    closest = current_sum

Reason: A smaller sum is not necessarily closer to the target. For example, if target=5, sum=3 (distance=2) is closer than sum=1 (distance=4), even though 1 < 3.

Mistake 3: Not returning early on exact match¶

# INEFFICIENT — continues searching even after finding exact match
if abs(current_sum - target) < abs(closest - target):
    closest = current_sum

# BETTER — return immediately when exact match found
if current_sum == target:
    return target
if abs(current_sum - target) < abs(closest - target):
    closest = current_sum

Reason: If the sum equals the target, the distance is 0 and we cannot do better. Returning early avoids unnecessary iterations.

Related Problems¶

Visual Animation¶

Interactive animation: animation.html

In the animation: - Brute Force tab — three nested loops (i, j, k) check all triplets - Sort + Two Pointers tab — fix i, move left and right pointers - Array visualization with sorting step - Distance-to-target display and best sum tracking - Custom input controls for experimenting with different arrays and targets