Log inSign up
mediumLeetCodeNot Started

3Sum Closest

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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.

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), which has a difference of |2 - 1| = 1.

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), difference is |0 - 1| = 1.

Example 3:

Input: nums = [1,1,1,0], target = -100
Output: 2
Explanation: Triplets include (1+1+0=2) and (1+1+1=3). The closest sum to -100 is 2.

Constraints:

  • 3 <= nums.length <= 500
  • -1000 <= nums[i] <= 1000
  • -104 <= target <= 104

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Array sorting and indexing
  • Two-pointer search on sorted arrays (Two Sum II)
  • 3Sum problem concepts

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the Sort + Two-Pointer pattern for triplet summation problems.
  • Understand how sorting enables directional pointer adjustments based on currentSum vs target.
  • Implement absolute distance tracking with overflow-safe initialization.
  • Identify early termination conditions (e.g. currentSum === target).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding a combination of K elements whose sum is closest to, equal to, or bounded by a target.
  • Array is unsorted, but sorting doesn't disrupt the triplet sum requirement.
  • Continuous minimization of absolute difference |sum - target|.

Algorithmic Decision Tree:

  • If target requires exact match and count -> Hash Map or Two Pointers with deduplication.
  • If target requires closest sum of 3 numbers -> Sort + Two Pointers (O(N2) time, O(1) space).
  • If N is very small (N <= 500) -> O(N2) Two Pointer is optimal.

Connected Patterns:

3Sum (Exact Zero Triplet)3Sum SmallerTwo Sum II - Input Array Is Sorted

1. Check All Triplets (Brute Force)

Intuition

Iterate with three nested loops for all triplets 0 <= i < j < k < n. Compute sum = nums[i] + nums[j] + nums[k]. If abs(sum - target) < abs(closest - target), update closest.

When to apply: Use to understand the baseline search for triplet sums.

Exhaustive Triplet Enumeration (O(N^3) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Start exhaustive enumeration at indices (0, 1, 2)
Visual state
Values and pointers at this exact step
pointers
S
-1
2
1
-4
0
↑ i
1
↑ j
2
↑ k
3
Variables at this step
i
0
j
1
k
2
currentSum
2
target
1
closestSum
2
minDiff
1
Check / comparison
Evaluate first triplet: nums[0] + nums[1] + nums[2] = (-1) + 2 + 1 = 2
Decision / next transition
Diff |2 - 1| = 1. Initialize closestSum = 2, minDiff = 1.
Why this step matters

Start exhaustive enumeration at indices (0, 1, 2). The sum of 2 is only 1 away from target 1.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int threeSumClosest(int[] nums, int target) {
4 int closest = nums[0] + nums[1] + nums[2];
5 int n = nums.length;
6
7 for (int i = 0; i < n; i++) {
8 for (int j = i + 1; j < n; j++) {
9 for (int k = j + 1; k < n; k++) {
10 int sum = nums[i] + nums[j] + nums[k];
11 if (Math.abs(sum - target) < Math.abs(closest - target)) {
12 closest = sum;
13 }
14 }
15 }
16 }
17 return closest;
18 }
19 }
20
21 public static void main(String[] args) {
22 Solution sol = new Solution();
23 int[] nums = {-1, 2, 1, -4};
24 int target = 1;
25 System.out.println("Closest sum: " + sol.threeSumClosest(nums, target));
26 }
27}

Time & Space Complexity

  • Time complexity: O(n^3) — Three nested loops examine all n*(n-1)*(n-2)/6 triplets.
  • Space complexity: O(1) — Only scalar closest tracking variable.

Why Brute Force Doesn't Scale:

For N = 500, N3 = 125,000,000 loop operations. Sorting reduces search space by a factor of N to N2 = 250,000 operations.

On an array of size 500: Brute force takes ~125M operations (~150 ms); Two-pointer takes ~250K operations (< 1 ms).

2. Sort + Binary Search for 3rd Element

Intuition

Sorting takes O(n log n). For each pair (i, j), search for complement = target - nums[i] - nums[j] in nums[j+1..n-1] using lower_bound/binary search. Evaluate the closest element before and after complement.

When to apply: Use to understand reducing search complexity via binary search.

Sort + Binary Search Third Element (O(N^2 log N) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Sorting costs O(N log N)
Visual state
Values and pointers at this exact step
pointers
S
-4
-1
1
2
0
↑ sorted
1
2
3
Variables at this step
sorted
[-4,-1,1,2]
target
1
closestSum
null
minDiff
null
Check / comparison
Sort array ascending: [-4, -1, 1, 2]
Decision / next transition
Prepare to fix pair (i, j) and binary search k in range [j+1, n-1].
Why this step matters

Sorting costs O(N log N). For any fixed pair, the ideal third value is target - nums[i] - nums[j].

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int threeSumClosest(int[] nums, int target) {
6 Arrays.sort(nums);
7 int n = nums.length;
8 int closest = nums[0] + nums[1] + nums[2];
9
10 for (int i = 0; i < n - 2; i++) {
11 for (int j = i + 1; j < n - 1; j++) {
12 int complement = target - nums[i] - nums[j];
13 int low = j + 1, high = n - 1;
14 while (low <= high) {
15 int mid = low + (high - low) / 2;
16 int sum = nums[i] + nums[j] + nums[mid];
17 if (Math.abs(sum - target) < Math.abs(closest - target)) {
18 closest = sum;
19 }
20 if (nums[mid] < complement) low = mid + 1;
21 else high = mid - 1;
22 }
23 }
24 }
25 return closest;
26 }
27 }
28
29 public static void main(String[] args) {
30 Solution sol = new Solution();
31 int[] nums = {-1, 2, 1, -4};
32 int target = 1;
33 System.out.println("Closest sum: " + sol.threeSumClosest(nums, target));
34 }
35}

