Find number of pairs (A[i], A[j]) such that A[i] <= A[j] c, i < j (c is given constant). [O(-CodePudding

O(N^2) solution is not accepted so brute force cannot be applied.

I am stuck and can't think of any other algorithm.

I thought of applying binary search but the array is not sorted and we need the original indices for the condition i < j.

Can we use inversion count concept here? (I have seen it used for A[i]>2*A[j] but will it work for this question?)

Please help.

CodePudding user response：

I guess you could use a variant of merge sort here.
Given an array A[0...n/2...n-1], let us divide it into two parts left and right.
Left is A[0...n/2-1]
Right is A[n/2...n]

Now calculate the no. of such pairs in left & right arrays using function f(array) which also sorts the array
Now we called f on "Left" and we got no. of such pairs in left with left array sorted. Similarly for the right one.

Now given these two parts, how will you find no of such required pairs in A? We have count for "Left" & "Right", and now just need to find pairs (x, y) such that x is in Left; y is in Right; x <= y c.
Remember that we already called this function on left & right so elements are sorted. Now just write modified merge of those two arrays which in-addition to sorting also counts no. of such pairs by maintaining index in left array which has not seen any left[index] <= y c for elements y in right.

Implementation

public (int, int[]) merge(int[] arr, int c){
        lanswer, left = merge(left);
        ranswer, right = merge(right);
        
        int lsize = left.length;
        int rsize = right.length;

        int p = 0; // left index
        int q = 0; // right index
        int r = 0; // combined index
        int lIndex = 0; // least index in left array for which left[lIndex] > right[q]   c

        int answer = lanswer   ranswer;

        while(p < lsize && q < rsize){

            if(left[p] >= right[q]){
                arr[r] = left[p];
                r  = 1;
                p  = 1;
            }
            else{
                while(right[q] >= left[lIndex] - c){
                    answer  = (rsize - q);
                    lIndex  = 1;
                }
                arr[r] = right[q];
                q  = 1;
                r  = 1;
            }
        }

        while(p < lsize){
            arr[r] = left[p];
            r  = 1;
            p  = 1;
        }

        while(q < rsize){
            while(right[q] >= left[lIndex] - c){
                answer  = (rsize - q);
                lIndex  = 1;
            }
            arr[r] = right[q];
            q  = 1;
            r  = 1;
        }
        
        return (answer, arr);

    }

CodePudding user response：

Here is another solution:

Use a balanced tree, e.g. AVL tree. Additionally you store the number of nodes in the sub tree for each edge. Now you can just go backwards through the array and find the number of nodes <= A[i] - c in O(logn). This is the count for A[i]. Then add A[i] to the tree and proceed.