Still no time limit, I’m sorry about your solution.
Well, the complexity you told is the most efficient one.
Sorting efficiently will be O(NlogN) anyways.
In case we don’t sort, then we have to use an auto balancing tree (multiset in C++ will work). In that case, we’ll insert all the elements, and then sum up the rank(upper_bound(A[i]+k))-rank(A[i]) using pbds library, which would be O(logN) for each element in worst case i.e. O(NlogN + NlogN) in total.
Hence, O(NlogN + N) is the best among worst case complexities for this problem.
2 Likes
you can refer this one it will provide you how to approach
1 Like
If the above guy can give q. link…then it will be more helpful …as i don’t know how to optimise more , i want to submit the problem at that platform.
this is the optimised version the other approach is to use
binary search …
1 Like
Bro I already mention more optimised approach then GFG , but the guy still got TLE …
I approached and still got timed out
What are the constraints ??
Your ideas are very good, I still look forward to seeing your complete solution
Any constraints???
You can use sliding windows method and do it O(N) time ig.
- Sort the array.(O(log(N))
- Find a window such that first index(start) is 0 and last index is such that arr[last] -arr[start] <= k and last < n(ofcourse) .
- Numer of pairs that can be formed in this window = (Last -start)
- Increment start to start + 1 and increment last such that arr[last] -arr[start] <= k and last < n(ofcourse) .
- Repeat step 3.
- Repeat 4 -5 until start and last become equal to size of array.
- Total time = 2N + logN + C
#include<bits/stdc++.h>
using namespace std ;
int main()
{
int N,K;
cin>>N>>K;
vector arr(N);
for(int i=0 ;i<N;i++)
{
cin>>arr[i];
}
sort(arr.begin(),arr.end());
int value1 = arr[0], value2=0, index1 = 0;
int index2 = 0, i =0 , MAX=0;
while(index2 != N)
{
value2 = value1 + (K);
index2 = lower_bound(arr.begin(),arr.end(),value2)-arr.begin();
MAX= max(MAX,(index2-index1));
index1 = lower_bound(arr.begin(),arr.end(),arr[index1]+1)-arr.begin();
value1 = arr[index1];
}
cout<<MAX<<"\n";
return 0;
}
try this one
1 Like
which soting method is O(log N), really interested to know?
1 Like
what is the complexity of your code?
sorting in log(N) 
what if all elements are same ?
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
then for each i …j will go upto N
its O(N2)
optimal soltn will include binary search
No… Try to understand it will not be n^2 …see internal loop will not iterate n times each…
The best solution is to do a binary search or use upper bound, after sorting the array.
The time complexity will overall be O(N log(N))
Code With Binary Search
//Point to be noted: I haven't checked the code, and compiled it
//It might have a bug, please tell me if it does, I will correct it.
#include <bits/stdc++.h>
using namespace std;
int main() {
//input the array given as input and k
sort(input + 1, input + 1 + n); //indexed 1, and I am using an array, not a vector
long long ans = 0;
for(long long i = 1; i < n; i++) {
if(a[i + 1] - a[i] > k) { //if difference is greater than the next element
continue;
}
if(a[n] - a[i] <= k) { //if difference is smaller than or equal to the greatest element
ans += (n - i);
continue;
}
long long l = i, r = n, mid;
while(l <= r) {
mid = (l + r) / 2;
if(a[mid] <= a[i] + k) {
l = mid + 1;
}
else {
r = mid - 1;
}
}
ans += (l - i);
}
cout << ans << endl;
}
1 Like
It isn’t actually O(N^2), but it is neither O(N). It is kinda in the middle, a bit worse than O(NlogN). But it should do the work 
. It actually depends on the size of the window, which may change the complexity.