☕ DSA Java Articles

Topics › Stacks and Queues › Monotonic Stack/Queue Problems [VVV. Imp]

Number of Greater Elements to the Right

Easy TUF ID 285 A2Z

Java source ↗ Edit this article ↗

Problem

You are given an array arr of n integers and a list of q query indices. For each query index i, report how many elements to the right of i are strictly greater than arr[i], that is, the number of j > i with arr[j] > arr[i]. Return the answers in query order.

Constraints in the usual version: n ≤ 10^4 and around a hundred queries. We will also handle the case where both n and q are large.

Example 1

arr     = [3, 4, 2, 7, 5, 8, 10, 6]
queries = [0, 5]
answer  = [6, 1]     // right of 3: 4, 7, 5, 8, 10, 6 are all bigger; right of 8: only 10

Example 2

arr     = [1, 2, 3, 4, 1]
queries = [0, 1, 4]
answer  = [3, 2, 0]  // the trailing 1 is not greater than the first 1, and the last index has nothing to its right

Example 3

arr     = [5, 5, 5]
queries = [0, 1, 2]
answer  = [0, 0, 0]  // equal does not count as greater

Why the monotonic stack does not apply here. This problem sits next to the next-greater-element problems, but it is a different kind of question. A monotonic stack works by discarding elements that are hidden behind a closer, bigger one, because only the nearest greater element matters. Here every greater element to the right counts, so nothing can ever be discarded. The right tools are a direct scan for small inputs and an order-statistics structure for large ones.

Approach 1: Brute force per query

Intuition. Each query is independent: walk from i + 1 to the end and count values bigger than arr[i]. With a hundred queries over ten thousand elements this is about 10^6 comparisons, which is instant. This is the expected solution for the stated constraints, and it is worth recognising when the simple method is already good enough.

Algorithm.

  1. For each query index idx:
  2. Set count = 0. For j from idx + 1 to n - 1, increment count when arr[j] > arr[idx].
  3. Store count as the answer for this query.
static int[] bruteForce(int[] arr, int[] queries) {
    int[] res = new int[queries.length];
    for (int k = 0; k < queries.length; k++) {
        int idx = queries[k], count = 0;
        for (int j = idx + 1; j < arr.length; j++) {
            if (arr[j] > arr[idx]) count++;
        }
        res[k] = count;
    }
    return res;
}

Complexity. Time O(n · q): each query may scan almost the whole array. Space O(1) besides the output.

If q grows to n (every index is asked about), this becomes O(n^2), which is too slow for n = 10^5. The fix is to compute the answer for every index at once, faster than n separate scans.

Approach 2: Optimal, Fenwick tree over value ranks

Intuition. Sweep from right to left. When we stand at index i, the elements already passed are exactly the elements to the right of i. If we keep those elements in a structure that can answer “how many of you are ≤ v?” quickly, then

greater(i) = (number of elements to the right) - (how many of them are ≤ arr[i])
           = (n - 1 - i) - countAtMost(arr[i])

and afterwards we insert arr[i] so it is counted for the indices further left.

A Fenwick tree (binary indexed tree) does exactly this: it stores counts per value and answers prefix sums “how many inserted values have rank ≤ r” in O(log m), with O(log m) inserts. The step r & -r isolates the lowest set bit of r; subtracting it walks down the tree for a query, and adding it walks up for an update.

The tree is indexed by value, so values must first be mapped to small positive ranks. Sort a copy of the array, remove duplicates, and the rank of v is its position in that list plus one. This also makes negative and very large values harmless, since only their order matters.

Equal values deserve a second look. countAtMost includes elements equal to arr[i], so they are subtracted out, and only strictly greater elements remain. That is exactly the required strictness.

Algorithm.

  1. Copy arr, sort it, and remove duplicates in place, leaving m distinct values.
  2. Create a Fenwick array tree of size m + 1.
  3. For i from n - 1 down to 0:
    • rank = position of arr[i] among the distinct values, plus one (binary search).
    • notGreater = prefix sum of tree up to rank.
    • greater[i] = (n - 1 - i) - notGreater.
    • Add one at rank.
  4. Answer each query with greater[query].
static int[] optimal(int[] arr, int[] queries) {
    int n = arr.length;
    int[] vals = arr.clone();
    Arrays.sort(vals);
    int m = 0;                                   // number of distinct values, kept in vals[0..m-1]
    for (int i = 0; i < n; i++) {
        if (m == 0 || vals[i] != vals[m - 1]) vals[m++] = vals[i];
    }
    int[] tree = new int[m + 1];                 // 1-based Fenwick tree: how many seen elements have each rank
    int[] greater = new int[n];
    for (int i = n - 1; i >= 0; i--) {
        int rank = Arrays.binarySearch(vals, 0, m, arr[i]) + 1;     // 1..m
        int notGreater = 0;                      // seen elements with rank <= rank
        for (int r = rank; r > 0; r -= r & -r) notGreater += tree[r];
        greater[i] = (n - 1 - i) - notGreater;   // everything to the right minus the ones that are not greater
        for (int r = rank; r <= m; r += r & -r) tree[r]++;
    }
    int[] res = new int[queries.length];
    for (int k = 0; k < queries.length; k++) res[k] = greater[queries[k]];
    return res;
}

Dry run on arr = [3, 4, 2, 7, 5, 8, 10, 6]. The distinct sorted values are [2, 3, 4, 5, 6, 7, 8, 10], so ranks are 2→1, 3→2, 4→3, 5→4, 6→5, 7→6, 8→7, 10→8.

i arr[i] rank already seen (right side) seen with rank ≤ rank greater[i]
7 6 5 none 0 0
6 10 8 6 1 0
5 8 7 6, 10 1 1
4 5 4 6, 10, 8 0 3
3 7 6 6, 10, 8, 5 2 2
2 2 1 6, 10, 8, 5, 7 0 5
1 4 3 6, 10, 8, 5, 7, 2 1 5
0 3 2 6, 10, 8, 5, 7, 2, 4 1 6

Queries [0, 5] read greater[0] = 6 and greater[5] = 1, as expected.

Complexity. Time O(n log n + q): sorting is O(n log n), each of the n steps does a binary search, a prefix query and an update in O(log n), and each query is a lookup. Space O(n) for the sorted copy, the tree and the greater array.

Another route. The same counts fall out of a merge sort: while merging, every element of the left half learns how many elements of the right half are bigger than it. That is the technique from Count Inversions, with the comparison flipped. It has the same O(n log n) cost but needs to carry original indices through the sort, which makes the Fenwick version shorter.

Edge cases and pitfalls