Time & Space Complexity

  • Time complexity: O(n^2 log n) — n2 pairs, each performing O(log n) binary search.
  • Space complexity: O(log n) or O(n) — Sorting recursion space.

3. Sort + Two Pointers (Optimal & Standard)

Intuition

1. Sort nums. 2. For each i from 0 to n-3: initialize left = i + 1, right = n - 1. 3. sum = nums[i] + nums[left] + nums[right]. 4. If abs(sum - target) < abs(closest - target), update closest. 5. If sum < target, left++ to increase sum; if sum > target, right-- to decrease sum; if sum == target, return target immediately.

When to apply: Use as the universal StudyVex Gold Standard for 3Sum variations.

Sort + Two Pointers (O(N^2) Time, O(1) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Because the array is sorted, when current sum (-3) is smaller than target (1), moving L right increases the sum
Visual state
Values and pointers at this exact step
pointers
S
-4
-1
1
2
0
↑ i
1
↑ L
2
3
↑ R
Variables at this step
i
0
L
1
R
3
sum
-3
target
1
closestSum
-3
minDiff
4
Check / comparison
Fix i = 0 (-4), set L = 1 (-1), R = 3 (2). Sum = -4 + (-1) + 2 = -3
Decision / next transition
Diff |-3 - 1| = 4. Set closestSum = -3. Since sum < 1, advance L to 2.
Why this step matters

Because the array is sorted, when current sum (-3) is smaller than target (1), moving L right increases the sum.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int threeSumClosest(int[] nums, int target) {
6 Arrays.sort(nums);
7 int n = nums.length;
8 int closest = nums[0] + nums[1] + nums[2];
9
10 for (int i = 0; i < n - 2; i++) {
11 int left = i + 1, right = n - 1;
12 while (left < right) {
13 int sum = nums[i] + nums[left] + nums[right];
14 if (Math.abs(sum - target) < Math.abs(closest - target)) {
15 closest = sum;
16 }
17 if (sum < target) {
18 left++;
19 } else if (sum > target) {
20 right--;
21 } else {
22 return target;
23 }
24 }
25 }
26 return closest;
27 }
28 }
29
30 public static void main(String[] args) {
31 Solution sol = new Solution();
32 int[] nums = {-1, 2, 1, -4};
33 int target = 1;
34 System.out.println("Closest sum: " + sol.threeSumClosest(nums, target));
35 }
36}

Time & Space Complexity

  • Time complexity: O(n^2) — Sorting takes O(n log n). Outer loop runs n times, inner two pointers take O(n).
  • Space complexity: O(1) auxiliary — Strictly pointer variables outside sorting recursion.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force (3 Nested Loops)O(N^3)O(1)Evaluate all possible triplets (i, j, k) and find the one with minimal |nums[i] + nums[j] + nums[k] - target|.3 nested iterations checking all C(N, 3) combinations without pruning.
2.Better (Sort + Binary Search on 3rd Element)O(N^2 log N)O(1) to O(N)Sort array, fix two elements (i, j), and binary search for the element closest to (target - nums[i] - nums[j]).Repeated logarithmic lookups per pair instead of two-pointer scan.
3.Optimal (Sort + Two Pointers)OptimalO(N^2)O(1)Sort array, fix element i, and use two pointers moving inward from both ends to track the closest sum.O(N2) two-pointer search loop.

Common Pitfalls & Crucial Edge Cases

Initializing closestSum to `INT_MAX`

When computing abs(currentSum - target) vs abs(closestSum - target), if target < 0, closestSum - target can cause integer overflow. Initialize with nums[0] + nums[1] + nums[2].

Forgetting to sort the array first

Two pointers only work if incrementing left increases the sum and decrementing right decreases the sum.

Returning the difference instead of the sum

Problem asks for the sum of the three integers, not abs(sum - target).

Crucial Edge Cases to Validate:

  • Exactly 3 elements (nums = [0, 1, 2], target = 0): Only 1 triplet possible; returns sum immediately without unnecessary iterations.
  • Exact match exists (target can be formed directly): Early exit returns target on currentSum == target without exploring further.
  • Large positive/negative target (target = 10000 or -10000): Initialization with nums[0] + nums[1] + nums[2] avoids overflow issues compared to INT_MAX.
  • All negative numbers (nums = [-5, -3, -2, -1], target = -10): Absolute difference arithmetic handles negative numbers transparently.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention the early exit optimization: if currentSum == target, return target immediately because difference is 0.
  2. Highlight why you initialize closestSum = nums[0] + nums[1] + nums[2] instead of INT_MAX (avoids overflow during subtraction).
  3. Compare with standard 3Sum: Explain that 3Sum Closest doesn't need duplicate skipping because we must evaluate every sum difference.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does sorting the array enable the two-pointer technique for 3Sum Closest?

2.What is the most robust way to initialize closestSum to prevent integer overflow?

3.What is the time complexity of the optimal Two-Pointer approach for 3Sum Closest?

Back to DSA Sheet