Why am I getting TLE in this ques ?
Priyansh Dubey
48

Given an array A[] of n elements and an integer k. The task is to find the number of triplet (x, y, k), where 0 <= x, y, k < n and x, y, k are the index in the array A[] such that:
|A[x] – A[y]| <= k
|A[y] – A[z]| <= k
|A[z] – A[x]| <= k

I got this ques in one of the online assessment.
I have written the following code but I got TLE for 5 test cases. How could I had optimize my code ?

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

int lower_bound(int value, vector<int> arr, int n) 
{ 
	int lo= 0; 
	int hi = n - 1; 
	int ans = -1; 
	int mid; 

	while (lo <= hi) { 
		mid = (lo + hi) / 2; 
		if (arr[mid] >= value) { 
			hi = mid - 1; 
			ans = mid; 
		} 
		else { 
			lo = mid + 1; 
		} 
	} 
	return ans; 
} 

int countTriplet(vector<int> arr, int k) 
{ 
	int count = 0; 
	sort(arr.begin(),arr.end()); 
    int n= arr.size();
	for (int i = 2; i < n; i++) { 
		
		int cur = lower_bound(arr[i] - k, arr, n); 
		
	   if (cur <= i - 2) { 
	   
			count += ((i - cur) * (i - cur - 1)) / 2;  // (i-cur) C 2
		} 
	} 
	return count; 
}
Comments (1)