Coding

Next Greater Element

Asked atGGeekyants

Morgan Stanley

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an array arr of size n containing elements, find the next greater element for each element in the array in the order of their appearance.

The next greater element of an element in the array is the nearest element on the right that is greater than the current element.

If there does not exist a next greater element for the current element, then the next greater element for that element is -1.

Input: arr = [1, 3, 2, 4] Output: [3, 4, 4, -1] Explanation: In the array, the next larger element to 1 is 3, 3 is 4, 2 is 4 and for 4 is -1, since it does not exist.

Input: arr = [6, 8, 0, 1, 3] Output: [8, -1, 1, 3, -1] Explanation: In the array, the next larger element to 6 is 8, for 8 there is no larger elements hence it is -1, for 0 it is 1 , for 1 it is 3 and then for 3 there is no larger element on the right and hence -1.

Input: arr = [1, 3, 2]

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

cpp

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

java

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

python

class Solution:
    def nextLargerElement(self, arr):

javascript

class Solution {
    nextLargerElement(arr) {
       
    }
}

csharp

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

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

}

Stuck? Show a way to structure it+

01Initialize all answers to minus one.
02Scan left to right.
03While current value exceeds values at pending indices, resolve them.
04Push the current index as unresolved.
05Leave remaining stack indices at minus one.

Reference answer

Scan from left to right while maintaining indices whose next greater value has not been seen. Before pushing index i, repeatedly pop any top index j with arr[j] less than arr[i]; arr[i] is the first greater value to j's right, so set answer[j] to arr[i]. Then push i. Values remaining in the stack never encounter a greater element, so their initialized minus one answer stays correct. Using indices rather than only values handles duplicates and preserves the output position. Every index is pushed once and popped at most once, giving O(n) time and O(n) space. The comparison should be strictly less because the question asks greater, not greater-or-equal. A nested rightward scan is easy to state but is O(n squared) in decreasing input.

Then expect these follow-ups

How would you find next smaller elements?
Tests: follow-up reasoning
How do you solve the circular version?
Tests: follow-up reasoning

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question