Pairs with Difference less than K

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

1 Like

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) {
// 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;
1 Like

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 :slight_smile:

There’s already an efficient approach in this article
You can improve your code like this-

int fun(int arr[],int size,int k){
        int count 0; 
        for (int i=0; i<size; i++) { 
            int j = i+1;  
            while (j < size && a[j] - a[i] < k) { 
      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 :slight_smile:

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.

1 Like

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

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

I can see how you do it

Have u tried my solution ?

1 Like

Can you show me your complete solution?

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

1 Like