503. Next Greater Element II
mediumFind the next greater element in a circular array. Same monotonic-stack pattern as NGE I, but with a circular twist — and a slick 'iterate 2n times' trick.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Problem
Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums. The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 for this number.
Constraints
1 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9
Examples
Example 1
nums = [1,2,1][2,-1,2]Explanation: The first 1's next greater number is 2; The number 2 can't find next greater number. The second 1's next greater number needs to search circularly, which is also 2.
Example 2
nums = [1,2,3,4,3][2,3,4,-1,4]Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Same monotonic-decreasing stack as NGE I — but how do you handle 'wrap around'?
Hint 2
Trick: iterate i from 0 to 2n - 1, indexing into nums via i % n. Each element gets two chances to find its successor.
Hint 3
Only push to the stack on the first pass (i < n); the second pass is purely for matching wrapped-around indices.
Hint 4
Final state: everything still on the stack at the end has no greater element — leave answer[i] = -1.
Solution approach
Reveal approach
Initialize answer[i] = -1 for all i. Use a monotonic decreasing stack of indices. Iterate i from 0 to 2n - 1 (yes, twice through the array). At each step let cur = nums[i % n]. While the stack is non-empty and nums[stack.top()] < cur, pop top j and set answer[j] = cur. Only push i % n onto the stack when i < n — second pass is only for matching, not for seeding. O(n) time (each index pushed once, popped once), O(n) space. The 'iterate 2n' trick is the cleanest way to simulate circularity without concatenating the array.
Complexity
- Time
- O(n)
- Space
- O(n)
Related patterns
- stack
- monotonic-stack
- circular-array
Related problems
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Bloomberg
Practice these live with InterviewChamp.AI
Drill Next Greater Element II and Stacks problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →