Problem

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.

Examples

Example 1:

Input: nums = [10, 3, 4, 5, 2]
Output: 2
Explanation: The surpassers of 3 is 4 and 5, and 10 doesn’t have any surpasser.

Solution

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.

Method 1 - Naive

  • For each element, we examine all elements before it and keep track of numSurpassers as its count of surpassers.
  • If an element is larger, we increment the numSurpassers.
  • Once we’ve processed all elements, the maximum value in numSurpassers is the result.

This approach has a time complexity of O(n^2). How can we make it more efficient?

Method 2 - Divide and Conquer

Note that if the array is sorted in decreasing order, the number of surpassers for position (i) is (i - 1). This suggests a more efficient approach by sorting the array while tracking the original positions of each element. Another key observation is that if we split the array into two halves, both sorted in decreasing order, we can calculate the surpassers for the left partition using the right partition by merging them as follows:

  • If Left[i] < Right[j], then Right[j] is a surpasser for Left[i]. Keep counting surpassers for Left[i] in the right partition while the condition holds for ($q \leq j \leq r$), where (q) is the partition index and (r) is the high-end index.
  • If Left[i] >= Right[j], then elements Right[j..] cannot be surpassers for Left[i]. Update the count of surpassers by adding the accumulated surpassers from the previous step.

This approach consists of three main parts:

  • Divide: Recursively halve the array until each subarray contains one element.
  • Conquer: Solve each subproblem immediately since the number of surpassers for a single element is zero.
  • Accumulate: Merge the two halves while maintaining sorted order and counting surpassers for each element in the left half.

Code

Java
public class SurpassersCount {
    public int maxSurpassers(int[] nums) {
        int n = nums.length;
        int[] surpassers = new int[n];

        mergeSortAndCount(nums, surpassers, 0, n - 1);

        int maxSurpassers = 0;
        for (int count : surpassers) {
            maxSurpassers = Math.max(maxSurpassers, count);
        }

        return maxSurpassers;
    }

    private void mergeSortAndCount(
        int[] nums, int[] surpassers, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            mergeSortAndCount(nums, surpassers, left, mid);
            mergeSortAndCount(nums, surpassers, mid + 1, right);

            mergeAndCount(nums, surpassers, left, mid, right);
        }
    }

    private void mergeAndCount(
        int[] nums, int[] surpassers, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; i++) {
            L[i] = nums[left + i];
        }
        for (int i = 0; i < n2; i++) {
            R[i] = nums[mid + 1 + i];
        }

        int i = 0, j = 0, k = left;
        int count = 0;

        while (i < n1 && j < n2) {
            if (L[i] > R[j]) {
                count++;
                nums[k] = L[i];
                surpassers[left + i] += count;
                i++;
            } else {
                nums[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            nums[k] = L[i];
            surpassers[left + i] += count;
            i++;
            k++;
        }

        while (j < n2) {
            nums[k] = R[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] nums = {10, 3, 4, 5, 2};
        System.out.println("Maximum number of surpassers: "
            + maxSurpassers(nums)); // Output should be 3
    }
}

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(n)

Dry Run

Let’s dry run the example nums = {4, 3, 5, 1, 2}:

  1. Split into {4, 3, 5} and {1, 2}.
  2. Split {4, 3, 5} into {4} and {3, 5}.
  3. Split {3, 5} into {3} and {5}.
  4. Merge {3} and {5}:
    • 3 has no surpassers from {5}.
    • Array becomes {3, 5}.
  5. Merge {4} and {3, 5}:
    • 4 has 1 surpasser from {5} (total so far is 1).
    • Array becomes {3, 4, 5}.
  6. Split {1, 2} into {1} and {2} and merge:
    • 1 has 1 surpasser from {2}.
    • Array becomes {1, 2}.
  7. Merge {3, 4, 5} and {1, 2}:
    • 3 has 2 surpassers (4 is counted later).
    • 4 has 1 surpasser.
    • Array becomes {1, 2, 3, 4, 5}.

The maximum number of surpassers is 3 (for the element 4).