3Sum Closest – Leetcode #16

This problem is from Leetcode – 3Sum Closest. The problem statement in short is given below:

Given an array nums of integers and an integer target, find the sum of three integers in nums such that the sum is closest to target. Assume there is only one solution.

SOLUTION

FIRST APPROACH

Here we modify the 2-pointer approach used in the last problem – 3Sum. See the code sample below:

public int threeSumClosest(int[] nums, int target) {

		int diff = 0;
		int distFromTarget = Integer.MAX_VALUE;
		int lowestSum = 0;

		Arrays.sort(nums);

		int len = nums.length;

		for(int i=0; i<len-2; i++) {

			// skip duplicates
			if(i>0 && nums[i] == nums[i-1]) {
				continue;
			}

			int j = i+1;
			int k = nums.length-1;

			while(j < k) {

				int sum = nums[i] + nums[j] + nums[k];
				diff = Math.abs(target - sum); 
				
				// minimize distanceFromTarget
				if(distFromTarget > diff){

					distFromTarget = diff;
					lowestSum = sum;
				}

				if(sum == target) 
					return sum;

				else if(sum < target)				
					j++;

				else if(sum > target)
					k--;


			} // endwhile

		}// end outer for loop


		return lowestSum;
	}

You can checkout the code from Github here – 3Sum Closest – Leetcode #16 – FirstApproach

PERFORMANCE ANALYSIS

RUNTIME	13 ms | Beats 90.11 %
MEMORY	43.66 MB | Beats 15.14 %
TIME COMPLEXITY	O (N2)
SPACE COMPLEXITY	O (N)