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]
Same algorithm implemented in C++
using namespace std; #include <algorithm> #include <iostream> #include <string> #include <vector> class TripletWithSmallerSum { public: static vector<vector<int>> searchTriplets(vector<int> &arr, int target) { sort(arr.begin(), arr.end()); vector<vector<int>> triplets; for (int i = 0; i < arr.size() - 2; i++) { searchPair(arr, target - arr[i], i, triplets); } return triplets; } private: static void searchPair(vector<int> &arr, int targetSum, int first, vector<vector<int>> &triplets) { int left = first + 1, right = arr.size() - 1; while (left < right) { if (arr[left] + arr[right] < targetSum) { // 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 (int i = right; i > left; i--) { triplets.push_back({arr[first], arr[left], arr[i]}); } left++; } else { right--; // we need a pair with a smaller sum } } } }; int main(int argc, char *argv[]) { vector<int> vec = {-1, 0, 2, 3}; auto result = TripletWithSmallerSum::searchTriplets(vec, 3); for (auto vec : result) { cout << "["; for (auto num : vec) { cout << num << " "; } cout << "]"; } cout << endl; vec = {-1, 4, 2, 1, 3}; result = TripletWithSmallerSum::searchTriplets(vec, 5); for (auto vec : result) { cout << "["; for (auto num : vec) { cout << num << " "; } cout << "]"; } }
Python
def triplet_with_smaller_sum(arr, target): arr.sort() triplets = [] for i in range(len(arr)-2): search_pair(arr, target - arr[i], i, triplets) return triplets def search_pair(arr, target_sum, first, triplets): left = first + 1 right = len(arr) - 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 in range(right, left, -1): triplets.append([arr[first], arr[left], arr[i]]) left += 1 else: right -= 1 # we need a pair with a smaller sum def main(): print(triplet_with_smaller_sum([-1, 0, 2, 3], 3)) print(triplet_with_smaller_sum([-1, 4, 2, 1, 3], 5)) main()
JAVA
import java.util.*; class TripletWithSmallerSum { public static List<List<Integer>> searchTriplets(int[] arr, int target) { Arrays.sort(arr); List<List<Integer>> triplets = new ArrayList<>(); for (int i = 0; i < arr.length - 2; i++) { searchPair(arr, target - arr[i], i, triplets); } return triplets; } private static void searchPair(int[] arr, int targetSum, int first, List<List<Integer>> triplets) { int left = first + 1, right = arr.length - 1; while (left < right) { if (arr[left] + arr[right] < targetSum) { // 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 (int i = right; i > left; i--) triplets.add(Arrays.asList(arr[first], arr[left], arr[i])); left++; } else { right--; // we need a pair with a smaller sum } } } public static void main(String[] args) { System.out.println(TripletWithSmallerSum.searchTriplets(new int[] { -1, 0, 2, 3 }, 3)); System.out.println(TripletWithSmallerSum.searchTriplets(new int[] { -1, 4, 2, 1, 3 }, 5)); } }
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));