Three Sum Closest to Target

You are given an array of n integers and an integer target. Find three distinct positions whose values sum as close as possible to target, and report that sum. If two different triplets are equally close to target (the same absolute difference), report the smaller of the two sums.

Input: The first line contains the integer n. The second line contains n space-separated integers. The third line contains the integer target. Output: Print a single integer: the sum of the triplet closest to target (the smaller sum on a tie).

3 <= n <= 3000 -10^5 <= arr[i] <= 10^5 -10^5 <= target <= 10^5

This is the 'closest' variant of the exact-sum triplet problem - the same sort-plus-fix-plus-two-pointer skeleton applies, just with the STOPPING/UPDATING condition changed from 'exact match' to 'track the closest distance seen so far'.

Find the triplet whose sum is closest to a target value, using sorting plus two pointers. Brute force: Check every possible triplet of positions directly, tracking the closest sum found - this costs O(n³), too slow for larger arrays. Optimised: Sorting first enables fixing one element and using two pointers to efficiently search the remaining sub-array for the CLOSEST-to-target pair sum, moving the appropriate pointer based on whether the current triplet sum is above or below target - this reduces the search from O(n³) to O(n²), the same reduction used for the exact-sum triplet problem.

1. Sort the array, then FIX one element and use TWO POINTERS on the rest to search for the pair that brings the triplet total NEAREST to target. 2. Track the BEST sum found so far by comparing ABSOLUTE DISTANCE to target; update whenever something STRICTLY CLOSER is found, or exactly as close but SMALLER. 3. Move the pointer on the SMALLER-sum side inward when the current triplet sum is BELOW target, and the OTHER side inward when it's ABOVE - this explores every useful triplet in O(n²).

Time: O(n²) - sorting costs O(n log n), and each of the n fixed elements gets an O(n) two-pointer scan. Space: O(1) extra space beyond the sort itself.

Handle the smallest allowed n = 3 (only one triplet is possible) and arrays where the exact target sum is achievable (the answer should equal target exactly); sort first and use two pointers per fixed first element to stay within O(n^2) at n = 3000.

Be precise about the exact tie-breaking rule (prefer the SMALLER sum when two candidates are EQUALLY close to target) - a small but easy-to-miss detail in this problem's specific requirement.