Leetcode 16. 3Sum Closest

Problem Explanation

Given an array of integers and a target integer, the goal is to find three numbers in the array such that their sum is closest to the target. If the exact sum is found, it can be returned immediately. However, if the exact sum cannot be found, then the sum that is as close as possible to the target should be returned.

For example, consider the array nums = [-1, 2, 1, -4], and target = 1. The three numbers in the array that their sum is closest to the target are -1, 2, and 1 because their sum equals 2. Hence, the solution to this problem is 2.

Approach of the Solution

This problem can be approached using the two-pointers technique. The two pointers technique involves having two pointers, one which is set to the start of the array and another which is set to the end of the array.

The solution starts with sorting the array and initialising the ans variable with the sum of the first three elements of the array nums.

Then, we loop starting from the first element of the array until we reach the element that is before the last two numbers. For each i, we set a pointer l pointing to the element after i and another pointer r pointing to the last element of the array.

While l is less than r, we calculate the sum of the values pointed to by i, l, and r. Then, we compare this sum to the target. If the sum equals to the target, we return the sum. Otherwise, we update ans only if the absolute difference between sum and target is less than the absolute difference between ans and target.

Also, if the sum is less than the target, we increment l. If not, we decrement r.

Finally, if we exit the loop without finding a sum, equal to the target, we return ans.

Now let's walk-through the solution code using C++, Java, Python, and JavaScript

C++ solution

1
2cpp
3class Solution {
4 public:
5  int threeSumClosest(vector<int>& nums, int target) {
6    int ans = nums[0] + nums[1] + nums[2];
7    sort(begin(nums), end(nums)); // sorting the array
8    for (int i = 0; i + 2 < nums.size(); ++i) {
9      if (i > 0 && nums[i] == nums[i - 1]) continue;
10      int l = i + 1;
11      int r = nums.size() - 1;
12      while (l < r) {
13        const int sum = nums[i] + nums[l] + nums[r];
14        if (sum == target) return sum;
15        if (abs(sum - target) < abs(ans - target)) ans = sum;
16        if (sum < target) ++l;
17        else --r;
18      }
19    }
20    return ans;
21  }
22};

Java solution

1
2java
3import java.util.Arrays;
4
5class Solution {
6    public int threeSumClosest(int[] nums, int target) {
7        int closest = nums[0] + nums[1] + nums[2];
8        Arrays.sort(nums); // sorting the array
9        for (int i = 0; i < nums.length - 2; i++) {
10            int left = i + 1;
11            int right = nums.length - 1;
12            while (left < right) {
13                int sum = nums[i] + nums[left] + nums[right];
14                if (Math.abs(sum - target) < Math.abs(closest - target)) {
15                    closest = sum;
16                }
17                if (sum > target) {
18                    right--;
19                } else if (sum < target) {
20                    left++;
21                } else {
22                    return sum;
23                }
24            }
25        }
26        return closest;
27    }
28}

Python solution

1
2python
3class Solution:
4    def threeSumClosest(self, nums: List[int], target: int) -> int:
5        nums.sort() # sorting the array
6        closest = sum(nums[:3]) # initial closest sum
7        for i, num in enumerate(nums[:-2]):
8            l, r = i + 1, len(nums) - 1
9            while l < r:
10                s = num + nums[l] + nums[r]
11                if s == target:
12                    return s
13                if abs(s - target) < abs(closest - target):
14                    closest = s
15                if s < target:
16                    l += 1
17                elif s > target:
18                    r -= 1
19        return closest

JavaScript solution

1
2javascript
3var threeSumClosest = function(nums, target) {
4    nums.sort((a, b) => a - b); // sorting the array
5    let closest = nums[0] + nums[1] + nums[2];
6    for(let i = 0; i < nums.length - 2; i++){
7        let left = i + 1, right = nums.length - 1;
8        while(left < right){
9            let sum = nums[i] + nums[left] + nums[right];
10            if(Math.abs(sum - target) < Math.abs(closest - target)) closest = sum;
11            if(sum > target) right--;
12            else left++
13            if(closest === target) return closest;
14        }
15    }
16    return closest;
17};

C# solution

1
2csharp
3public class Solution {
4    public int ThreeSumClosest(int[] nums, int target) {
5        Array.Sort(nums); // sorting the array
6        int ans = nums[0] + nums[1] + nums[2];
7        for (int i = 0; i < nums.Length - 2; i++){
8            int start = i + 1, end = nums.Length - 1;
9            while (start < end){
10                int sum = nums[i] + nums[start] + nums[end];
11                if (Math.Abs(target - sum) < Math.Abs(target - ans)){
12                    ans = sum;
13                }
14                if (sum > target){
15                    end--;  
16                } else {
17                    start++;
18                }
19            }
20        }
21        return ans;
22    }
23}

In all the five languages (C++, Java, Python, JavaScript, and C#), we sort the given array and initialize the initial answer to be the sum of the first three elements in the array. Then, we apply the two-pointers technique. We iterate over each element one by one and for each element, a pointer is assigned to the element following it and another one assigned to the last element of the array. Then, we keep adjusting the pointers if the sum is less than or greater than the target, and also update our answer if we find a closer sum. If the exact sum equal to the target is found, we return it immediately. Otherwise, after looping over all elements, we return the closest sum we found.

The time complexity for this problem can be O(n^2), where n is the length of the array. This is because, in the worst-case scenario, we will need to check each pair of numbers in the array (which requires two loops). As for the space complexity, it is O(n log n) to O(n^2) which is needed for sorting. But, while sorting can help to speed up the operation, it is not necessarily required.

Note: The comparison between ans and sum relies on the absolute difference to the target. Even though the sum might be larger than the target, it can still be closer to the target than other sums, which would result in updated ans. This is why the absolute difference is used in the comparison.

All solutions are concise and readable in their corresponding language. To understand them better, individual study on the languages is needed due to their syntax. To improve the algorithm, other advanced data structures could be used, such as trees and graphs. We also need to consider edge cases, like duplicate values in the array and ensure our solution handles them correctly.