Alkesh

LeetCode - 3Sum closest

Problem statement

Given an integer array nums of length n 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.

Problem statement taken from: https://leetcode.com/problems/3sum-closest

Example 1:

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

Example 2:

Input: nums = [0, 0, 0], target = 1
Output: 0

Constraints:

- 3 <= nums.length <= 1000
- -1000 <= nums[i] <= 1000
- -10^4 <= target <= 10^4

Explanation

Brute force approach

A simple approach to solving the problem is to explore all the subsets of size 3 and keep a track of the difference between target and the sum of this subset. Then return the subset whose difference between sum and target is minimum.

C++ implementation of the above approach looks like this:

for (int i = 0; i < arr.size() ; i++)
{
    for(int j =i + 1; j < arr.size(); j++)
    {
        for(int k =j + 1; k < arr.size(); k++)
        {
            //update the closestSum
            if(abs(x - closestSum) > abs(x - (arr[i] + arr[j] + arr[k])))
                closestSum = (arr[i] + arr[j] + arr[k]);
        }
    }
}

return closestSum

Since we are using three nested loops, the time complexity of the above approach is O(N^3) and no extra space is required the space complexity is O(1).

Two pointer technique

By sorting the array, we can improve the efficiency of the algorithm. Once the array is sorted, we can use the two-pointer technique.

We traverse the array and fix the first element of the triplet. We use the two-pointer algorithm to find the closest number to target - nums[i]. Update the closest sum. Since the two-pointer takes linear time, it is better than a nested loop.

Algorithm
- if nums.size < 3
  - return 0

- sort(nums.begin(), nums.end())

- set i = 0, minDiff = INT_MAX
- initialize sum

- loop while i < nums.size() - 2
  - set left = i + 1
  - set right = nums.size() - 1

  - loop while right > left
    - set temp = nums[i] + nums[left] + nums[right]
    - set diff = abs(temp - target)

    - if diff == 0
      - return target

    - if diff < minDiff
      - minDiff = diff
      - sum = temp

    - if temp < target
      - left++
    - else
      - right++

  - loop end

  - i++
- loop end

- return sum
C++ Solution
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        if(nums.size() < 3){
            return 0;
        }

        sort(nums.begin(), nums.end());

        int i = 0;
        int sum, minDiff = INT_MAX;

        while(i < nums.size() - 2){
            int left = i + 1;
            int right = nums.size() - 1;
            while(right > left){
                int temp = nums[i] + nums[left] + nums[right];
                int diff = abs(temp - target);

                if(diff == 0){
                    return target;
                }

                if(diff < minDiff){
                    minDiff = diff;
                    sum = temp;
                }

                if(temp < target){
                    left++;
                }
                else{
                    right--;
                }
            }
            i++;
        }

    return sum;
  }
};
Golang Solution
const MaxUint = ^uint(0)
const MaxInt = int(MaxUint >> 1)

func absInt(x int) int{
    if x < 0 {
        return x*-1
    }

    return x
}

func threeSumClosest(nums []int, target int) int {
    numsLength := len(nums)
    if numsLength < 3 {
        return 0
    }

    sort.Ints(nums)

    i, sum := 0, 0
    minDiff := MaxInt

    for i < numsLength - 2 {
        left := i + 1
        right := numsLength - 1

        for right > left {
            temp := nums[i] + nums[left] + nums[right]
            diff := absInt(temp - target)

            if diff == 0 {
                return target
            }

            if diff < minDiff {
                minDiff = diff
                sum = temp
            }

            if temp < target {
                left++
            } else {
                right--
            }
        }

        i++
    }

    return sum
}
Javascript solution
var threeSumClosest = function(nums, target) {
    if(nums.length < 3) {
        return 0;
    }

    nums.sort();

    let i = 0, minDiff = Number.MAX_VALUE;
    let sum;

    while( i < nums.length - 2 ){
        let left = i + 1;
        let right = nums.length - 1

        while( right > left ){
            let temp = nums[i] + nums[left] + nums[right];
            let diff = Math.abs(temp - target);

            if( diff == 0 ){
                return target;
            }

            if( diff < minDiff ){
                minDiff = diff;
                sum = temp;
            }

            if( temp < target ){
                left++;
            } else {
                right--;
            }
        }
        i++;
    }

    return sum;
};

Let's dry-run our algorithm to see how the solution works.

Input: nums = [-1, 2, 1, -4], target = 1

Step 1: if nums.size() < 3
           4 < 3
           false

Step 2: sort(nums.start(), nums.end())
          - [-4, -1, 1, 2]

Step 3: int i = 0;
        int sum, minDiff = INT_MAX;

Step 4: loop while i < nums.size() - 2
        0 < 4 - 2
        0 < 2
        true

        left = i + 1
             = 0 + 1
             = 1
        right = nums.size() - 1
              = 4 - 1
              = 3

        loop while right > left
        3 > 1
        true

        temp = nums[i] + nums[left] + nums[right]
             = nums[0] + nums[1] + nums[3]
             = -4 + -1 + 2
             = -3

        diff = abs(temp - target)
             = abs(-3 - 1)
             = abs(-4)
             = 4

        if diff == 0
           4 == 0
           false

        if diff < minDiff
           4 < INT_MAX
           true

           minDiff = diff
                   = 4
           sum = temp
               = -3

        if temp < target
           -3 < 4
           true

           left++
           left = 2

        loop while right > left
        3 > 2
        true

        temp = nums[i] + nums[left] + nums[right]
             = nums[0] + nums[2] + nums[3]
             = -4 + 1 + 2
             = -1

        diff = abs(temp - target)
             = abs(-1 - 1)
             = abs(-2)
             = 2

        if diff == 0
           2 == 0
           false

        if diff < minDiff
           2 < 4
           true

           minDiff = diff
                   = 2
           sum = temp
               = -1

        if temp < target
           -1 < 4
           true

           left++
           left = 3

        loop while right > left
        3 > 3
        false

        i++
        i = 1

Step 5: loop while i < nums.size() - 2
        1 < 4 - 2
        1 < 2
        true

        left = i + 1
             = 1 + 1
             = 2
        right = nums.size() - 1
              = 4 - 1
              = 3

        loop while right > left
        3 > 2
        true

        temp = nums[i] + nums[left] + nums[right]
             = nums[1] + nums[2] + nums[3]
             = -1 + 1 + 2
             = 2

        diff = abs(temp - target)
             = abs(2 - 1)
             = abs(1)
             = 1

        if diff == 0
           1 == 0
           false

        if diff < minDiff
           1 < 2
           true

           minDiff = diff
                   = 1
           sum = temp
               = 2

        if temp < target
           2 < 4
           true

           left++
           left = 3

        loop while right > left
        3 > 3
        false

        i++
        i = 2

Step 6: loop while i < nums.size() - 2
        2 < 4 - 2
        2 < 2
        false

Step 7: return sum
        return 2

So the answer is 2.
Share this post!