Find an algorithm which solves the following problem

Question

I have a problem like this:

we have an array of elements like this :

(a0,b0)
(a1,b1)
.
.
.
(an,bn)

and I wanna find the number of elements which have one of this two condition:

1) if ai>aj and bi<bj then:count:=count+1

or

2)if ai<aj and bi>bj then:count:=count+1

I've already found an algorithm that is O(n^2), but I need the faster algorithm

Example: suppose we have this:

(1,5)
(4,7)
(8,2)

I wanna find the number of time that condition satisfied, so 1<8 and 2<5 so condition is satisfied but 1<4 and 5<7 so condition is not satisfied.

Answer 1

This can be accomplished by divide-and-conquer, and if done well (essentially, avoiding multiple sorts by using merge in each pass), this will be $O(n\cdot \log{n})$. Throughout this solution it is helpful to imagine these tuples as points on a $2D$ Cartesian plane which $a_i$s being the horizontal $x$-coordinate and $b_i$s being the vertical $y$-coordinates: thus the left/right notions refer to comparisons in $a_i$s while upper/lower notions refer to comparisons in $b_i$s.

This is a recursive solution, here is the pseudocode:

function numpair(array_sorted_by_ai):
    N = length(array_sorted_by_ai)
    // base case: for N=1, we have 0 pairs and already bi-sorted array
    if N == 1:
        return (0, array_sorted_by_ai)

    // call for left & right partitions: get intra-partition pairs &
    // the bi-sorted subarrays for these partitions
    leftans,  left_sorted_by_bi  = numpair(array_sorted_by_ai[0 → N/2])
    rightans, right_sorted_by_bi = numpair(array_sorted_by_ai[N/2 → N])

    // Now find cross partition pairs and do two-pointer merge of 
    // bi-sorted subarrays to get the bi-sorted parent array
    crossans = 0, leftidx = 0, rightidx = 0
    oldpoints = 0
    array_sorted_by_bi = [] // We will return the input array sorted by bi's

    while length(array_sorted_by_bi) < N:
        // The right one's bi is lower (i.e. a potential pair)
        if left_sorted_by_bi[leftidx][1] > right_sorted_by_bi[rightidx][1]:
            // Must also check that the right one's ai is strictly bigger
            if left_sorted_by_bi[leftidx][0] < right_sorted_by_bi[rightidx][0]:
                crossans = crossans + oldpoints + 1
            // Try to up the lower side (right) pointer unless impossible
            if rightidx < length(right_sorted_by_bi):
                array_sorted_by_bi += [right_sorted_by_bi[rightidx]]
                rightidx = rightidx + 1
                oldpoints = 0
            else:
                array_sorted_by_bi += [left_sorted_by_bi[leftidx]]
                leftidx = leftidx + 1
                oldpoints = rightidx
        // The left one is lower (not a valid pair)
        else:
            // Try to up the lower (left) side pointer unless impossible
            if leftidx < length(left_sorted_by_bi):
                array_sorted_by_bi += [left_sorted_by_bi[leftidx]]
                leftidx = leftidx + 1
                oldpoints = rightidx
            else:
                array_sorted_by_bi += [right_sorted_by_bi[rightidx]]
                rightidx = rightidx + 1
                oldpoints = 0
    // pairs on left, right and cross-partition, bi-sorted input array
    return (leftans+rightans+crossans, right_sorted_by_bi)

Explanation:

1. We first sort our array by the $a_i$s and call $numpair()$ with this sorted array. The recursive function calls the left and right halves of this array in turn and thus gets the number of pairs where both members lie on the left or on the right. These calls also return the left and right subarrays (which we passed sorted by $a_i$s), now sorted by $b_i$s

2. Now we run a merge sequence for these returned $b_i$-sorted subarrays while now also counting pairs that have one member in the left and one in the right. We use a two pointer method: we keep each pointer on left and right at their lowest values (by $b_i$s) and increment the one which has the lower $b_i$ between the two. At any time we see the left point at greater $b_i$ than the right one, we increment our cross-pairs count. Now here comes a little twist: we actually increment every time by a quantity $oldpoints+1$. Here is why:

   • If the previous update was on the left, it means that it is a new point suitable for making pairs for all previous points encountered below its $b_i$ on the right (including the current one), i.e. an increment by $rightidx+1$ is needed. So whenever we update on the left, we make $oldpoints$ equal to $rightidx$, so that if this scenario arises in the following iteration, pairs from all older points encountered in the right are added for this newly eligible point on the left.
   • If the previous update was on the right, then the left point is not new and has already been considered for all lower points in the right previously. So only an increment for the current right point (i.e. by 1) is needed. So whenever we update on the right, we make $oldpoints$ equal to $0$, so that if this scenario arises in the following iteration, we only add one more new pair for just the current point on the right

3. At the end we return the total number of pairs we counted on the left and right (by recursion) and the cross-partition pairs we counted via the merge sequence as the total number of pairs and also return the input array sorted by $b_i$s to tie up the recursion. The first element we returned is the actual answer.

Time Complexity:

Denote this as a function of input size $n$ as $T(n)$ and observe that the merge process is $O(n)$. So for the function, complexity: $$T(n) = 2T(n / 2) + O(n)$$ This, as we know (just like in merge sort) resolves to $O(n\cdot \log{n})$. And this doesn't change when you count the initial sort by $a_i$s, we do on the parent array before calling the function. So yeah, a properly designed divide-and-conquer achieves this in $O(n\cdot \log{n})$