algoadvance

Leetcode 16. 3Sum Closest

Problem Statement

Given an array nums of n integers 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:

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

Clarifying Questions

1. Q: Can the array contain duplicate integers? A: Yes, the array can contain duplicates.

2. Q: Should the solution handle large arrays efficiently? A: Yes, the solution should be efficient enough to handle reasonably large arrays as per typical LeetCode constraints.

3. Q: Are there any constraints on the values of integers in nums, such as minimum or maximum values? A: No specific constraints aside from standard integer limits.

Strategy

1. Sort the Array: Sorting the array will help in efficiently finding the closest sum using a two-pointer approach.
2. Traverse the Array: Use a for loop to iterate through each element.
3. Two-Pointer Technique: For each selected element, use two pointers (left and right) to find the pair that, along with the selected element, gives the closest sum to the target.
   • Initialize left to the element next to the current element and right to the last element.
   • Calculate the current sum of the triplet.
   • If the current sum is closer to the target than the previous closest sum, update the closest sum.
   • Move the pointers based on whether the current sum is less than or greater than the target to try and get closer to the target.

Code

import java.util.Arrays;

public class ThreeSumClosest {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int closestSum = nums[0] + nums[1] + nums[2];
        
        for (int i = 0; i < nums.length - 2; i++) {
            int left = i + 1;
            int right = nums.length - 1;
            
            while (left < right) {
                int currentSum = nums[i] + nums[left] + nums[right];
                
                if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
                    closestSum = currentSum;
                }
                
                if (currentSum < target) {
                    left++;
                } else if (currentSum > target) {
                    right--;
                } else {
                    // if the currentSum is exactly equal to the target, it's the closest possible sum
                    return currentSum;
                }
            }
        }
        
        return closestSum;
    }

    // For Testing
    public static void main(String[] args) {
        ThreeSumClosest solver = new ThreeSumClosest();
        int[] nums = {-1, 2, 1, -4};
        int target = 1;
        int result = solver.threeSumClosest(nums, target);
        System.out.println(result); // Output should be 2
    }
}

Time Complexity

• Sorting the array takes O(n log n).
• The traversal of the array with the two-pointer technique inside the for loop takes O(n^2) in the worst case.
  • For each element, the two-pointer approach runs a linear scan.

Thus, the overall time complexity of the algorithm is O(n^2).

Summary

• Sort the array.
• Use a for loop to iterate through the array and a two-pointer approach to find the closest triplet sum.
• Continuously update the closest sum when a closer sum is found.
• The time complexity is O(n^2), which is efficient for the given problem.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?