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

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) {
j++;
}
// Number of above pairs = j-i-1
res += j-i-1;
}
return res;
}``````
1 Like

I tried this way and failed

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

1 Like

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 ?

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 y7Tvuj - Online C++0x Compiler & Debugging Tool - Ideone.com

1 Like