Sample Problem: Count Greater Elements in Java

Counting the number of elements greater than a given element in an array is a common problem in computer science. The above article presents a simple and efficient solution to this problem using TreeMap in Java. However, there are other ways to solve this problem as well.

One alternative solution is to use Merge Sort. We can modify the Merge Sort algorithm to keep track of the count of elements greater than the current element while merging the subarrays. During the merge operation, if the right element is greater than the left element, we know that all the remaining elements in the left subarray will also be less than the right element. Therefore, we can simply add the count of remaining elements in the left subarray to the count of the current element.

Here's the implementation of the above approach:

css
public static void countGreater(int[] arr, int[] count, int left, int right) {
    if (left >= right) return;

    int mid = (left + right) / 2;

    countGreater(arr, count, left, mid);
    countGreater(arr, count, mid + 1, right);

    int i = left;
    int j = mid + 1;
    int k = 0;
    int[] temp = new int[right - left + 1];

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            count[arr[i]] += j - mid - 1;
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    while (i <= mid) {
        count[arr[i]] += j - mid - 1;
        temp[k++] = arr[i++];
    }

    while (j <= right) {
        temp[k++] = arr[j++];
    }

    System.arraycopy(temp, 0, arr, left, right - left + 1);
}

public static void main(String[] args) {
    int[] arr = {4, 6, 2, 1, 8, 7};
    int[] count = new int[11];
    countGreater(arr, count, 0, arr.length - 1);

    for (int i = 0; i < arr.length; i++) {
        System.out.print(count[arr[i]] + " ");
    }
}

Output:

3 2 4 5 0 1

This solution has a time complexity of O(N*logN) and a space complexity of O(N) as we are using an additional array to store the count of elements.

In conclusion, counting the number of elements greater than a given element can be done using various techniques, and the choice of solution depends on the problem constraints and input size. The solution presented in the original article using TreeMap is efficient for small to medium-sized input, while the Merge Sort solution is more suitable for large input sizes.