Print all triplets with sum less than target in an array
Write a function to return the list of all such triplets. How will the time complexity change in this case?
Example 1:
Input: [-1, 0, 2, 3], target=3
Output: [-1, 0, 3], [-1, 0, 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: [-1, 1, 4], [-1, 1, 3], [-1, 1, 2], [-1, 2, 3]
Explanation: There are four triplets whose sum is less than the target:
[-1, 1, 4], [-1, 1, 3], [-1, 1, 2], [-1, 2, 3]
goli202084 Answered question
Below is the Javascript code for the above problem.
Please follow this blog (https://www.golibrary.co/count-all-triplets-with-sum-less-than-target-in-a-given-array/) for detailed explanation on how the below code works
function triplet_with_smaller_sum(arr, target) {
arr.sort((a, b) => a - b);
const triplets = [];
for (i = 0; i < arr.length - 2; i++) {
search_pair(arr, target - arr[i], i, triplets);
}
return triplets;
}
function search_pair(arr, target_sum, first, triplets) {
let left = first + 1,
right = arr.length - 1;
while ((left < right)) {
if (arr[left] + arr[right] < target_sum) { // found the triplet
// since arr[right] >= arr[left], therefore, we can replace arr[right] by any number between
// left and right to get a sum less than the target sum
for (i = right; i > left; i--) {
triplets.push([arr[first], arr[left], arr[i]]);
}
left += 1;
} else {
right -= 1; // we need a pair with a smaller sum
}
}
}
console.log(triplet_with_smaller_sum([-1, 0, 2, 3], 3));
console.log(triplet_with_smaller_sum([-1, 4, 2, 1, 3], 5));
goli202084 Answered question
Write your answer.