Count triplets with sum smaller than a given value
Problem
Return the number of index triplets i < j < k with arr[i] + arr[j] + arr[k] < sum.
Example 1
Input: arr = [-2, 0, 1, 3], sum = 2 Output: 2
(−2, 0, 1) and (−2, 0, 3).
Also asked as: Count triplet with sum smaller than a given value
Test cases
Case 1
Input: [-2,0,1,3], 2 Expected: 2
Case 2
Input: [5,1,3,4,7], 12 Expected: 4
Case 3
Input: [1,2,3], 100 Expected: 1
Case 4
Input: [1,2], 5 Expected: 0
View solutionHide solution1 approach
1. Sort + two pointers
Time O(n²)Space O(1)
Fix i; with l = i+1 and r = end, if a[i]+a[l]+a[r] < target then all r−l triplets between l and r qualify — advance l; otherwise decrease r.
function countTriplets(a, target) { a.sort((x, y) => x - y); let count = 0; for (let i = 0; i < a.length - 2; i++) { let l = i + 1, r = a.length - 1; while (l < r) { if (a[i] + a[l] + a[r] < target) { count += r - l; l++; } else r--; } } return count;}