Pairs with Difference less than K

help
1

Given an array of n integers, We need to find all pairs with difference less than k
image
This is my code but timed out: 5hvQfS - Online C++ Compiler & Debugging Tool - Ideone.com
I need help from everyone, thanks

2

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

3

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

1 Like
4

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

5

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;
}
1 Like
6

I tried this way and failed

7

link to problem ?

8

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:

9

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;
    }
10

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

11

I thank the solution but still not right
image

12

Can u please give question link :slight_smile:

13

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

14

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

1 Like
15

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

16

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

17

I can see how you do it

18

Have u tried my solution ?

1 Like
19

Can you show me your complete solution?

20

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 - Ideone.com

1 Like