Count all triplets with sum less than target in a given array
Problem Statement
Given an array arr of unsorted numbers and a target sum, count all triplets in it such that arr[i]+arr[j]+arr[k] < target where i , j , and k are three different indices. Write a function to return the count of such triplets.
Example 1: Input: [-1, 0, 2, 3], target=3 Output: 2 Explanation: There are two triplets whose sum is less than the target: [-1, 0, 3], [-1, 0, 2] Example 2: Input: [-1, 4, 2, 1, 3], target=5 Output: 4 Explanation: There are four triplets whose sum is less than the target: [-1, 1, 4], [-1, 1, 3], [-1, 1, 2], [-1, 2, 3]
Solution
This problem follows the Two Pointers pattern (similar to binary search) and shares similarities with Triplet Sum to Zero problem. The only difference is that, in this problem, we need to find the triplets whose sum is less than the given target. To meet the condition i!=j!=k, in the triplet, we need to make sure that each number is not used more than once.
Following a similar approach, first we can sort the array and then iterate through it, taking one number at a time. Let’s say during our iteration we are at number ‘X’, so we need to find ‘Y’ and ‘Z’ such that X + Y + Z < target. At this stage, our problem translates into finding a pair whose sum is less than “$ target – X$” (as from the above equation Y + Z == target – X). We can use a similar approach as discussed in Triplet Sum to Zero problem.
In the loop, we are essentially finding the min and max range of low and high index values for Y and Z where X+Y+Z < target and thus, to count the number of triplets, we add the difference between high and low indices to count i.e. count += high – low;
Javascript code below:-
<script>
function triplet_with_smaller_sum(arr, target) {
// TODO: Write your code here
let count = 0;
arr.sort((a,b)=>a-b);
for (var index = 0; index < arr.length; index++) {
count += search_pair(arr, target - arr[index], index);
}
return count;
};
function search_pair(arr, target, index) {
var low = index + 1,
high = arr.length - 1,
count = 0;
while (low < high) {
if (arr[low] + arr[high] < target) {
count += high - low;
console.log(low, high, arr[low], arr[high], target);
low++;
} else {
high--;
}
}
return count;
}
document.write(triplet_with_smaller_sum([-1, 0, 2, 3], 3)+'<br/>');
document.write(triplet_with_smaller_sum([-1, 4, 2, 1, 3], 5)+'<br/>');
</script>
Time complexity
Sorting the array will take O(N * logN). The search_pair() will take O(N). So, overall triplet_with_smaller_sum() will take O(N * logN + N^2), which is asymptotically equivalent to O(N^2).
Space complexity
Ignoring the space required for the output array, the space complexity of the above algorithm will be O(N) which is required for sorting if we are not using an in-place sorting algorithm.
Comments
