The LeetCode problem “3Sum Closest” asks us to find three numbers in an array that sum up to a value closest to a given target. For example, given an array nums = [-1, 2, 1, -4] and target 1, the three numbers closest to the target are [-1, 2, 1], which sum up to 2.
Algorithm and Data Structure Choice
Chosen Algorithm: Sorting and Two-Pointer Technique
The algorithm follows the two-pointer pattern on a sorted array, which is efficient for problems involving finding specific sums in pairs or triplets.
1. Combination of Elements with a Target Sum: The problem asks to find a triplet sum that’s closest to a target. This often suggests a two-pointer approach, especially in sorted arrays.
2. Minimizing the Difference: If the goal involves finding the closest match rather than an exact match, this method allows quick adjustments to bring the sum closer to the target.
3. Handling Multiple Elements: This pattern is useful for problems where multiple elements need to be selected and their sums compared or optimized.
This approach falls under sorted array two-pointer patterns that are frequently applied in problems where pairs or triplets need to reach a certain sum or are constrained in a particular order. Sorting simplifies the process, allowing us to make targeted adjustments instead of checking every combination.
• Time Complexity: O(n^2), where n is the number of elements in the array. This is because we sort the array O(n \log n) and then use two pointers within a loop O(n^2).
• Space Complexity: O(1), since we only use a few additional variables for tracking the closest sum (ignoring the input array sorting in-place).
High-Level Algorithm Steps
1. Sort the Array: Sort the array to allow for two-pointer adjustments.
2. Initialize Closest Sum: Set an initial closest sum with a large value.
3. Iterate with Fixed Element: For each element in the array (as the first element of the triplet):
• Use two pointers (left and right) to find the other two elements.
4. Calculate and Compare: For each triplet formed by the fixed element and two pointers:
• Calculate the sum.
• If the sum is closer to the target than the current closest, update the closest sum.
5. Adjust Pointers: Move pointers based on the comparison of the sum to the target.
6. Return the Closest Sum: After looping through all elements, return the closest sum.
import java.util.Arrays;
public class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums); // Sort the array for two-pointer approach
int closestSum = Integer.MAX_VALUE / 2; // Initialize closest sum with a large value
for (int i = 0; i < nums.length - 2; i++) { // Fix the first element
int left = i + 1, right = nums.length - 1; // Set two pointers
while (left < right) { // While pointers don't overlap
int currentSum = nums[i] + nums[left] + nums[right]; // Calculate triplet sum
// Check if this sum is closer to target than the closestSum found so far
if (Math.abs(target - currentSum) < Math.abs(target - closestSum)) {
closestSum = currentSum; // Update closestSum if it's closer
}
// Adjust pointers based on comparison with target
if (currentSum < target) {
left++; // Move left pointer right to increase sum
} else if (currentSum > target) {
right--; // Move right pointer left to decrease sum
} else {
return currentSum; // Exact match found
}
}
}
return closestSum; // Return the closest sum found
}
}
Line-by-Line Explanation
- Sorting the Array
Arrays.sort(nums);
• Sorting makes it possible to use the two-pointer approach effectively, allowing us to control the sum by moving pointers.
2. Initialize Closest Sum
int closestSum = Integer.MAX_VALUE / 2;
• We initialize closestSum with a large value to ensure that the first calculated sum will replace it.
3. Loop to Fix the First Element
for (int i = 0; i < nums.length - 2; i++) {• We loop through each element, treating it as the fixed first element of our triplet.
• We stop at nums.length – 2 to leave space for the other two elements in the triplet.
4. Set Two Pointers
int left = i + 1, right = nums.length - 1;
• We set left to the element immediately after i and right to the last element, enabling us to explore all valid triplets with the fixed element.
5. While Loop to Calculate and Compare Sums
while (left < right) {
int currentSum = nums[i] + nums[left] + nums[right];
• As long as left and right pointers don’t meet, calculate the sum of the three numbers (nums[i], nums[left], and nums[right]).
6, Update Closest Sum if Closer to Target:
if (Math.abs(target - currentSum) < Math.abs(target - closestSum)) {
closestSum = currentSum;
}
• If the current sum is closer to the target than closestSum, we update closestSum to the current sum.
7. Adjust The Pointers
if (currentSum < target) {
left++;
} else if (currentSum > target) {
right--;
} else {
return currentSum;
}• If currentSum is less than the target, we move left to the right to increase the sum.
• If currentSum is greater than the target, we move right to the left to decrease the sum.
• If currentSum exactly equals the target, we return it immediately as it’s the best possible match.
8, Return the Closest Sum
return closestSum;
• After checking all combinations, closestSum will hold the sum closest to the target, so we return it.
Why This Code Was Coded This Way
• Efficiency: The sorted two-pointer technique avoids unnecessary computations by focusing only on valid combinations and making targeted adjustments.
• Clarity: The separation of concerns (sorting, initializing, and updating pointers) keeps the code clean and easy to follow.
• Scalability: This approach is optimal for larger arrays due to the O(n^2) complexity, making it scalable compared to brute-force approaches.
The two-pointer technique combined with sorting provides a systematic and efficient way to find the sum closest to the target in a clean and understandable solution.
