Coding

Next Greater Element - 2

Asked at

Freshwoks

Media.net

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given a circular integer array arr, return the next greater element for every element in arr.

The next greater element for an element x is the first element greater than x that we come across while traversing the array in a clockwise manner.

If it doesn't exist, return -1 for that element.

Input: arr = [3, 10, 4, 2, 1, 2, 6, 1, 7, 2, 9] Output: [10, -1, 6, 6, 2, 6, 7, 7, 9, 9, 10] Explanation: For the first element in arr i.e, 3, the greater element which comes next to it while traversing and is closest to it is 10. Hence,10 is present on index 0 in the resultant array. Now for the second element i.e, 10, there is no greater number and hence -1 is it’s next greater element (NGE). Similarly, we got the NGEs for all other elements present in arr.

Input: arr = [5, 7, 1, 7, 6, 0] Output: [7, -1, 7, -1, 7, 5] Explanation: For the first element in arr i.e, 5, the greater element which comes next to it while traversing and is closest to it is 7. Now for the second element i.e, 7, there is no greater number and hence -1 is it’s next greater element (NGE). Similarly, we got the NGEs for all other elements present in arr.

Input: arr = [1, 2, 3, 4, 5]

1 ≤ n≤ 105
0 ≤ arr[i] ≤ 109

cpp

class Solution {
public:
    vector<int> nextGreaterElements(vector<int> &arr) {
        
    }
};

java

class Solution {
    public int[] nextGreaterElements(int[] arr) {
   
    }
}

python

class Solution:
    def nextGreaterElements(self, arr):

javascript

class Solution {
    nextGreaterElements(arr) {
  
    }
}

csharp

public class Solution
{
    public List<int> NextGreaterElements(List<int> arr)
    {
        
    }
}

func nextGreaterElements(arr []int) []int {

}

Stuck? Show a way to structure it+

01Initialize answers to minus one.
02Traverse indices from zero through twice n minus one.
03Use index modulo n to read values.
04Resolve smaller pending values with the current value.
05Push indices only during the first pass.

Reference answer

A circular array gives every index one extra pass over elements to its left. Simulate this by iterating i from zero to 2n minus one and reading idx = i modulo n. Keep a stack of unresolved indices. At each step, while the current value is greater than the value at the stack top, pop and assign the current value as that index's next greater element. Push idx only during the first n iterations; the second pass exists solely to resolve wraparound candidates and must not duplicate pending indices. Initialize answers to minus one, which covers values with no greater element anywhere. Each original index is pushed once and popped once, so time is O(n) and space O(n). This is preferable to checking up to n successors from each position, which becomes O(n squared).

Then expect these follow-ups

How would you return next greater index rather than value?
Tests: implementation extension
How does this compare with duplicating the array physically?
Tests: follow-up reasoning

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question