Number of NGEs to the Right
Monotonic Stack & Queue Problems DSA practice problem on Onlearn.
Difficulty: easy.
Topics: Number of NGEs (Next Greater Elements) to the right, Arrays, Loops, Brute Force, Time Complexity, Space Complexity, Optimization, Data Structures, Fenwick Tree, Coordinate Compression, Hash Map, Sorting, array traversal, monotonic stack, time complexity analysis, stack, Next/Previous Greater/Smaller Element.
Problem: Number of Next Greater Elements to the Right You are given an array A of N integers. For each element A[i] in the array, you need to find the count of elements A[j] such that j i and A[j] A[i]. In other words, for each element, count how many elements to its right are strictly greater than it. Input Format: The first line contains a single integer N (the number of elements in the array). The second line contains N space separated integers A 0, A 1, ..., A {N 1} representing the elements of the array. Output Format: Print N space separated integers, where the i th integer is the count of next greater elements to the right of A[i]. Constraints: 1 <= N <= 10^5 0 <= A[i] <= 10^9 Example Test Case: Input: Output: Explanation: For 3 (at index 0): 4 (index 2) and 5 (index 4) are greater to its right. Count = 2. For 1 (at index 1): 4 (index 2) and 5 (index 4) are greater to its right. Count = 2. For 4 (at index 2): 5 (index 4) is greater to its right. Count = 1. For 2 (at index 3): 5 (index 4) is greater to its right. Count = 1. For 5 (at index 4): No elements to its right. Count = 0.