Next Greater Element

Medium

Problem

For each element, find the first element to its right that is strictly greater. Use −1 when there is none.

Example 1

Input:  [4, 5, 2, 25]
Output: [5, 25, 25, -1]

Example 2

Input:  [13, 7, 6, 12]
Output: [-1, 12, 12, -1]

Also asked as: Find the next Greater element

Test cases

Case 1

Input:    [4,5,2,25]
Expected: [5,25,25,-1]

Case 2

Input:    [13,7,6,12]
Expected: [-1,12,12,-1]

Case 3

Input:    [3,3]
Expected: [-1,-1]

Case 4

Input:    []
Expected: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Monotonic decreasing stack

Time O(n)Space O(n)

Push indices; when the current value beats the stack top, it is that index’s next-greater. Each index is pushed/popped once.

function nextGreater(nums) {
const res = Array(nums.length).fill(-1);
const st = [];
for (let i = 0; i < nums.length; i++) {
while (st.length && nums[i] > nums[st[st.length - 1]]) res[st.pop()] = nums[i];
st.push(i);
}
return res;
}