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

Output:

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)