Stack - Monotonic Stack

A monotonic stack is a stack that maintains its elements in strictly increasing or decreasing order. Learn how to use it to find the next greater element for every element in an array.

Input: [2,1,2,4,3] → Next Greater: [4,2,4,-1,-1]

Input: [1,3,2,4] → Next Greater: [3,4,4,-1]

Use a monotonic decreasing stack: iterate from right to left. For each element, pop all stack elements that are smaller (they cannot be the next greater). The top of the stack is the next greater element.

Initialize result[] with -1.
Iterate i from n-1 to 0.
While stack is non-empty and stack.top() <= nums[i]: pop.
If stack is non-empty: result[i] = stack.top(). Push nums[i].

import java.util.*; class Solution { // Next Greater Element for each position public int[] nextGreaterElement(int[] nums) { int n = nums.length; int[] result = new int[n]; Arrays.fill(result, -1); Deque<Integer> stack = new ArrayDeque<>(); // stores indices for (int i = 0; i < n; i++) { while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) { result[stack.pop()] = nums[i]; } stack.push(i); } return result; } }

Time Complexity: O(N) — each element pushed and popped at most once
Space Complexity: O(N)