28. Find the Triplet That Sums to a Given Value

Given an array and a target sum, determine whether any three elements add up to exactly that target. Print 'Yes' or 'No'.

Input: The first line contains an integer n. The second line contains n space-separated integers. The next line contains the target sum. Output: Print 'Yes' if any three elements sum to the target, otherwise print 'No'.

1 <= n <= 10^5

Sorting first is what enables the two-pointer technique - without a sorted order, there's no reliable way to decide which pointer to move based on whether the current sum is too big or too small.

Check whether any three numbers in an array add up to exactly a given target value. Brute force: Check every possible combination of three distinct elements directly (three nested loops) - this costs O(n³), too slow for larger arrays. Optimised: Sorting first, then fixing each element in turn and using two pointers on the rest (searching for a pair summing to the needed remainder), reduces the search from checking every triplet combination to a linear two-pointer scan per fixed element - the same reduction used for the classic 3Sum problem.

Sort the array once, then fix the first element with an outer loop and use two pointers - one just after the fixed element, one at the end of the array - moving the low pointer up when the three-way sum is too small and the high pointer down when it's too large, until they meet or a match is found. This achieves the same quadratic time as the hashset approach but needs no extra hashset storage beyond the sort itself, relying purely on the sorted order to prune the search space, which makes it the more memory-efficient and typically faster standard solution for this problem. Time: O(n^2) Space: O(1)

Try every combination of three distinct indices i < j < k and check whether arr[i] + arr[j] + arr[k] equals the target, printing 'Yes' the moment a match is found and 'No' if none exists after exhausting all combinations. This checks every possible triplet directly from the problem statement, but the number of triplets to check grows cubically with n. Time: O(n^3) Space: O(1)

Fix the first element of the triplet with an outer loop, then for the remaining two elements, use a hashset to solve a two-sum-style check: as you scan forward, for each element check whether (target - fixed - current) has already been seen, and if so a valid triplet exists. This drops one nested loop compared to the brute force by trading it for O(1) average-time hashset lookups, reducing overall time from cubic to quadratic at the cost of extra hashset memory. Time: O(n^2) Space: O(n)

1. Sort the array first. 2. Fix one element as the 'first' member of the candidate triplet. 3. Use two pointers (one just after the fixed element, one at the very end) on the remaining elements, searching for a pair that sums to exactly (target - fixed element). 4. If the two-pointer sum is too small, move the left pointer forward; if too big, move the right pointer backward; if it matches exactly, you've found your triplet.

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

n < 3 (no triplet can exist, so the answer must be 'No'); an array where no triplet reaches the target (print 'No'); and n = 10^5 (largest, confirming a sort plus two-pointer approach, not brute-force O(n^3), is required).

This is literally the classic '3Sum' problem under a different name - recognizing it instantly and reciting the sort-plus-two-pointer approach confidently is exactly what's expected.