Algorithm Code
Time: O(n) | Space: O(n)
1function nextGreaterElement(arr) {
2 const result = new Array(arr.length).fill(-1);
3 const stack = []; // Monotonic decreasing stack
4
5 for (let i = 0; i < arr.length; i++) {
6 // While stack is not empty and current element
7 // is greater than stack top
8 while (stack.length > 0 && arr[i] > arr[stack[stack.length - 1]]) {
9 const index = stack.pop();
10 result[index] = arr[i];
11 }
12 stack.push(i);
13 }
14
15 return result;
16}Algorithm Steps
Step 1 of 37
Initialize Algorithm
Create empty monotonic stack and result array. The stack will maintain indices in decreasing order of their values.
Step 1: Process arr[0] = 2
Now examining element 2 at index 0. We'll check if it's greater than elements in our stack.
Stack is Empty
No elements to compare with. We'll push current index to the stack.
Push to Stack
Push index 0 (value 2) to stack. Stack maintains decreasing order of values.
Element 0 Processed
Finished processing arr[0] = 2. Stack now contains indices: [0]
Step 2: Process arr[1] = 1
Now examining element 1 at index 1. We'll check if it's greater than elements in our stack.
Check Stack Top
Stack top has index 0 (value 2). Compare with current element 1.
No Greater Element Found
1 ≤ 2, so we cannot pop any elements from the stack.
Push to Stack
Push index 1 (value 1) to stack. Stack maintains decreasing order of values.
Element 1 Processed
Finished processing arr[1] = 1. Stack now contains indices: [0, 1]
Step 3: Process arr[2] = 2
Now examining element 2 at index 2. We'll check if it's greater than elements in our stack.
Check Stack Top
Stack top has index 1 (value 1). Compare with current element 2.
✓ Found Next Greater Element
2 > 1, so 2 is the next greater element for arr[1]
Update Result
Pop index 1 from stack and set result[1] = 2
Continue Checking Stack
Stack still has elements. Check if 2 > 2 (current stack top)
Push to Stack
Push index 2 (value 2) to stack. Stack maintains decreasing order of values.
Element 2 Processed
Finished processing arr[2] = 2. Stack now contains indices: [0, 2]
Step 4: Process arr[3] = 4
Now examining element 4 at index 3. We'll check if it's greater than elements in our stack.
Check Stack Top
Stack top has index 2 (value 2). Compare with current element 4.
✓ Found Next Greater Element
4 > 2, so 4 is the next greater element for arr[2]
Update Result
Pop index 2 from stack and set result[2] = 4
Continue Checking Stack
Stack still has elements. Check if 4 > 2 (current stack top)
✓ Found Next Greater Element
4 > 2, so 4 is the next greater element for arr[0]
Update Result
Pop index 0 from stack and set result[0] = 4
Push to Stack
Push index 3 (value 4) to stack. Stack maintains decreasing order of values.
Element 3 Processed
Finished processing arr[3] = 4. Stack now contains indices: [3]
Step 5: Process arr[4] = 3
Now examining element 3 at index 4. We'll check if it's greater than elements in our stack.
Check Stack Top
Stack top has index 3 (value 4). Compare with current element 3.
No Greater Element Found
3 ≤ 4, so we cannot pop any elements from the stack.
Push to Stack
Push index 4 (value 3) to stack. Stack maintains decreasing order of values.
Element 4 Processed
Finished processing arr[4] = 3. Stack now contains indices: [3, 4]
Step 6: Process arr[5] = 1
Now examining element 1 at index 5. We'll check if it's greater than elements in our stack.
Check Stack Top
Stack top has index 4 (value 3). Compare with current element 1.
No Greater Element Found
1 ≤ 3, so we cannot pop any elements from the stack.
Push to Stack
Push index 5 (value 1) to stack. Stack maintains decreasing order of values.
Element 5 Processed
Finished processing arr[5] = 1. Stack now contains indices: [3, 4, 5]
Algorithm Complete ✅
Final result: [4, 2, 4, -1, -1, -1]. Elements remaining in stack (arr[3]=4, arr[4]=3, arr[5]=1) have no next greater element.