3Sum Closest

Medium
132.

3Sum Closest

3Sum Closest is a medium coding problem on arrays, sorting and two pointers, asked in Dream11 interviews.

Given an integer array nums and an integer target, find three numbers in nums whose sum is closest to target and return that sum. Each input has exactly one closest sum.

Example 1

Input
nums = [-1,2,1,-4], target = 1
Output
2
Explanation
(-1 + 2 + 1) = 2.

Example 2

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

Constraints

  • 3 <= nums.length <= 12
  • -20 <= nums[i] <= 20
  • -60 <= target <= 60
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

3Sum Closest — Solution in Python, Java & C++

3Sum Closest solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Dream11.

3Sum Closest is a medium coding problem on arrays, sorting and two pointers, asked in Dream11 interviews.

  • Difficulty: Medium
  • Topics: Arrays, Sorting, Two Pointers
  • Asked at: Dream11
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an integer array nums and an integer target, find three numbers in nums whose sum is closest to target and return that sum. Each input has exactly one closest sum.

Example 1

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: (-1 + 2 + 1) = 2.

Example 2

Input: nums = [0,0,0], target = 1
Output: 0

Constraints

  • 3 <= nums.length <= 12
  • -20 <= nums[i] <= 20
  • -60 <= target <= 60

Hints for 3Sum Closest

  1. Hint 1

    Sort, fix one element, two-pointer the rest — like 3Sum but tracking the closest sum.

  2. Hint 2

    Early-exit when the sum hits the target exactly.

How to solve 3Sum Closest

The same sorted two-pointer machinery as 3Sum, but instead of demanding an exact hit you keep the best near-miss. Sorting is what lets a single comparison tell you which way to move: if the current sum is below the target, the only way to grow it is to raise the smaller element.

Approach

  1. Sort the array and seed best with any valid triplet sum, such as the first three values.
  2. Fix i, then sweep l = i + 1 and r = n - 1 towards each other.
  3. At each step compute the sum and update best if it is closer to the target than the current best.
  4. If the sum is below the target move l right; if above, move r left.
  5. An exact match cannot be beaten — return it immediately.

Why it works

For a fixed i, sliding the pointers explores the pair sums monotonically, so the comparison against the target always points towards the region that could improve the answer — the discarded side is uniformly further away in the wrong direction. Every candidate that could be the closest is therefore examined, and tracking a running minimum of |sum - target| picks it out.

Complexity

  • Time — O(n^2)
  • Space — O(n)

Pitfalls

  • Seed best with a real triplet sum, not 0 or a huge sentinel — comparing distances against an unreachable value can never improve.
  • Compare absolute distances to the target, not the raw sums.
  • No deduplication is needed or wanted here; skipping repeats could skip the closest sum.
  • Return the sum itself, not the distance.

Reference solution

Python

from typing import List

def threeSumClosest(nums: List[int], target: int) -> int:
    s = sorted(nums)
    best = s[0] + s[1] + s[2]
    for i in range(len(s) - 2):
        l, r = i + 1, len(s) - 1
        while l < r:
            total = s[i] + s[l] + s[r]
            if abs(total - target) < abs(best - target):
                best = total
            if total == target:
                return total
            if total < target:
                l += 1
            else:
                r -= 1
    return best

Java

public static int threeSumClosest(int[] nums, int target) {
    int[] s = nums.clone();
    Arrays.sort(s);
    int n = s.length;
    int best = s[0] + s[1] + s[2];
    for (int i = 0; i + 2 < n; i++) {
        int l = i + 1, r = n - 1;
        while (l < r) {
            int sum = s[i] + s[l] + s[r];
            if (Math.abs(sum - target) < Math.abs(best - target)) best = sum;
            if (sum < target) l++;
            else if (sum > target) r--;
            else return sum;
        }
    }
    return best;
}

C++

int threeSumClosest(vector<int>& nums, int target) {
    vector<int> s = nums;
    sort(s.begin(), s.end());
    int n = (int) s.size();
    int best = s[0] + s[1] + s[2];
    for (int i = 0; i + 2 < n; i++) {
        int l = i + 1, r = n - 1;
        while (l < r) {
            int sum = s[i] + s[l] + s[r];
            if (abs(sum - target) < abs(best - target)) best = sum;
            if (sum < target) l++;
            else if (sum > target) r--;
            else return sum;
        }
    }
    return best;
}

JavaScript

var threeSumClosest = function(nums, target) {
    const s = nums.slice().sort(function(a, b) { return a - b; });
    let best = s[0] + s[1] + s[2];
    for (let i = 0; i < s.length - 2; i++) {
        let l = i + 1, r = s.length - 1;
        while (l < r) {
            const sum = s[i] + s[l] + s[r];
            if (Math.abs(sum - target) < Math.abs(best - target)) best = sum;
            if (sum === target) return sum;
            if (sum < target) l++;
            else r--;
        }
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms