Leetcode 16 Solution

This article provides solution to leetcode question 16 (3sum-closest).
Categories:
Tags:
Access this page by simply typing in "lcs 16" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/3sum-closest

Thinking Process

This is a similar question to https://leetcode.com/problems/3sum. Same algorithm can be applied with a little bit variance.

Time & Space Complexity

Assuming N is the size of the array

  • Time complexity: O(N^2)
  • Space complexity: O(N)

Solution

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        bool assigned = false;
        int minval = INT_MAX;

        sort(nums.begin(), nums.end());
        
        for (int i = 0; i < nums.size(); i++)
        {
            int l = i + 1;
            int r = nums.size() - 1;
            
            while (l < r)
            {
                int s = nums[i] + nums[l] + nums[r];

                if (assigned == false || abs(minval - target) > abs(s - target))
                {
                    minval = s;
                    assigned = true;
                }
                
                if (s < target)
                    l++;
                else if (s > target)
                    r--;
                else
                    return target;
            }
        }
        
        return minval;
    }
};