16. 3Sum Closest

Hello, reader 👋🏽 ! Welcome to day 8 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 3Sum - Closest.

🤔 Problem Statement

• Given an array of integers and target, find three numbers such that their sum is the closest to the given target. Return this closest sum.
• For e.g. nums = [-1,2,1,-4], target = 1, then the closest sum = 2 (-1+2+1).

You can find the question here: 3Sum - Closest.

💬 Initial Thought Process - Naive Approach

• The solution is pretty straightforward and I came up with the naive approach immediately.

• It's basically figuring out all possible 3sum and keep track of the closest sum to the target.

• Something like this:

  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++) {
              // find sum of nums[i] + nums[j] + nums[k] 
              // check if this sum is closest to target
          }
      }  
  }
  

• But the above approach is terribly slow: O(n^3)

• So how can we solve this?

• Well, initially I thought of this:

  • We generate all possible pairs <i,j> and save them in a list. (This takes O(n^2)).
  • Now, we traverse through the array and find k for all the pairs such that i != k && j != k. (This also takes O(n^2)).
  • And for every such triplet, we calculate the the sum and compare if this is the closest sum to the target.

• Unfortunately, the above approach resulted in TLE.

• Then I had to look into the tag and noticed sorting and two pointers. Now, this did give me an idea.

💬 Thought Process - Sorted 2 Pointers

• The idea is: sort the array and for every index i from i = 0 => i = n-2, set 2 pointers: one at i+1 and another at n-1.
• We run the second loop for every i, such that the left pointer is always less than the right pointer.
  • If the sum of the numbers at i, left and right is greater than the target, then we know that the number must be in the range [i+1, n-2] => since the array is sorted.
  • But if the sum is less than the target, then we know that the number must be in the range [i+2,n-1] => since the array is sorted.
  • And if the sum is equal to the target, we just return the target!

• Now let's look into the code!

👩🏽‍💻 Solution - Sorted 2 Pointers

• Below is the code for the above approach:

class Solution { public int threeSumClosest(int[] nums, int target) { if(nums == null || nums.length <= 2) { return Integer.MIN_VALUE; }

    int n = nums.length;
    int closestSum = nums[0] + nums[1] + nums[2];

    Arrays.sort(nums);
    for(int outer = 0; outer < n-2; outer++) {
        int left = outer+1;
        int right = n-1;
        int outerNum = nums[outer];

        while(left < right) {
            int leftNum = nums[left];
            int rightNum = nums[right];
            int currSum = outerNum + leftNum + rightNum;

            if(currSum == target) {
                return target;
            }    
            if(currSum > target) {
                right--;
            }
            else {
                left++;
            }

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

    return closestSum;
}

}

Time Complexity: O(n^2)
     - n = number of elements in the array
Space Complexity: O(1)

Check out the code here.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!