Binary Search solution for Max Number of Surpassers

Question

For an array of integers, a surpasser of an integer element is an element on its right hand side that is larger than it.

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

So the Max Number of Surpassers problem is

Given an array of integers

Out put the max number of surpassers

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.

---

I am wondering whether there is a O(nLogn) solution exists where binary search is used.

I got this question because the chapter 2 in the book Pearls of Functional Algorithm Design says:

In this pearl we solve a small programming exercise of Martin Rem (1988a). While Rem’s solution uses binary search, our solution is another application of divide and conquer.

Though I got the functional solution, I can't think of a binary search one for arrays.

Any ideas?

Answer 1

Solution 1

I don't know if this is the same as Rem's solution, but you could solve this quite easily with a binary search tree.

Initialize an empty binary search tree and then iterate in reverse order through the array.

Insert each element in the binary search tree and then perform a count of all the elements in the tree above the value of the element. (If each subtree stores the number of elements it contains, then these operations can both be done in O(logn) if an appropriate balanced tree is used.)

The max number of successors is given by the largest count observed.

Solution 2

A potentially faster solution with a similar basic idea is to use a binary indexed tree (aka Fenwick tree) to store the elements. This data structure can be accessed to retrieve the number of elements above a given value so can be used in the same way as the binary search tree in solution 1.

This will have the same O(nlogn) complexity as solution 1, but may be faster in practice as it has a smaller memory footprint.

Answer 2

Here's one solution which uses binary search, but I don't suppose it's what you're looking for (binary search is not the main technique used in the algorithm). Most of the work for this solution is done by a combination of sorting and a Fenwick tree. The binary search component can probably be replaced by a hash map or a binary search tree.

Anyway, here is the code. Let me know if you have any questions:

import java.util.Arrays;

public class MaxSurpassersFenwick {
    public static void main(String[] args) {
        // The number of surpassers for a value is the number of values to the right and bigger.
        // The number of surpassers for { 2, 7, 5, 5, 2, 7, 0, 8, 1 } are { 5, 1, 2, 2, 2, 1, 2, 0, 0 }.
        // The max number of surpassers is thus 5.
        // The code I have written runs in O(n lg n) time.

        int[] values = new int[] { 2, 7, 5, 5, 2, 7, 0, 8, 1 };

        System.out.println("The max number of surpassers for any value in " + Arrays.toString(values) + " is " + getMaxNumSurpassers(values) + ".");
    }

    public static int getMaxNumSurpassers(int[] values) {
        if (values == null) {
            throw new IllegalArgumentException("Array of values cannot be null!");
        }

        int n = values.length;

        if (n <= 1) {
            return 0;
        }

        int[] numSurpassers = getNumSurpassers(values);
        int maxNumSurpassers = numSurpassers[0];

        for (int i = 1; i < n; ++i) {
            maxNumSurpassers = Math.max(maxNumSurpassers, numSurpassers[i]);
        }

        return maxNumSurpassers;
    }

    public static int[] getNumSurpassers(int[] values) {
        if (values == null) {
            throw new IllegalArgumentException("Array of values cannot be null!");
        }

        int n = values.length;
        int[] sortedValues = values.clone();
        FenwickTree numValues = new FenwickTree(n);
        int[] numSurpassers = new int[n];

        Arrays.sort(sortedValues);

        // Iterate through the values from right to left
        for (int i = n - 1; i >= 0; --i) {
            // Find the index of the current value in the sorted array of values
            // If the value occurs more than once, return the last index for that value
            int lastOccurrenceIndex = binarySearchLastOccurrence(sortedValues, values[i]);

            // Count the number of values we've seen that are greater than the current value
            numSurpassers[i] = numValues.sum(lastOccurrenceIndex + 1, n - 1);

            // Mark the current value as seen
            numValues.add(lastOccurrenceIndex, 1);
        }

        return numSurpassers;
    }

    private static int binarySearchLastOccurrence(int[] values, int valueToFind) {
        int low = 0;
        int high = values.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (mid == high || (values[mid] == valueToFind && values[mid] < values[mid + 1])) {
                return mid;
            } else if (values[mid] > valueToFind) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return -1;
    }

    private static class FenwickTree {
        private int size;
        private int[] values;

        public FenwickTree(int size) {
            this.size = size;
            this.values = new int[size];
        }

        public void add(int index, int value) {
            while (index < this.size) {
                this.values[index] += value;
                index |= index + 1;
            }
        }

        public int prefixSum(int index) {
            int sum = 0;
            int n = index + 1;

            while (n > 0) {
                sum += this.values[n - 1];
                n &= n - 1;
            }

            return sum;
        }

        public int sum(int leftIndex, int rightIndex) {
            if (leftIndex > rightIndex) {
                return 0;
            }

            int rightSum = this.prefixSum(rightIndex);
            int leftSum = (leftIndex > 0) ? this.prefixSum(leftIndex - 1) : 0;

            return (rightSum - leftSum);
        }
    }
}