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] <= 109The key challenge in #503 Next Greater Element II is that the array is treated as circular. This means the search for the next greater element may continue from the beginning of the array after reaching the end. A brute-force approach would check the next elements for every index, potentially looping around the array, but this leads to O(n^2) time complexity.
A more optimal strategy uses a monotonic decreasing stack. The idea is to keep indices of elements whose next greater element has not yet been found. By iterating through the array twice (simulating the circular nature), we compare current values with elements represented in the stack. When a larger value appears, it resolves pending indices in the stack.
This approach ensures each element is pushed and popped at most once, giving an efficient O(n) time complexity while using additional stack space to track unresolved indices.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Monotonic Stack with Circular Traversal | O(n) | O(n) |
take U forward
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.
Time Complexity: O(n)
Space Complexity: O(n) (due to the stack and result array)
1import java.util.Stack;
2
3class Solution {
4 public int[] nextGreaterElements(int[] numsThis Java implementation uses a stack to handle every element in the cyclic array twice, once directly and once through a wrap-around. It approximately matches the logic in other solutions with slight adjustments for Java-specific techniques.
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.
Time Complexity: O(n^2) in the worst case
using namespace std;
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> res(n, -1);
for (int i = 0; i < n; ++i) {
for (int j = 1; j < n; ++j) {
if (nums[i] < nums[(i + j) % n]) {
res[i] = nums[(i + j) % n];
break;
}
}
}
return res;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The array is considered circular, meaning elements at the end can look for greater values at the beginning. Iterating up to 2*n allows us to simulate this wrap-around behavior without actually modifying the array.
Yes, this problem or its variations are common in technical interviews, including FAANG-style interviews. It tests understanding of stacks, monotonic stack patterns, and handling circular arrays efficiently.
The optimal approach uses a monotonic decreasing stack. By iterating through the array twice to simulate its circular nature, we can efficiently determine the next greater element for each position in O(n) time.
A stack is the most suitable data structure for this problem. Specifically, a monotonic stack helps track indices whose next greater element has not yet been found, allowing efficient comparisons as we traverse the array.
This C++ solution takes the brute force approach of checking each element's possibilities in an exhaustive fashion using two nested loops. Modulo is used for effectively handling the circular nature.