DEV Community

Aniket Vaishnav
Aniket Vaishnav

Posted on

Count Next Greater Element

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)

Top comments (0)