3Sum Closest - Leetcode Solution

Problem Link

💡 Step-by-Step Thought Process

Understand the problem: Find three numbers in an array whose sum is closest to a given target.
Sort the array to enable efficient two-pointer traversal and skip duplicates.
Initialize closest_sum to infinity to track the sum closest to the target.
Iterate through each index i from 0 to n-3.
Skip duplicate values at i to avoid redundant triplets.
Use two pointers, lo (i+1) and hi (n-1), to find pairs that sum with nums[i].
Compute the current sum as nums[i] + nums[lo] + nums[hi].
If the absolute difference between current sum and target is less than that of closest_sum and target, update closest_sum.
If current sum equals target, return it immediately.
If current sum is less than target, increment lo; otherwise, decrement hi.
Return closest_sum after the loop.

Code Solution

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        n = len(nums)
        nums.sort()
        closest_sum = float('inf')

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

            lo, hi = i + 1, n - 1
            while lo < hi:
                cur_sum = nums[i] + nums[lo] + nums[hi]

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

                if cur_sum == target:
                    return cur_sum
                elif cur_sum < target:
                    lo += 1
                else:
                    hi -= 1

        return closest_sum
        # Time: O(n^2)
        # Space: O(n)

#include <vector>
#include <algorithm>
#include <cstdlib>

class Solution {
public:
    int threeSumClosest(std::vector<int>& nums, int target) {
        int n = nums.size();
        std::sort(nums.begin(), nums.end());
        int closestSum = INT_MAX;

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

            int lo = i + 1, hi = n - 1;
            while (lo < hi) {
                int curSum = nums[i] + nums[lo] + nums[hi];

                if (std::abs(curSum - target) < std::abs(closestSum - target)) {
                    closestSum = curSum;
                }

                if (curSum == target) {
                    return curSum;
                } else if (curSum < target) {
                    lo++;
                } else {
                    hi--;
                }
            }
        }
        return closestSum;
    }
};

import java.util.Arrays;

public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int n = nums.length;
        Arrays.sort(nums);
        int closestSum = Integer.MAX_VALUE;

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

            int lo = i + 1, hi = n - 1;
            while (lo < hi) {
                int curSum = nums[i] + nums[lo] + nums[hi];

                if (Math.abs(curSum - target) < Math.abs(closestSum - target)) {
                    closestSum = curSum;
                }

                if (curSum == target) {
                    return curSum;
                } else if (curSum < target) {
                    lo++;
                } else {
                    hi--;
                }
            }
        }
        return closestSum;
    }
}

var threeSumClosest = function(nums, target) {
    nums.sort((a, b) => a - b);
    let n = nums.length;
    let closestSum = Infinity;

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

        let lo = i + 1, hi = n - 1;
        while (lo < hi) {
            let curSum = nums[i] + nums[lo] + nums[hi];

            if (Math.abs(curSum - target) < Math.abs(closestSum - target)) {
                closestSum = curSum;
            }

            if (curSum === target) {
                return curSum;
            } else if (curSum < target) {
                lo++;
            } else {
                hi--;
            }
        }
    }
    return closestSum;
};

Detailed Explanation

Understanding the 3Sum Closest Problem

The "3Sum Closest" problem asks you to find a triplet in an array of integers such that the sum of the three numbers is closest to a given target value. This problem is a variation of the classic 3Sum problem and is frequently encountered in technical interviews because it tests your ability to combine sorting and two-pointer techniques to achieve efficient solutions.

Efficient Strategy Using Sorting and Two Pointers

To solve this problem efficiently, we start by sorting the array in ascending order. Sorting allows us to use a two-pointer technique, which helps reduce the time complexity from O(n³) in a brute-force approach to O(n²).

We fix one element at a time using a loop, and for the remaining subarray, we apply the two-pointer method. We initialize two pointers: one starting just after the fixed element (left) and one at the end of the array (right). At each step, we calculate the sum of the three elements. If this sum is exactly equal to the target, we return it immediately, as we can’t get any closer. Otherwise, we update the closest sum if the current one is closer than our previous best.

Depending on whether the current sum is less than or greater than the target, we adjust our pointers accordingly. Moving the left pointer forward increases the sum, while moving the right pointer backward decreases it. This process continues until the left and right pointers meet.

Time and Space Complexity

Time Complexity: O(n²), where n is the length of the array. Sorting takes O(n log n), and the two-pointer scan for each element adds O(n²) total complexity.
Space Complexity: O(1), since we use only constant extra space aside from the input array.

Why This Approach is Optimal

By combining sorting with two-pointer traversal, this approach avoids unnecessary repeated computation of all triplet sums, which would be inefficient for large arrays. Sorting provides a structure that enables intelligent pointer movement based on the sum comparison with the target. This ensures that we examine only the most relevant combinations of triplets, significantly improving performance.

Conclusion

The 3Sum Closest problem demonstrates how classical algorithm techniques like sorting and two pointers can be leveraged to build efficient solutions for combination-based problems. Mastering this approach not only improves performance but also strengthens your ability to solve related optimization and search problems with confidence.

Get Personalized Support at AlgoMap Bootcamp 💡