Algorithm Day110 - 3Sum Closest

Posted on In Views:

LC-16 3Sum Closest

📌 Problem

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

1
2
3
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).

💡 Intuition

The problem is similar to the classic 3Sum, but instead of finding an exact match, we want the closest sum.
We can sort the array first, then use a two-pointer approach to efficiently explore possible triplets.

🔢 Java Code (Sorting + Two Pointers)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.*;

class Solution {
    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++) {
            int left = i + 1, right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (Math.abs(sum - target) < Math.abs(closest - target)) {
                    closest = sum;
                }
                if (sum < target) left++;
                else if (sum > target) right--;
                else return sum; // exact match
            }
        }
        return closest;
    }
}

⏱ Complexity Analysis

  • Time: O(n²) — Sorting takes O(n log n), and two-pointer scanning for each element takes O(n²).
  • Space: O(1) — In-place sorting, no extra space used.

✍️ Summary

  • Sort the array to apply two-pointer logic.
  • Track the closest sum as we move pointers.
  • Efficient and intuitive extension of the 3Sum problem.