### Problem Statement

Given an array of unsorted numbers and a range [a, b], find total number of triplets in it that add up int the range a to b, such that a <= sum <= b.

### Example:

```Input: arr: [0, -1, -3, 2, 7], a = 6, b = 9
Output: 4
Explanation: Only triplets having sum greater than or equal to 6 and less than or equal to 9 are [-3, 2, 7], [-1, 0, 7], [-1, 2, 7] and [0, 2, 7].```

### Code

```import java.util.*;

class Innoskrit {

public static int countRangeTriplets(int[] arr, int a, int b) {
Arrays.sort(arr);
return countTriplets(arr, b) - countTriplets(arr, a - 1);
}

public static int countTriplets(int[] arr, int target) {

int res = 0;
int n = arr.length;

for(int i = 0; i < n - 2; i++) {
res += countTripletsUtil(arr, i, i + 1, n, target);
}

return res;
}

private static int countTripletsUtil(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[] {0, -1, -3, 2, 7};
int a = 6, b = 9;
System.out.println(Innoskrit.countRangeTriplets(arr, a, b));

}
}```
```#include<bits/stdc++.h>
using namespace std;

class Innoskrit {

public:

static int countRangeTriplets(vector<int> &arr, int a, int b) {
sort(arr.begin(), arr.end());
return countTriplets(arr, b) - countTriplets(arr, a - 1);
}

private:

static int countTriplets(vector<int> &arr, int target) {

int res = 0;
int n = arr.size();

for(int i = 0; i < n - 2; i++) {
res += countTripletsUtil(arr, i, i + 1, n, target);
}
return res;
}

static int countTripletsUtil(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 = {0, -1, -3, 2, 7};
int a = 6, b = 9;
cout << Innoskrit::countRangeTriplets(arr, a, b);

}```
```class Innoskrit:

@staticmethod
def count_range_triplets(arr, a, b):
arr.sort()
return Innoskrit.count_triplets(arr, b) - Innoskrit.count_triplets(arr, a - 1)

@staticmethod
def count_triplets(arr, target):

res, n = 0, len(arr)

for i in range(0, n-1):
res += Innoskrit.count_triplets_util(arr, i, i + 1, n, target)

return res

@staticmethod
def count_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 = [0, -1, -3, 2, 7]
a, b = 6, 9
print(Innoskrit.count_range_triplets(arr, a, b))```

`4`

### 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 “a – 1” and then smaller then “b”, and this whole process will take O(N2) time. Hence, the final time complexity is O(N2).

Space Complexity: O(1)