Bootcamps
Masterclasses
Menu
Courses
Account
Login / Sign Up

Number of NGEs to the right

Medium Acceptance 56.74% Points 30

You are given an array of N integers and Q queries, where each query provides a specific index in the array. For each query, you need to determine how many elements to the right of the given index are strictly greater than the element at that index. Return the results as a list NGEs[], where NGEs[i] represents the count of such elements for the i-th query.

Examples
Example 1

Example 1

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

Output: 6, 1

Explanation: The next greater elements to the right of 3(index 0) are 4,7,5,8,10,6. The next greater element to the right of 8(index 5) is only 10.

Example 2

Example 2

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

Output: 3, 0

Explanation: The count of numbers to the right of index 0 which are greater than arr[0] is 3 i.e. (2, 3, 4). Similarly, the count of numbers to the right of index 3 which are greater than arr[3] is 0, since there are no greater elements than 4 to the right of the array.

Constraints
  • 1 <= N <= 10^4
  • 1 <= arr[i] <= 10^5
  • 1 <= queries <= 100
  • 0 <= indices[i] <= N - 1
Hints
  • Expected Time Complexity: O(N * queries).
  • Expected Space Complexity: O(queries).
Topics
Stack
Companies
Amazon Microsoft Walmart Google
Added 17 Dec 2024 56.74% acceptance
Ln 1, Col 1Sign in to save your code
8
3 4 2 7 5 8 10 6
2 
0 5
6 1