Watch 10 video solutions for Next Greater Element II, a medium level problem involving Array, Stack, Monotonic Stack. This walkthrough by take U forward has 208,561 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
Input: nums = [1,2,1] Output: [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:
Input: nums = [1,2,3,4,3] Output: [2,3,4,-1,4]
Constraints:
1 <= nums.length <= 104-109 <= nums[i] <= 109Problem Overview: You are given a circular integer array where the next element after the last index wraps back to the first. For every element, find the first greater value encountered while moving forward through the array. If no such element exists, return -1 for that position.
Approach 1: Monotonic Stack (O(n) time, O(n) space)
The optimal solution uses a stack that maintains indices in decreasing order of values. The stack represents elements whose next greater value hasn't been found yet. Traverse the array twice to simulate the circular behavior. For each index, compare the current value with the value at the index on top of the stack. While the current value is greater, pop the index and record the current value as its next greater element.
This structure is a classic monotonic stack pattern. Each index is pushed once and popped once, which guarantees linear processing. The second traversal ensures elements near the end of the array can still find greater elements at the beginning. Only indices from the first pass are pushed to the stack to avoid duplicates.
This approach works well because the stack stores only unresolved elements. As soon as a larger value appears, it resolves multiple previous indices in one step. The result array stores answers directly by index, avoiding extra searches.
Approach 2: Double Traversal Without Stack (O(n²) time, O(1) extra space)
A straightforward method checks the next greater element for every index by scanning forward through the array. Because the array is circular, the scan may wrap around to index 0 and continue until the starting position is reached again. The first value greater than the current element becomes the answer.
This approach uses only the array itself and a few loop variables. However, each element may trigger a full traversal of the array, leading to quadratic time complexity. For large inputs this quickly becomes inefficient.
Despite the inefficiency, this method helps build intuition about the circular search requirement. It also makes debugging easier since the logic mirrors the problem definition exactly.
Recommended for interviews: Interviewers expect the monotonic stack solution. The brute-force double traversal shows you understand the circular nature of the problem, but the O(n) monotonic stack demonstrates strong knowledge of stack-based patterns used in next-greater-element problems. Variations of this technique appear frequently in array and stack interview questions.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Monotonic Stack | O(n) | O(n) | Best general solution for circular next-greater-element problems and typical interview expectations |
| Double Traversal Without Stack | O(n²) | O(1) | Useful for understanding the circular search logic or when avoiding extra data structures |