Given an array of n integers, We need to find all pairs with difference less than k

This is my code but timed out: 5hvQfS - Online C++ Compiler & Debugging Tool - Ideone.com

I need help from everyone, thanks

Sort the array and start finding difference. If difference gets greater than k then break and start for next i. This is also O(n^2) but it is faster than yours

you can do binary search to find the element greater and hence making it nlogn

I don’t understand that idea, can you say it clearly?

After Sorting u can do in O(N) with two pointer -

```
int countPairs(int a[], int n, int k)
{
// to sort the array.
sort(a, a + n);
int res = 0;
int j=0;
for (int i = 0; i < n; i++) {
while (j < n && a[j] - a[i] < k) {
j++;
}
// Add all pairs (a[i],a[i+1]),(a[i],a[i+2]),...,(a[i],a[j])
// Number of above pairs = j-i-1
res += j-i-1;
}
return res;
}
```

I tried this way and failed

link to problem ?

I think better than this approach is quite impossible …but yeah if anyone have some another approach better than O(nlogn + n) then tell us

There’s already an efficient approach in this article

You can improve your code like this-

```
int fun(int arr[],int size,int k){
sort(arr,arr+size);
int count 0;
for (int i=0; i<size; i++) {
int j = i+1;
while (j < size && a[j] - a[i] < k) {
count++;
j++;
}
}
return count;
}
```

This is O(N^2) …while my code is O(N) [after sorting]

I thank the solution but still not right

Can u please give question link

Sorry to not give you the link because this is the grading system of my teacher

Yes, worst TL is O(n^2). We can use binary search to reduce the complexity I guess.

I hope you guys can help me complete this article, thank you

are bhai mera code worst case me O(N) hai see carefully .

I can see how you do it

Have u tried my solution ?

Can you show me your complete solution?

Trythis if it will not pass then i don’t know hot to do with more optimization y7Tvuj - Online C++0x Compiler & Debugging Tool - Ideone.com