Leetcode – 16 – 3Sum Closest

3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Description:

This problem is same as that of Leetcode – 15 – 3Sum  but the change is that we have return the closest sum instead of the elements adding up to zero.

Solution (three pointers)

The approach that we are talking about is to sort the array first and then have one pointer running along the length of the array. We will have another two pointer to point to the start and end of the array elements

We will check for the sum store in a variable and if its equal to the target then we return the result. Otherwise we will get the difference and see if the value is closest enough to the target and return the closest after checking for all the elements in the array.

1

Code:

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int n = nums.length;
        int leastDiff = Integer.MAX_VALUE;
        int closest = 0;
        if(nums != null && n >= 3){
            Arrays.sort(nums);
            for(int i=0;i < n-2;i++){
                for(int j = i+1, k = n-1;j<k;){
                    int result = nums[i] + nums[j] + nums[k];
                    if(result == target){
                        return result;  
                    }
                    else{
                        int diff = Math.abs(target - result);
                        if(diff < leastDiff){
                            leastDiff = diff;
                            closest = result;
                        }
                        if(result > target){
                          k--;  
                        }
                        else{
                         j++;   
                        }
                    }
                }
                }
            }
            return closest;
        }    
    }

Time Complexity: O(n2)

  • Go through the length of array elements and check for elements adjacent to the current element – O(n2)

Space Complexity: O(1)

  • We will adding 3 elements to the list and can have n number of combinations  – O(n)

Available Test Cases: 120

  • Check for empty array
  • Check for duplicate elements

Github:

Leetcode_16_3_Sum_Closest

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: