Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Count of Greater Elements to Right

EASYProblemSolveExternal Links

Description

You are given an integer array arr[] of size n and Q queries. Each query provides an index indices[i] into the array.

For each query, determine the count of elements in arr that are strictly greater than arr[indices[i]] and appear to the right of position indices[i] (i.e., at positions indices[i]+1 through n-1).

Return an array where each entry corresponds to the count for the respective query.

Examples

Example 1

Input: arr = [3, 4, 2, 7, 5, 8, 10, 6], queries = 2, indices = [0, 5]

Output: [6, 1]

Explanation:

  • Query index 0: arr[0] = 3. Elements to the right: [4, 2, 7, 5, 8, 10, 6]. Those greater than 3 are 4, 7, 5, 8, 10, 6. Count = 6.
  • Query index 5: arr[5] = 8. Elements to the right: [10, 6]. Only 10 is greater than 8. Count = 1.

Example 2

Input: arr = [1, 2, 3, 4, 1], queries = 2, indices = [0, 3]

Output: [3, 0]

Explanation:

  • Query index 0: arr[0] = 1. Elements to the right: [2, 3, 4, 1]. Those greater than 1 are 2, 3, 4. Count = 3.
  • Query index 3: arr[3] = 4. Elements to the right: [1]. No element is greater than 4. Count = 0.

Example 3

Input: arr = [5, 5, 5], queries = 1, indices = [0]

Output: [0]

Explanation:

  • Query index 0: arr[0] = 5. Elements to the right: [5, 5]. Neither is strictly greater than 5. Count = 0. This edge case confirms that equal elements do not count.

Constraints

  • 1 ≤ n ≤ 10^4
  • 1 ≤ arr[i] ≤ 10^5
  • 1 ≤ queries ≤ 100
  • 0 ≤ indices[i] ≤ n - 1

Editorial

Brute Force

Intuition

Imagine you are in a classroom and a teacher asks: "How many students sitting to your right are taller than you?" The simplest approach is for the queried student to look at every person to their right, one by one, and count those who are taller.

Similarly, for each query index, we scan all elements to the right and count those that are strictly greater than the element at the queried position. This is a direct, straightforward approach — examine every candidate and compare.

Since each query is answered independently, we process queries one at a time, scanning the relevant portion of the array for each.

Step-by-Step Explanation

Let's trace through with arr = [1, 2, 3, 4, 1], indices = [0, 3]:

Query 1: index = 0, arr[0] = 1

Step 1: Start at j = 1. arr[1] = 2 > 1? YES. count = 1.
Step 2: j = 2. arr[2] = 3 > 1? YES. count = 2.
Step 3: j = 3. arr[3] = 4 > 1? YES. count = 3.
Step 4: j = 4. arr[4] = 1 > 1? NO (equal, not strictly greater). count stays 3.
Step 5: Result for query 1: count = 3.

Query 2: index = 3, arr[3] = 4

Step 6: Start at j = 4. arr[4] = 1 > 4? NO. count = 0.
Step 7: Result for query 2: count = 0.

Final Result: [3, 0]

Brute Force — Scanning Right for Each Query — Watch how each query independently scans all elements to the right of the queried index, counting those strictly greater. Equal elements are skipped.

Algorithm

  1. For each query index idx in the indices array:
    • Initialize count = 0.
    • For each position j from idx + 1 to n - 1:
      • If arr[j] > arr[idx], increment count.
    • Store count as the result for this query.
  2. Return the array of results.

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> count_NGEs(int n, vector<int>& arr, int queries, vector<int>& indices) {
        vector<int> result;
        
        for (int idx : indices) {
            int count = 0;
            for (int j = idx + 1; j < n; j++) {
                if (arr[j] > arr[idx]) {
                    count++;
                }
            }
            result.push_back(count);
        }
        
        return result;
    }
};
class Solution:
    def count_NGEs(self, n, arr, queries, indices):
        result = []
        
        for idx in indices:
            count = 0
            for j in range(idx + 1, n):
                if arr[j] > arr[idx]:
                    count += 1
            result.append(count)
        
        return result
