Number of Greater Elements to the Right
EasyCount, so a stack is not enough
Problem
For each element, count how many elements to its right are greater than it.
Scan from the right into a sorted structure, counting how many seen values already exceed each element.
The idea
A monotonic stack finds the nearest greater element but cannot count all of them. Counting needs an order-statistics structure — a Fenwick tree over the values, filled from the right — giving O(n log n).
The trick
- Sweep right to left, querying the count of larger values already inserted.
- Compress the values first so the tree indices stay small.
- Merge sort with counting is an equivalent O(n log n) approach.
3
4
2
7
5
8
10
6
0
1
2
3
4
5
6
7
Step 1 of 10. Brute force: for each element, count the bigger values to its right. Values: 3, 4, 2, 7, 5, 8, 10, 6.
1/10
Brute force
timeO(n²)spaceO(1)
Count to the right.
1for (let i = 0; i < n; i++)2 for (let j = i + 1; j < n; j++)3 if (nums[j] > nums[i]) res[i]++;Input
- array
- [3, 4, 2, 7, 5, 8, 10, 6]
Output
- counts
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [3, 4, 2, 7, 5, 8, 10, 6]
- Output:
- [6, 5, 5, 2, 3, 1, 0, 0]
- Explanation:
- For each element, count bigger values to its right.
Example 2
- Input:
- nums = [5, 4, 3, 2, 1]
- Output:
- [0, 0, 0, 0, 0]
- Explanation:
- Decreasing → all 0.
Example 3
- Input:
- nums = [1, 2, 3]
- Output:
- [2, 1, 0]
- Explanation:
- 1 has 2 greater, 2 has 1, 3 has 0.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.