LeetCode //C - 16. 3Sum Closest

16. 3Sum Closest

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.
 

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
Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

Constraints:

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

From: LeetCode
Link: 16. 3Sum Closest

Solution:

Ideas:

1. Sorting: The array is sorted first using qsort to allow efficient searching.
2. Comparator Function: The compare function helps in sorting integers using qsort.
3. Two-Pointer Approach: After fixing one number (by iterating with i), two pointers (left and right) are used to find the best pair with nums[i] to approach the target sum.
4. Closest Sum Calculation: During the search, if the sum of nums[i], nums[left], and nums[right] is closer to the target than the previously found sums, it updates the closest sum.
5. Early Exit: If at any point the exact target sum is found, it immediately returns that sum, as it is the closest possible.

Code:

// Comparator function for qsort
int compare(const void *a, const void *b) {
    int int_a = *((int*)a);
    int int_b = *((int*)b);
    return int_a - int_b;
}

int threeSumClosest(int* nums, int numsSize, int target) {
    // Sort the array
    qsort(nums, numsSize, sizeof(int), compare);
    
    // Initialize the closest sum with the sum of the first three elements
    int closestSum = nums[0] + nums[1] + nums[2];
    
    // Iterate over each number in the array
    for (int i = 0; i < numsSize - 2; i++) {
        int left = i + 1;
        int right = numsSize - 1;
        
        while (left < right) {
            int currentSum = nums[i] + nums[left] + nums[right];
            
            // Check if the current sum is closer to the target than the closest sum
            if (abs(target - currentSum) < abs(target - closestSum)) {
                closestSum = currentSum;
            }
            
            // Move pointers based on comparison between currentSum and target
            if (currentSum > target) {
                right--;
            } else if (currentSum < target) {
                left++;
            } else {
                // If currentSum exactly equals to target, this is the closest we can get
                return currentSum;
            }
        }
    }
    
    return closestSum;
}