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