81. Count Triplets Such That One Element Is the Sum of the Other Two

Given an array of n integers, count the number of unordered triplets (three distinct elements, by index) where the largest of the three equals the sum of the other two.

Input: The first line contains an integer n. The second line contains n space-separated integers. Output: Print a single integer - the count of triplets where the largest element equals the sum of the other two.

3 <= n <= 2000

Sorting first is what makes the two-pointer technique possible at all - two pointers rely on being able to move confidently in one direction based on whether the current sum is too high or too low, which only works on sorted data.

Count how many groups of three numbers exist where the biggest one equals the sum of the other two. Brute force: Check every possible combination of three distinct elements directly (three nested loops), verifying if the largest equals the sum of the other two - this costs O(n³), too slow for arrays larger than a few hundred elements. Optimised: Sorting first, then fixing each element in turn as the 'largest' candidate and using a two-pointer sweep on everything smaller than it (looking for a pair summing exactly to it), reduces the search from checking every triplet combination down to a linear two-pointer scan per candidate - the same reduction technique used for the classic 3Sum problem.

Check every triplet of three distinct indices directly, and for each one, determine which of the three values is the largest and test whether it equals the sum of the other two, incrementing a counter on success. This is a straightforward, obviously-correct reading of the problem, but examining all C(n,3) triplets one by one is cubic and too slow as n approaches 2000. Time: O(n^3) Space: O(1)

With the array sorted, fix arr[k] as the candidate largest value (iterating k from the end backward), then use two pointers i and j starting at the two ends of the subarray before k (i at the start, j at k-1) and move them toward each other: if arr[i]+arr[j] equals arr[k], count it and move both pointers inward (handling equal-value runs carefully to count all matching pairs); if the sum is too small, advance i; if too large, decrease j. This finds all valid pairs for each k in a single linear sweep rather than needing a hash set, giving the same quadratic time as the hashing approach but with constant extra space instead of linear. Time: O(n^2) Space: O(1) extra (excluding the sort)

Sort the array first so that, for any fixed index k, every element before it is guaranteed to be less than or equal to arr[k], meaning arr[k] is a valid candidate for the 'largest' element of a qualifying triplet. Then, for each k from right to left, build a hash set of the elements strictly before k, and for each i < k check whether arr[k] - arr[i] is present in that set at an index between i and k. Using a hash set to test the complement's existence replaces a linear inner scan with a near O(1) lookup, cutting one factor of n off the brute force. Time: O(n^2) Space: O(n)

1. Sort the array first. 2. For every element, treat it as the potential LARGEST of a candidate triplet. 3. Use two pointers on the elements BEFORE it (which are all smaller or equal, since the array is sorted) to search for pairs that sum exactly to it. 4. Count every such matching pair found, across every possible 'largest' candidate.

Time: O(n²) - sorting costs O(n log n), and then for each of the n elements, a two-pointer scan costs O(n), giving O(n²) overall. Space: O(1) extra space beyond what the sort itself requires (or O(log n) for the sort's own recursion, depending on the algorithm).

n = 3 (exactly one triplet to check) and n = 2000 (largest, confirming the sort plus two-pointer approach scales); also test an array with no qualifying triplet (answer 0).

Be ready to connect this directly to the classic 3Sum problem (find triplets summing to zero) - this is structurally the identical technique, just with a different target for each candidate 'largest' element instead of a fixed zero.