Max Surpasser

For an array of integers, a surpasser of an integer element is an element on its right hand side that is larger than it. Given an array of integers, Output the max number of surpassers.

For example, {10,3,4,5,2}, the surpassers of 3 is 4 and 5, and 10 doesn’t have any surpasser.

Basically, we need to get the number of surpassers of every element and finally output the max of them. For example, The max number of surpassers for {10,3,4,5,2} is 2 as 3 has 2 surpassers.

Trivial solution would be,

• For every element, we scan all elements behind it and maintain a ns as its number of surpassers.
• If one element is larger, then we increase the ns.
• After we finish on all elements, the max of all the nses is what we are looking for.

This is O(n^2) solution. How can we improve? Note that if the array is sorted in decreasing order than number of surpassers for position i = i-1. This signals us that we can do better by sorting the array while saving the position of each element in the original array. Also, another important observation is that if we split the array into two halves such that both halves are sorted in decreasing order then we can compute left partitions surpassers by using solution of right partition by merging them in the following way –

• Left[i] < Right[j]: then Right[j] is a surpasser for Left[i]. We can keep accumulate number of surpassers for Left[i] on the right partition as long as the condition is valid for q<=j<=r , where q is the partition index and r in the high end index.
• Left[i] >= Right[j]: then Right[j..] can’t be part of the surpasser for Left[i]. So, we can update number of surpassers by adding the accumulated surpasser in the previous step.

Essentially there are three parts of this approach –

• Divide: We can keep halving the array recursively until we see one element.
• Conquer: We get each of the subproblems of one element and solve it right away because we know that number of surpasser for these smallest subproblem (i.e. with only one element) is 0.
• Accumulate: Now, we accumulate results from the conquered i.e. solved subproblems. We accumulate by merging as described previously.

How to implement the approach? We might have already figured out this sounds like a merge sort. It is indeed exactly merge sort in decreasing order while maintaining the surpasser. Following is a simple Merge Sort modification which sorts the given array “A” in decreasing order, but in spite of modifying given array it modifies the an array of indexes “rank”, which allows to track surpassers in the third array “surp”.
Time: O(n log n).
Space: O(n).

public static class MaxSurpasser {
    int[] A, rank, surp, mergedRank;

    private MaxSurpasser(int[] a) {
        this.A = a;
        this.rank = new int[a.length];
        this.surp = new int[a.length];
        this.mergedRank = new int[a.length];
        for (int i = 0; i < rank.length; i++){
            rank[i] = i;
        }
    }

    public static int find(int[] a) {
        return new MaxSurpasser(a).sort();
    }

    private int sort() {
        mergeSort(0, A.length - 1);
        int max = 0;
        System.out.print("bigger on rights count: ");
        for (int i = 0; i < A.length; i++) {
        	System.out.print(surp[i]+", ");
            if (surp[i] > max) {
                max = surp[i];
            }
        }
        System.out.println();
        return max;
    }

    private void mergeSort(int l, int r) {
        if (l >= r) {
            return;
        }
        //divide
        int q = (l + r) / 2;
        mergeSort(l, q);
        mergeSort(q + 1, r);
        //conquer
        int i = l;
        int j = q + 1; int acc = 0;
        //accumulate through merge
        for (int s = l; s <= r; s++) {
        	if (j <= r && (i > q || A[rank[i]] < A[rank[j]])){
                mergedRank[s] = rank[j];
                acc++;
                j++;
            }
        	else{
        		mergedRank[s] = rank[i];
                surp[rank[i]] += acc;
                i++;
        	}
        }
        for (int s = l; s <= r; s++) {
            rank[s] = mergedRank[s];
        }
    }
}