Last Updated: 9 Sep, 2022

Next Greater Element II

Moderate

Asked in companies

Solve now

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.

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.

Solve now

Approaches

01 Approach

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[]’):

Initialize an array ‘answer’ of size ‘n’ to store the Next Greater Element for each element.
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.
Return the ‘answer’ array.

Solve now

02 Approach

The idea is very much similar to what we find NGE for the normal arrays. But in the case of a circular array, we can consider executing the same idea over an array appended to itself, because a circular array can be considered as the array appending to itself.

We will iterate linearly on the array of length 2 * ‘n’. In the stack, we will have all the indexes, whose answers we haven’t found yet, and whenever we find any element ‘x’, such that ‘x’ > a[top of the stack], we can surely say that ‘x’ is the next greater element for a[top of the stack].

The steps are as follows:-

function nextGreaterElementII(int ‘a[]’):

Initialize an array ‘answer’ of size ‘n’ with -1, to store the Next Greater Element for each element.
Initialize an empty stack ‘st’ to keep track of the next greater element.
Run a for loop form ‘i’ = 0 to 2 * ‘n’:
1. Initialize integer variable ‘index’ to ‘i’ % ‘n’ and ‘num’ to a[index].
2. While the stack ‘st ’ is not empty and a[top of the stack] < num:
  1. answer[top of stack] = num.
  2. Pop the top of the stack.
3. Insert ‘i’ in the stack.
Return ‘answer’ as the answer to the problem.

Solve now