Next Greater Element
Mahabharata — The Circular Arena — Who is the Next Mightier Warrior?
प्रत्येकस्य योधस्य — पश्चात् महाबलः कः?। वृत्तयुद्धे अनुक्रमेण — उत्तरम् एकैकं दीयताम्॥
*For each warrior — who is the next mightier one behind? In circular combat, answer each in turn.*
The Story
Given a circular array, for each element find the next greater element (searching circularly). If no greater element exists, return -1.
For `nums = [1,2,1]`, the answers are `[2,-1,2]`: - 1 → next greater is 2 ✓ - 2 → no greater in circular array → -1 - 1 → circularly, next greater is 2 ✓
This is the **Monotonic Stack** pattern — a stack that maintains elements in increasing (or decreasing) order.
**Key insight:** We use a stack of INDICES storing elements in DECREASING order (monotone decreasing). When we find a greater element, we pop indices whose elements are smaller.
**For circular array:** Loop from i=0 to 2n-1, using index `i % n`. The second pass handles wrap-arounds.
```java for (int i = 0; i < 2*n; i++) { int val = nums[i % n]; // Pop all elements smaller than current — current is their next greater while (!stack.isEmpty() && nums[stack.peek()] < val) res[stack.pop()] = val; // Only push actual indices (not the second pass phantoms) if (i < n) stack.push(i); } ```
Trace `[1,2,3,2,1]`: - i=0(1): push 0. stack=[0] - i=1(2): 1<2 → pop 0, res[0]=2. push 1. stack=[1] - i=2(3): 2<3 → pop 1, res[1]=3. push 2. stack=[2] - i=3(2): 3>2. push 3. stack=[2,3] - i=4(1): both >1. push 4. stack=[2,3,4] - i=5(1, %5=0): 1>1? No pop. - i=6(2): 1<2 → pop 4, res[4]=2. pop 3, res[3]=2. 3>2, stop. - i=7(3): 2<3 → pop 2, res[2]=3. stop. - Remaining in stack (i >= n so not pushed): stack empty. Result: [2,3,-1,3,2] ✓
The monotone stack ensures O(n) — each element pushed and popped at most once.
The Brute Force Scout
For each element, scan forward (circularly) until finding a greater one. O(n²).
public int[] nextGreaterElementsBruteForce(int[] nums) {
int n = nums.length;
int[] res = new int[n];
Arrays.fill(res, -1);
for (int i = 0; i < n; i++)
for (int j = 1; j < n; j++)
if (nums[(i+j) % n] > nums[i]) { res[i] = nums[(i+j)%n]; break; }
return res;
}The Monotonic Stack Wisdom
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] res = new int[n];
Arrays.fill(res, -1);
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < 2 * n; i++) {
int val = nums[i % n];
while (!stack.isEmpty() && nums[stack.peek()] < val) {
res[stack.pop()] = val;
}
if (i < n) stack.push(i);
}
return res;
}Step-by-Step Walkthrough
nums=[5,4,3,2,1] (strictly decreasing) i=0..4: all pushed, no pops (each new is smaller) i=5..9 (2nd pass): still no element > top (5 is max) All remain → all -1 ✅
Deep Insight
**Why the monotone stack is O(n)?** Each index is pushed once and popped at most once. Total operations = O(n), even though the outer loop runs 2n times.
**Non-circular variant (LeetCode 496):** For a non-circular array, loop once (0 to n-1). Elements remaining in stack at the end get -1.
**Monotone decreasing stack:** Stack always has decreasing values (larger values are deeper). When a larger value comes, it "resolves" all pending smaller values below it.
**This pattern powers st-5 (daily temperatures)** — same technique, different formulation.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(n) | Circular scan for each element |
| Optimal | O(n) | O(n) | Each element pushed/popped at most once |
Pattern Recognition
✅ Monotone decreasing stack of indices ✅ Loop 2n times for circular array (i%n) ✅ Pop when current > top: record answer ✅ Push only for i<n (first pass) **LeetCode Trigger Phrases:** → "next greater element" (circular or non-circular) → "next warmer temperature" → "monotone stack" — decreasing values
Bhagavad Gita 15.17
उत्तमः पुरुषस्त्वन्यः परमात्मेत्युदाहृतः। यो लोकत्रयमाविश्य बिभर्त्यव्यय ईश्वरः॥
But beyond these two is yet another — the Supreme Person, the imperishable Lord who, pervading the three worlds, sustains them.
Connection: For every element, the algorithm searches for the one greater than it — the 'uttama purusha' that supersedes it. The monotone stack embodies the cosmic principle of hierarchy: elements smaller than what follows are resolved and released, while those without a greater successor remain acknowledged but unanswered (-1). The second circular pass, like karma, gives every element a second chance to find its greater counterpart in the cycle.