Next Greater Element
Morgan StanleyThe 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)
{
}
}go
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
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
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.
Next question