Next Greater Element II

Moderate
0/80
Average time to solve is 35m
profile
Contributed by
37 upvotes
Asked in companies
MathworksAmazonMAQ Software

Problem statement

You are given a circular array 'a' of length 'n'.


A circular array is an array in which we consider the first element is next of the last element. That is, the next element of 'a[n - 1]' is 'a[0]'.


Find the Next Greater Element(NGE) for every element.


The Next Greater Element for an element 'x' is the first element on the right side of 'x' in the array, which is greater than 'x'.


If no greater elements exist to the right of 'x', consider the next greater element as -1.


Example: 
Input: 'a' = [1, 5, 3, 4, 2]

Output: NGE = [5, -1, 4, 5, 5]

Explanation: For the given array,

- The next greater element for 1 is 5.

- There is no greater element for 5 on the right side. So we consider NGE as -1.

- The next greater element for 3 is 4.

- The next greater element for 4 is 5, when we consider the next elements as 4 -> 2 -> 1 -> 5.

- The next greater element for 2 is 5, when we consider the next elements as 2 -> 1 -> 5.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'n' denoting the size of the array 'a'.

The second line contains 'n' single space-separated integers, elements of the array 'a'.


Output format : 
Find the Next Greater Element(NGE) for every element in the circular array.


Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Sample Input 1 :
5
1 5 3 4 2


Sample Output 1 :
5 -1 4 5 5


Explanation Of Sample Input 1 :
For the given array,

- The next greater element for 1 is 5.

- There is no greater element for 5 on the right side. So we consider NGE as -1.

- The next greater element for 3 is 4.

- The next greater element for 4 is 5, when we consider the next elements as 4 -> 2 -> 1 -> 5.

- The next greater element for 2 is 5, when we consider the next elements as 2 -> 1 -> 5.


Sample Input 2:
5
5 5 5 5 5


Sample Output 2:
-1 -1 -1 -1 -1


Expected time complexity :
The expected time complexity is O(n).


Constraints :
1 <= 'n' <= 10^5
1 <= 'a[i]' <= 10^9

Time Limit: 1 sec
Hint

Check all possibilities.

Approaches (2)
Brute Force

In this approach, we will check individually for each element of the array. 

For each element of the array, we will linearly traverse the whole array circularly starting from the next index, and if we find any greater element then it will be our answer, otherwise, if we reach the starting index without any greater element, our answer is -1.  
The steps are as follows:-

function nextGreaterElementII(int ‘a[]’):

  1. Initialize an array ‘answer’ of size ‘n’ to store the Next Greater Element for each element.
  2. Run a for loop from ‘i’ = 0 to ‘n’ - 1:
    1. Initialize an integer variable ‘currentAnswer’ to -1.
    2. Run a for loop from ‘j’ = 1 to ‘n’ - 1:
      1. If a[(i + j) % n] > a[i] then update ‘currentAnswer’ to a[(i + j) % n] and break.
    3. Update answer[i] to ‘currentAnswer.
  3. Return the ‘answer’ array.
Time Complexity

O(n ^ 2), Where 'n' is the size of the given array 'a'.

We are running two nested for loops, each of O(n) complexity.

Hence the time complexity is O(n ^ 2).

Space Complexity

O(n), Where 'n' is the size of the given array 'a'.

We are using an array of size ‘n’ to store the Next Greater Element for each element.

Hence space complexity is O(n).

Code Solution
(100% EXP penalty)
Next Greater Element II
Full screen
Console