Next Greater Element
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: []
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;}