Count Next Greater Element

Aniket Vaishnav - Nov 22 '22 - - Dev Community

Problem Statement

Here we would look how to get number of greater element present next to current element

Example 1
[1,2,3,4] -> [3,2,1,0]

Example 2
[1,1,1,1] -> [0,0,0,0]

Example 3
[5,4,3,5,1] -> [0,1,1,0,0]

Solution

The Naive solution for this is to check for each element in the array, the next greater counts

Such as

class Solution {
    int[] nextGreaterElementCount(int[] a) {
        int[] res = new int[a.length]; // result array
        // for every element
        for (int i = 0; i < a.length; i++) {
            int count = 0;
            for (int j = i+1; j < a.length; j++) {
                // previous value is lesser than new value
                if (a[i] < a[j]) 
                    count++;
            }
            res[i] = count; // feed the count
        }
        return res;
    }
}
Enter fullscreen mode Exit fullscreen mode

Time Complexity: O(N2)

Space Complexity: O(1)

. . . . . . . . . . . . . . . . . . . . . . . . . . .
Terabox Video Player