How?
Wait I will submit and tell u if it is right or wrong.
Yes this one seems right too.
1 Like
Sorting is predetermining the complexity bound of O(N log(n)).
Suppose if a desired sub-array ends at i. Then we only have to look for no. of times a[i]+k and a[i]-k occurs before i. If the numbers are in range we can create a frequency array, else we can use a HashMap. Either way complexity will be O(n).
EDIT 1: I didn’t read the part less than equal to. Sorry MY bad
1 Like
But how do you query a frequency array range sum in O(1)?
It’s not diff = k, it’s diff < k.
[EDIT]. Lol. Alright.
2 Likes
WA bro
7
11 5 3 2 25 50 1
3
Your : 4
Expected : 12
Yeah i edited my post. Oops i didn’t read it carefully.
Please tell me we just didn’t discuss solution to a live test 
1 Like
Nope not a live contest bro.
“Coding Ninjas”
I already gave test yesterday that Coding ninja wala test . I got 460 out of 500
Cool then 
Let me see
actually we can submit our solution after contest too.
How is answer 12?
Pairs:
1,2
1,3
2,3
3,5
Also i was thinking if sorting is done can’t we use two pointer approach.
First in the sorted array low will represent a starting position and high will represent the number which is just less than or equal to a[low]+k.
All numbers in range [low,high] will make a pair with low.
Each element is also count in subarray too as self-self = 0 <=K
Ok my bad I forgot to take screenshot of explaination -
Bro this is actually I did after sort take two pointers but in worst case it will be N2
Two pointer in sorted array will be O(N).
Okay, so answer.
My code earlier was for difference less than K and not including self.
int index = upper_bound(all(arr),a[i]+k) - arr.begin();
ans += index - i
Complete Code
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
signed main(){
int n,k;
cin >> n;
vector<int> a(n);
for(int &i: a)cin >> i;
cin >> k;
sort(a.begin(),a.end());
long long ans = 0;
for(int i = 0; i < n; ++i){
int index = upper_bound(a.begin(),a.end(),a[i]+k) - a.begin();
ans += index - i;
}
cout << ans;
return 0;
}
3 Likes
This is exactly u did what I thought but some bugs in implementation but in thought of partial marks I apply two pointers. Thanks once again .
1 Like