class Solution {
    public int[] count_NGEs(int n, int[] arr, int queries, int[] indices) {
        int[] result = new int[queries];
        
        for (int q = 0; q < queries; q++) {
            int idx = indices[q];
            int count = 0;
            for (int j = idx + 1; j < n; j++) {
                if (arr[j] > arr[idx]) {
                    count++;
                }
            }
            result[q] = count;
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(Q × N)

For each of the Q queries, we scan up to N elements to the right. In the worst case (every query asks about index 0), this means Q full-array scans. With Q up to 100 and N up to 10^4, the worst case is 10^6 operations — manageable, but inefficient for larger inputs.

Space Complexity: O(1)

Beyond the output array, we use only a constant number of variables (idx, count, j). No additional data structures are needed.

Why This Approach Is Not Efficient

The brute force processes each query independently, scanning all elements to the right of the queried index. If there are Q queries and the array has N elements, the worst case is O(Q × N). When Q approaches N (imagine querying every position), this degrades to O(N²) — up to 10^8 operations.

More fundamentally, the brute force performs redundant work. If we query indices 0 and 1 in the same array, both queries scan many of the same elements to the right, counting independently each time. There is no sharing of information between queries.

Key insight: Instead of answering each query from scratch, we can precompute the answer for ALL positions in a single right-to-left pass. By maintaining a sorted collection of elements seen so far (the suffix), we can use binary search to count how many elements in the suffix are greater than the current element — in O(log n) per position instead of O(n). Once precomputed, each query is answered in O(1).

Optimal Approach - Suffix Processing with Binary Search

Intuition

Imagine you are collecting test scores from students as they enter a room one by one, from the last student to the first. You keep a sorted list of all scores seen so far. Each time a new student arrives, you want to know how many students already in the room scored higher.

Because your list is sorted, you do not need to check every student — you perform a binary search to find where the new score would fit, and immediately know how many scores above it exist (everything to the right of that position in the sorted list).

This is the core idea: process the array from right to left, maintaining a sorted list of all elements to the right of the current position. For each position, binary search tells us the count of greater elements in O(log n). After precomputing counts for all positions, any query is answered in O(1).

The sorted list grows by one element each iteration, and binary search efficiently partitions it into "elements ≤ current" and "elements > current."

Step-by-Step Explanation

Let's trace through with arr = [1, 2, 3, 4, 1], indices = [0, 3]:

We process from right to left, building a sorted suffix:

Step 1: i = 4, arr[4] = 1. Sorted suffix is empty.

  • No elements to the right → count[4] = 0.
  • Insert 1 → sorted suffix = [1].

Step 2: i = 3, arr[3] = 4. Sorted suffix = [1].

  • Binary search: bisect_right([1], 4) = 1. Elements after position 1: none.
  • count[3] = 1 − 1 = 0. No elements are greater than 4.
  • Insert 4 → sorted suffix = [1, 4].

Step 3: i = 2, arr[2] = 3. Sorted suffix = [1, 4].

  • Binary search: bisect_right([1, 4], 3) = 1. Elements after position 1: [4].
  • count[2] = 2 − 1 = 1. One element (4) is greater than 3.
  • Insert 3 → sorted suffix = [1, 3, 4].

Step 4: i = 1, arr[1] = 2. Sorted suffix = [1, 3, 4].

  • Binary search: bisect_right([1, 3, 4], 2) = 1. Elements after position 1: [3, 4].
  • count[1] = 3 − 1 = 2. Two elements (3 and 4) are greater than 2.
  • Insert 2 → sorted suffix = [1, 2, 3, 4].

Step 5: i = 0, arr[0] = 1. Sorted suffix = [1, 2, 3, 4].

  • Binary search: bisect_right([1, 2, 3, 4], 1) = 1 (goes past the duplicate 1). Elements after position 1: [2, 3, 4].
  • count[0] = 4 − 1 = 3. Three elements (2, 3, 4) are greater than 1.
  • Insert 1 → sorted suffix = [1, 1, 2, 3, 4].

Precomputed counts: count = [3, 2, 1, 0, 0]

Answer queries:

  • indices[0] = 0 → count[0] = 3
  • indices[1] = 3 → count[3] = 0

Result: [3, 0]

Suffix Processing — Building Sorted Suffix with Binary Search — Watch how we process from right to left, maintaining a sorted suffix of elements seen so far. Binary search instantly counts how many suffix elements are greater than the current one.

Algorithm

  1. Create an empty sorted list and a count array of size n.
  2. Process from right to left (i = n-1 down to 0):
    • Use binary search (bisect_right) to find the position pos where arr[i] would be inserted in the sorted list.
    • count[i] = total elements in sorted list − pos. This gives the count of elements greater than arr[i].
    • Insert arr[i] into the sorted list at the correct position (maintaining sorted order).
  3. For each query index idx, return count[idx].

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> count_NGEs(int n, vector<int>& arr, int queries, vector<int>& indices) {
        // Precompute count of greater elements to the right for all positions
        vector<int> count(n, 0);
        vector<int> sorted_suffix;
        
        for (int i = n - 1; i >= 0; i--) {
            // Binary search: count elements > arr[i]
            auto pos = upper_bound(sorted_suffix.begin(), sorted_suffix.end(), arr[i]);
            count[i] = sorted_suffix.end() - pos;
            
            // Insert arr[i] into sorted position
            auto insert_pos = lower_bound(sorted_suffix.begin(), sorted_suffix.end(), arr[i]);
            sorted_suffix.insert(insert_pos, arr[i]);
        }
        
        // Answer queries in O(1) each
        vector<int> result;
        for (int idx : indices) {
            result.push_back(count[idx]);
        }
        return result;
    }
};
import bisect

class Solution:
    def count_NGEs(self, n, arr, queries, indices):
        # Precompute count of greater elements to the right for all positions
        count = [0] * n
        sorted_suffix = []
        
        for i in range(n - 1, -1, -1):
            # Binary search: count elements > arr[i]
            pos = bisect.bisect_right(sorted_suffix, arr[i])
            count[i] = len(sorted_suffix) - pos
            
            # Insert arr[i] into sorted position
            bisect.insort(sorted_suffix, arr[i])
        
        # Answer queries in O(1) each
        return [count[idx] for idx in indices]
import java.util.*;

class Solution {
    public int[] count_NGEs(int n, int[] arr, int queries, int[] indices) {
        // Precompute count of greater elements to the right for all positions
        int[] count = new int[n];
        List<Integer> sortedSuffix = new ArrayList<>();
        
        for (int i = n - 1; i >= 0; i--) {
            // Binary search: count elements > arr[i]
            int pos = upperBound(sortedSuffix, arr[i]);
            count[i] = sortedSuffix.size() - pos;
            
            // Insert arr[i] into sorted position
            int insertPos = lowerBound(sortedSuffix, arr[i]);
            sortedSuffix.add(insertPos, arr[i]);
        }
        
        // Answer queries in O(1) each
        int[] result = new int[queries];
        for (int q = 0; q < queries; q++) {
            result[q] = count[indices[q]];
        }
        return result;
    }
    
    // Returns index of first element > target
    private int upperBound(List<Integer> list, int target) {
        int lo = 0, hi = list.size();
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (list.get(mid) <= target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
    
    // Returns index of first element >= target
    private int lowerBound(List<Integer> list, int target) {
        int lo = 0, hi = list.size();
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (list.get(mid) < target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
}

Complexity Analysis

Time Complexity: O(N log N + Q) — with a caveat

The precomputation loop runs N iterations. For each iteration:

  • Binary search (counting greater elements): O(log N) using bisect_right or upper_bound.
  • Sorted insertion: O(N) in the worst case with array-based lists (due to shifting elements), or O(log N) with a balanced BST (e.g., C++ std::set with order statistics, Python SortedList from sortedcontainers).

With a simple array/list: O(N²) for precomputation + O(Q) for queries.
With a balanced BST: O(N log N) for precomputation + O(Q) for queries.

The code above uses array-based lists for simplicity. For N ≤ 10^4, this is efficient enough (≈ 10^8 operations worst case).

Space Complexity: O(N)

The sorted suffix list can hold up to N elements. The count array also uses O(N). Total auxiliary space: O(N).