Problem Statement
Given an array of unsorted numbers and an integer target, find total number of triplets in it that add up to smaller than target.
Example:
Input: arr: [-1, 2, 3, 0], target = 3 Output: 2 Explanation: There are only two triplets with sum less than 3, [-1, 0, -3] and [-1, 0, 2]
Code
Java
C++
Python
class Innoskrit {
public static int findTriplets(int[] arr, int target) {
Arrays.sort(arr);
int res = 0;
int n = arr.length;
for(int i = 0; i < n - 2; i++) {
res += findTripletsUtil(arr, i, i + 1, n, target);
}
return res;
}
private static int findTripletsUtil(int[] arr, int i, int low, int n,
int target) {
int high = n - 1, res = 0;
while(low < high) {
int sum = arr[i] + arr[low] + arr[high];
if(sum < target) {
res += (high - low);
low++;
} else {
high--;
}
}
return res;
}
public static void main(String[] args) {
int arr[] = new int[] {-1, 2, 3, 0};
int target = 3;
System.out.println(Innoskrit.findTriplets(arr, target));
}
}
#include<bits/stdc++.h>
using namespace std;
class Innoskrit {
public:
static int findTriplets(vector<int> &arr, int target) {
sort(arr.begin(), arr.end());
int res = 0;
int n = arr.size();
for(int i = 0; i < n - 2; i++) {
res += findTripletsUtil(arr, i, i + 1, n, target);
}
return res;
}
private:
static int findTripletsUtil(vector<int> &arr, int i, int low, int n,
int target) {
int high = n - 1;
int res = 0;
while(low < high) {
int sum = arr[i] + arr[low] + arr[high];
if(sum < target) {
res += (high - low);
low++;
} else {
high--;
}
}
return res;
}
};
int main() {
vector<int> arr = {-1, 2, 3, 0};
int target = 3;
cout << Innoskrit::findTriplets(arr, target);
}
class Innoskrit:
@staticmethod
def find_triplets(arr, target):
arr.sort()
res, n = 0, len(arr)
for i in range(0, n-1):
res += Innoskrit.find_triplets_util(arr, i, i + 1, n, target)
return res
@staticmethod
def find_triplets_util(arr, i, low, n, target):
high, res = n - 1, 0
while low < high:
sum = arr[i] + arr[low] + arr[high]
if sum < target:
res += (high - low)
low += 1
else:
high -= 1
return res
if __name__ == '__main__':
arr = [-1, 2, 3, 0]
target = 3
print(Innoskrit.find_triplets(arr, target))
Output:
2
Time and Space Complexity
Time Complexity: O(N2)
Sorting the array will take O(n log n) and while finding the triplets, for each element we are finding the pair in a sorted array which will add to element giving sum smaller than target and this whole process will take O(N2) time. Hence, the final time complexity is O(N2).
Space Complexity: O(1)
Slight Modification to the Problem:
Given an array of unsorted numbers and an integer target, find triplets in it that add up to smaller than target and return list of Triplets.
Example:
Input: arr: [-1, 2, 3, 0], target = 3 Output: [[-1, 0, -3], [-1, 0, 2]] Explanation: There are only two triplets with sum less than 3,
Java
C++
Python
import java.util.*;
class Innoskrit {
public static List<List<Integer>> findTriplets(int[] arr, int target) {
Arrays.sort(arr);
List<List<Integer>> res = new ArrayList<>();
int n = arr.length;
for(int i = 0; i < n - 2; i++) {
findTripletsUtil(arr, i, i + 1, n, target, res);
}
return res;
}
private static List<List<Integer>> findTripletsUtil(int[] arr, int i, int low, int n,
int target, List<List<Integer>> res) {
int high = n - 1;
while(low < high) {
int sum = arr[i] + arr[low] + arr[high];
if(sum < target) {
for(int x = high; x > low; x--) {
res.add(Arrays.asList(arr[i], arr[low], arr[x]));
}
low++;
} else {
high--;
}
}
return res;
}
public static void main(String[] args) {
int arr[] = new int[] {-1, 2, 3, 0};
int target = 3;
System.out.println(Innoskrit.findTriplets(arr, target));
}
}
#include<bits/stdc++.h>
using namespace std;
class Innoskrit {
public:
static vector<vector<int>> findTriplets(vector<int> &arr, int target) {
sort(arr.begin(), arr.end());
vector<vector<int>> res;
int n = arr.size();
for(int i = 0; i < n - 2; i++) {
findTripletsUtil(arr, i, i + 1, n, target, res);
}
return res;
}
private:
static vector<vector<int>> findTripletsUtil(vector<int> &arr, int i, int low, int n,
int target, vector<vector<int>> &res) {
int high = n - 1;
while(low < high) {
int sum = arr[i] + arr[low] + arr[high];
if(sum < target) {
for(int x = high; x > low; x--) {
res.push_back({arr[i], arr[low], arr[x]});
}
low++;
} else {
high--;
}
}
return res;
}
};
// Just for printing
void printResult(vector<vector<int>> &ans) {
cout<<"[";
for(int i = 0; i < ans.size(); i++) {
cout<<"[";
for(int j = 0; j < ans[i].size(); j++) {
if(j != ans[i].size() - 1) {
cout<<ans[i][j]<<", ";
} else {
cout<<ans[i][j];
}
}
if(i != ans.size() - 1)
cout<<"], ";
else
cout<<"]";
}
cout<<"]\n";
}
int main() {
vector<int> arr = {-1, 2, 3, 0};
int target = 3;
vector<vector<int>> res = Innoskrit::findTriplets(arr, target);
printResult(res);
}
class Innoskrit:
@staticmethod
def find_triplets(arr, target):
arr.sort()
res, n = [], len(arr)
for i in range(0, n-1):
Innoskrit.find_triplets_util(arr, i, i + 1, n, target, res)
return res
@staticmethod
def find_triplets_util(arr, i, low, n, target, res):
high = n - 1
while low < high:
sum = arr[i] + arr[low] + arr[high]
if sum < target:
for x in range(high, low, -1):
res.append([arr[i], arr[low], arr[x]])
low += 1
else:
high -= 1
return res
if __name__ == '__main__':
arr = [-1, 2, 3, 0]
target = 3
print(Innoskrit.find_triplets(arr, target))
Output:
[[-1, 0, 3], [-1, 0, 2]]
Time and Space Complexity
Time Complexity: O(N2)
Sorting the array will take O(n log n) and while finding the triplets, for each element we are finding the pair in a sorted array which will add to element giving sum smaller than target and this whole process will take O(N2) time. Hence, the final time complexity is O(N2).
Space Complexity: Ignoring the size of the output array, O(1).