### 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

```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))```

`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, ```
```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--) {
}
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).