CODEWITHSUNDEEP
algorithmcounting
typedef
typedef

Reputation: 33

count no. of pairs such that absolute difference is less than K

Given an array A of size N, how do I count the number of pairs(A[i], A[j]) such that the absolute difference between them is less than or equal to K where K is any positive natural number? (i, j<=N and i!=j)

My approach:

  1. Sort the array.

  2. Create another array that stores the absolute difference between two consecutive numbers.

Am I heading in the right direction? If yes, then how do I proceed further?

Upvotes: 1

Views: 3371

Answers (4)

Vikram Bhat
Vikram Bhat

Reputation: 6246

Here is a O(nlogn) algorithm :-

1. sort input
2. traverse the sorted array in ascending order.
3. for A[i] find largest index A[j]<=A[i]+k using binary search.
4. count = count+j-i
5. do 3 to 4 all i's

Time complexity :-

Sorting : O(n)
Binary Search : O(logn)
Overall : O(nlogn)

Upvotes: 2

Abhishek Bansal
Abhishek Bansal

Reputation: 12715

Your approach is partially correct. You first sort the array. Then keep two pointers i and j.

1. Initialize i = 0, j = 1.  
2. Check if A[j] - A[i] <= K.   
   - If yes, then increment j,  
   - else
       - **increase the count of pairs by C(j-i,2)**. 
       - increment i.
       - if i == j, then increment j.  
3. Do this till pointer j goes past the end of the array. Then just add C(j-1,2) to the count and stop.

By i and j, you are basically maintaining a window within which the difference between elements is <= K.

EDIT: This is the basic idea, you will have to check for boundary conditions. Also you will have to keep track of the past interval that was added to the count. You will need to subtract the overlap with the current interval to avoid double counting.

Complexity: O(NlogN), for the sort operation, linear for the array traversal

Upvotes: 1

Paul Hankin
Paul Hankin

Reputation: 58280

Once your array is sorted, you can compute the sum in O(N) time.

Here's some code. The O(N) algorithm is pair_sums, and pair_sums_slow is the obviously correct, but O(N^2) algorithm. I run through some test cases at the end to make sure that the two algorithms returns the same results.

def pair_sums(A, k):
    A.sort()
    counts = 0
    j = 0
    for i in xrange(len(A)):
        while j < len(A) and A[j] - A[i] <= k:
            j+=1
        counts += j - i - 1
    return counts

def pair_sums_slow(A, k):
    counts = 0
    for i in xrange(len(A)):
        for j in xrange(i+1, len(A)):
            if A[j] - A[i] <= k:
                counts+=1
    return counts

cases = [
    ([0, 1, 2, 3, 4, 5], 10),
    ([0, 0, 0, 0, 0], 1),
    ([0, 1, 2, 4, 8, 16], 9),
    ([0, -1, -2, 1, 2], 2)
]

for A, k in cases:
    want = pair_sums_slow(A, k)
    got = pair_sums(A, k)
    if want != got:
        print A, k, want, got

The idea behind pair_sums is that for each i, we find the smallest j such that A[j] - A[i] > K (or j=N). Then j-i-1 is the number of pairs with i as the first value.

Because the array is sorted, j only ever increases as i increases, so the overall complexity is linear since although there's nested loops the inner operation j+=1 can occur at most N times.

Upvotes: 0

perreal
perreal

Reputation: 97978

This is O(n^2):

Sort the array  
For each item_i in array,
  For each item_j in array such that j > i
      If item_j - item_i <= k, print (item_j, item_i)
      Else proceed with the next item_i

Upvotes: 1

Related Questions