Pattern this teaches:Monotonic Stack
Next Greater Element II
A medium Stack interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Stack
- Sheets
- 2
- Core for
- 9 roles
The problem
Given an array nums2, find the next greater element for each element treating the array as circular — meaning the element after the last element wraps around to the first. Return -1 if no greater element exists.
Example 1
- Input
- nums1 = [1,2,1], nums2 = [1,2,1]
- Output
- [2,-1,2]
- Why
- For the first 1 in nums2, the next greater circular element is 2. For 2, there is no greater element. For the second 1, wrapping around finds 2.
Example 2
- Input
- nums1 = [1], nums2 = [1]
- Output
- [-1]
- Why
- A single element has no greater element even with circular wrapping.
Constraints
- 1 <= nums1.length <= nums2.length <= 10^4
- 0 <= nums1[i], nums2[i] <= 10^4
- All integers in nums2 are unique
How to think about it
Updated 2026-09-29A circular array of length n is identical to a linear array of length 2n where indices wrap via modulo arithmetic. Any element's next greater neighbor must appear within the next n - 1 steps. Simulating two consecutive passes over the array gives every index a complete opportunity to see the prefix elements wrapped around behind it.
Approaches, worst first
Circular scan per element
time O(n^2) · space O(1)
For each index i from 0 to n - 1, scan up to n - 1 steps forward using `(i + j) % n`. The first strictly greater value encountered is the answer. Takes quadratic time when the array is non-increasing or elements are identical.
Two-pass monotonic stack with modulo indexWrite this one
time O(n) · space O(n)
Loop index i from 0 to 2n - 1, accessing elements via `nums[i % n]`. Maintain a decreasing stack of original indices. Whenever `nums[i % n]` is greater than `nums[stack.top()]`, pop and assign `result[popped] = nums[i % n]`. Only push indices during the first pass `i < n`.
Where people lose marks · 3
- Pushing indices onto the stack during the second round: pushing on `i >= n` can cause duplicate index insertions and overwrite resolved answers.
- Failing to initialize the result array with -1: the maximum element in the array has no strictly greater circular element and must retain -1.
- Single-element array edge case: an element cannot be its own greater neighbor across the circular boundary.
The theory behind it
Stack — the ground this problem stands on. All Stack problems
What Stack is
A stack is a vertical pile of cafeteria trays where items enter and depart from one single opening at the top. The most recent item set down is the first one retrieved, while items deposited earlier remain buried underneath until newer arrivals are lifted away. This strict last-in, first-out sequence guarantees that older context stays preserved until all newer nested actions run to completion.
When to reach for it
Reach for a stack whenever an algorithm encounters nested structures like matched brackets, tags, or algebraic formulas. Problems demanding undo operations, function execution histories, or evaluating postfix arithmetic require this discipline. It is also the primary structure for monotonic queries where a task asks for the nearest greater or smaller value adjacent to each position in a series.
How the pattern works
Picture peeling layers back in exact reverse order of their arrival. Push items as pending jobs or unclosed delimiters encounter the scan. When closing boundaries appear, pop the topmost entry and check for compatibility. For monotonic patterns, maintain an invariant where elements on the stack remain strictly increasing or decreasing; pop any items that violate this rule before recording candidate answers and pushing the current item.
More Stack problems
Target Roles
Core requirement for 9 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .