342. Count Triplets With Sum Smaller Than a Given Value

Given an array of n integers and a target value, count the number of triplets (i, j, k with i < j < k) such that arr[i] + arr[j] + arr[k] is strictly less than the target.

Input: The first line contains an integer n. The second line contains n space-separated integers. The third line contains the target value. Output: Print a single integer - the count of triplets (i < j < k) whose sum is strictly less than the target.

3 <= n <= 2000

This is the 'smaller than target' cousin of the classic 3Sum-closest family of problems - the same sort-plus-two-pointers technique adapts to 'count pairs/triplets satisfying an inequality' just as naturally as it does to 'find an exact sum'.

Count how many groups of three numbers add up to LESS than a given target. 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 for each fixed smallest element using two pointers on the rest, lets you count MULTIPLE valid triplets in ONE step whenever the current sum is already small enough (since sorted order guarantees everything between the two pointers is also valid) - this batching is what reduces the complexity from cubic to quadratic.

After sorting, fix the smallest element at index i, then use two pointers j and k starting at i+1 and n-1 respectively scanning the remaining subarray toward each other. If arr[i]+arr[j]+arr[k] is less than the target, then it is also less than the target for every k' between j and k (since the array is sorted, decreasing k only decreases the sum), so all of those (k-j) triplets can be counted at once and j is advanced; otherwise k is decreased to try a smaller third element. This processes each fixed i in linear time with the two pointers only ever moving forward, replacing the binary search with an even cheaper sweep. Time: O(n^2) Space: O(1)

First sort the array; this doesn't change which triplets qualify since the count only depends on the multiset of values, not their positions. Then fix the first element at index i and the second element at index j (i < j), and binary search for the largest index k > j such that arr[i] + arr[j] + arr[k] is still less than the target - since the array is sorted, all indices from j+1 up to that boundary also work, so the count for this (i, j) pair is found in one search instead of a full inner loop. Summing this over all (i, j) pairs counts every valid triplet correctly. Time: O(n^2 log n) Space: O(1)

Check every triplet of indices i < j < k directly: three nested loops enumerate all combinations, and for each one test whether arr[i] + arr[j] + arr[k] is strictly less than the target, incrementing a counter when it is. This is a direct translation of the problem statement and is guaranteed correct, but examining all C(n,3) triplets becomes far too slow as n approaches 2000. Time: O(n^3) Space: O(1)

1. Sort the array first. 2. Fix the smallest index of a candidate triplet, then use two pointers (one just after it, one at the very end) on the remaining elements. 3. If the sum of all three is less than the target, EVERY index between the two pointers also forms a valid triplet with the fixed smallest element and the left pointer (since the array is sorted, all those in-between values are still small enough) - count all of them at once, then move the left pointer forward. 4. If the sum is too large, move the right pointer inward to try a smaller value.

Time: O(n²) - sorting costs O(n log n), and the two-pointer sweep for each fixed element costs O(n), giving O(n²) overall. Space: O(1) extra space beyond the sort itself.

n = 3 (only one possible triplet) and n = 2000 (largest size, confirming the O(n^2) two-pointer approach scales); also test a target smaller than every triplet sum (answer 0) and one larger than all of them (answer equals C(n,3)).

Be ready to explain precisely WHY you can count multiple triplets at once when the sum is small enough (every index between the two pointers is a valid 'right' partner) - this batching insight is what distinguishes an efficient two-pointer solution from a naive one that still checks pairs one at a time.