Count triplets with sum smaller than a given value

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}