DSA interview question

Number of Greater Elements to the Right

Easy · Data structures · Topics: stack, monotonic stack

The problem

A leaderboard shows, for selected players, how many players listed after them have a strictly higher score. The list is fixed, but many index queries arrive. Answering each query by scanning to the right is O(n) per query. It's better to precompute the count for every index in one right-to-left pass with a Fenwick tree (binary indexed tree) over the compressed score values. Each step asks "how many already-seen scores are ≤ mine?" and subtracts that from the number seen, and then every query is O(1).

Example: arr = [3, 4, 2, 7, 5, 8, 10, 6], queries [0, 5] → [6, 1].

Function signature

vector<int> countGreaterToRight(const vector<int>& arr, const vector<int>& queries);

Test cases

Input `(arr, queries)`	Output	Explanation
`([3, 4, 2, 7, 5, 8, 10, 6], [0, 5])`	`[6, 1]`	After 3: 4, 7, 5, 8, 10, 6. After 8: 10
`([1, 2, 3, 4, 1], [0, 3])`	`[3, 0]`	The trailing 1 is not greater than 1
`([5, 5, 5], [0, 1, 2])`	`[0, 0, 0]`	Strictly greater
`([2, 1, 3], [0, 1, 2])`	`[1, 1, 0]`
`([1], [0])`	`[0]`

(Confirm: count strictly greater elements at larger indices; queries are valid 0-based indices.)

How interviewers phrase it

"Given an array and Q index queries, return the number of elements greater than arr[i] to its right for each query" (GeeksforGeeks "Count of Greater Elements to the Right").

Clarifying questions to ask

Strictly greater? (Yes.)
How many queries compared with n? (Few queries → brute force O(n · Q) is fine; many → precompute.)
What's the value range? (Large values need coordinate compression.)

Follow-ups to expect

"What's the brute force?"
"Why a Fenwick tree?"
"Why compress coordinates?"
"Other O(n log n) methods?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview