3Sum Closest [TC: O(N^2); SC: O(1)]

3sum-closest.cpp

// Problem Link: https://leetcode.com/problems/3sum-closest/
// Test Link: https://ide.geeksforgeeks.org/EBNEOuStvx
// Solution Status: Accepted in Leetcode Online Judge

class Solution {
public:
  // Approach: Two-Pointer Technique. Time Complexity: Quadratic O(N^2) -- because we fix one element, and for
  // the remaining elements, we apply two-ptr technique.
  int threeSumClosest(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end()); // sort the array to apply two-ptr technique
    
    int closestSum = 1e8; // A very large number. Taking INT_MAX can cause overflow.
    const int nums_size = nums.size();
    for(int i = 0; i < nums_size; ++i) {
      // Fix one element: nums[i] and apply two ptr technique on the remaining elements
      int p1 = i+1, p2 = nums_size - 1;
      while(p1 < p2) {
        int sum = nums[i] + nums[p1] + nums[p2];
        if(abs(target - closestSum) > abs(target - sum))
          closestSum = sum;
        
        if(sum == target) return sum;
        else if(sum < target) ++p1;
        else --p2;
      }
    }
    return closestSum;
  }
};

Problem Link
Test Link