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.
This approach utilizes a stack to keep track of the indices of the elements for which we are finding the next greater element. We traverse the array twice (length times two) to account for the circular nature of the array. For each element, we repeatedly pop elements from the stack while the current element is greater than the element represented by the index at the top of the stack. As we pop elements, we update their next greater element in the resulting array. The stack helps ensure that each element is processed efficiently, leading to an O(n) complexity.
This Python solution employs a stack to track the indices of elements. It processes each index twice using a modulo operation to simulate the circular nature of the array. It successfully finds the next greater element by leveraging the stack to keep track of indices that need to find a larger subsequent value.
Time Complexity: O(n)
Space Complexity: O(n) (due to the stack and result array)
This approach uses two separate traversals to find the next greater element by checking for each element's greater counterpart. We double-iterate through the array copying elements to support cyclic checking. Though simpler conceptually, its efficiency isn't as optimal due to direct comparisons, and it could degrade to an O(n^2) complexity in worst cases. It's educational for understanding direct exhaustive search in circular constructs.
This Python solution performs direct iterative comparisons on pairs of elements. For each index, it tests succeeding elements using a nested loop construct, leveraging modulo to achieve wrap-around.
Time Complexity: O(n^2) in the worst case
The problem requires us to find the next greater element for each element. Therefore, we can traverse the array from back to front, which effectively turns the problem into finding the previous greater element. Additionally, since the array is circular, we can traverse the array twice.
Specifically, we start traversing the array from index n times 2 - 1, where n is the length of the array. Then, we let j = i bmod n, where bmod represents the modulo operation. If the stack is not empty and the top element of the stack is less than or equal to nums[j], then we continuously pop the top element of the stack until the stack is empty or the top element of the stack is greater than nums[j]. At this point, the top element of the stack is the previous greater element for nums[j], and we assign it to ans[j]. Finally, we push nums[j] onto the stack. We continue to the next element.
After the traversal is complete, we can obtain the array ans, which represents the next greater element for each element in the array nums.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: Using a Monotonic Stack | Time Complexity: |
| Approach 2: Double Traversal Without Stack | Time Complexity: |
| Monotonic Stack | — |
| 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 |
L6. Next Greater Element - II | Stack and Queue Playlist • take U forward • 208,561 views views
Watch 9 more video solutions →Practice Next Greater Element II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor