3Sum Closest | Leetcode 16 Solution

The 3Sum Closest problem from Leetcode is a popular algorithmic challenge that tests your understanding of array manipulation and optimization techniques. In this article, we’ll cover the problem statement, a step-by-step approach to solving it, and explain multiple solutions from naive to optimized with their complexities. We’ll also provide well-commented Java code for each solution.

Problem Statement for 3Sum Closest

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. 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).

Solution Approaches for 3Sum Closest

1. Naive Solution (Brute Force) for 3Sum Closest

Algorithm:

1. Use three nested loops to pick every combination of three numbers from the array.
2. Calculate the sum of the three numbers.
3. Compare the absolute difference between the current sum and the target with the closest sum found so far.
4. Update the closest sum if the current one is better.

Complexity:

• Time Complexity: O(n3)O(n^3)O(n3)
  Three nested loops traverse the array.
• Space Complexity: O(1)O(1)O(1)
  No extra space is used.

Java Code:

public class ThreeSumClosest {
    public int threeSumClosestBruteForce(int[] nums, int target) {
        int closestSum = Integer.MAX_VALUE;
        int n = nums.length;
        
        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 currentSum = nums[i] + nums[j] + nums[k];
                    if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
                        closestSum = currentSum;
                    }
                }
            }
        }
        return closestSum;
    }
}

2. Optimized Solution for 3Sum Closest with Sorting and Two Pointers

Algorithm:

1. Sort the array.
2. Use a loop to fix one element (nums[i]) and find the closest sum for the remaining two elements using the two-pointer technique:
   • Initialize two pointers, one at the start (left = i + 1) and one at the end (right = n - 1) of the remaining array.
   • Calculate the current sum and compare it with the target.
   • Move pointers based on whether the sum is smaller or larger than the target.
3. Update the closest sum if needed.

Complexity:

• Time Complexity: O(n2)O(n^2)O(n2)
  Sorting takes O(nlog⁡n)O(n \log n)O(nlogn), and the two-pointer traversal takes O(n2)O(n^2)O(n2).
• Space Complexity: O(1)O(1)O(1)
  Sorting is done in place.

Java Code:

import java.util.Arrays;

public class ThreeSumClosest {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums); // Sort the array
        int closestSum = nums[0] + nums[1] + nums[2]; // Initialize with a valid sum
        
        for (int i = 0; i < nums.length - 2; i++) {
            int left = i + 1, right = nums.length - 1;
            
            while (left < right) {
                int currentSum = nums[i] + nums[left] + nums[right];
                
                // Update closestSum if this sum is closer to the target
                if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
                    closestSum = currentSum;
                }
                
                // Move pointers based on the comparison with the target
                if (currentSum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return closestSum;
    }
}

3. Further Optimizations

The two-pointer approach is already efficient for this problem. However, we can add some optimizations:

1. Early Exit: If currentSum == target, return the currentSum immediately as it’s the closest possible value.
2. Avoid Redundant Calculations: Use conditions to skip duplicate numbers.

Conclusion

In this article, we covered solutions for the 3Sum Closest problem:

1. A naive O(n3)O(n^3)O(n3) brute force approach.
2. An optimized O(n2)O(n^2)O(n2) solution using sorting and the two-pointer technique.

The two-pointer approach is the most efficient and is recommended for practical use. This problem teaches valuable optimization strategies, such as reducing nested loops with sorting and two-pointer techniques.