Problem

Given an integer array arr of length n, return an array res where res[i] is the number of elements to the right of index i that are strictly greater than arr[i].

Input / Output

• Input: integer array arr.
• Output: integer array res of the same length.

Examples

Example 1 Input: arr = [3, 7, 1, 5, 9] Output: [3, 1, 2, 1, 0] Explanation: Right of 3 → {7, 5, 9} greater; right of 7 → {9}; right of 1 → {5, 9}; right of 5 → {9}; nothing right of 9.

Example 2 Input: arr = [5, 4, 3] Output: [0, 0, 0]

Example 3 Input: arr = [1, 2, 3] Output: [2, 1, 0]

Constraints

• 1 <= n <= 10^5
• -10^9 <= arr[i] <= 10^9

Approach

Brute force is O(n²): for each i scan j > i. Fine for n <= 10^4, too slow beyond.

Merge-sort counting — O(n log n). Process indices, not values. During the merge step of merge sort, when an element from the left half is placed, every element still remaining in the right half that has already been placed before it is smaller… For "greater to the right" it is easier to count while placing right-half elements: sort in descending order; when an element from the right half is placed before elements of the left half, it is greater than all of the remaining left-half elements, so add 1 to each of their counts (accumulate via a running counter attached to left-half indices). This is the classic "Count of Smaller Numbers After Self" (LeetCode 315) with the comparison flipped.

Fenwick tree — O(n log n), simpler to reason about. Coordinate-compress the values to ranks 1..m. Scan from right to left; before inserting arr[i], query how many inserted values have rank greater than rank(arr[i]) — that is inserted_total - prefix(rank). Then add rank(arr[i]) to the tree. Every query and update is O(log m).

Complexity

• Time: O(n log n)
• Space: O(n)

Reference solution (Python)

def greater_to_right(arr):
    ranks = {v: i + 1 for i, v in enumerate(sorted(set(arr)))}
    m = len(ranks)
    tree = [0] * (m + 1)

    def add(i):
        while i <= m:
            tree[i] += 1
            i += i & -i

    def prefix(i):          # count of inserted values with rank <= i
        s = 0
        while i > 0:
            s += tree[i]
            i -= i & -i
        return s

    res = [0] * len(arr)
    inserted = 0
    for i in range(len(arr) - 1, -1, -1):
        r = ranks[arr[i]]
        res[i] = inserted - prefix(r)
        add(r)
        inserted += 1
    return res

Test cases

Input	Expected
[3,7,1,5,9]	[3,1,2,1,0]
[5,4,3]	[0,0,0]
[1,2,3]	[2,1,0]
[2,2,2]	[0,0,0]