Next Greater Element II
Understanding the Problem
We have a circular array, meaning after the last element, we loop back to the beginning. For each element, we need to find the first element that is strictly greater than it when scanning to the right in this circular fashion.
The circular nature is the only difference from the standard problem. In a normal "next greater element" problem, you scan to the right and stop at the end. Here, after reaching the end, you wrap around to the beginning and keep scanning until you're back where you started. If no greater element is found after a full circle, the answer is -1.
Only instances of the global maximum get -1. Every other element eventually finds something greater as we circle around, since at minimum the global maximum is greater than it.
Key Constraints:
1 <= nums.length <= 10^4→ With n up to 10,000, an O(n^2) brute force performs up to 100 million operations. That is borderline but passes. An O(n) solution exists and is preferred.-10^9 <= nums[i] <= 10^9→ Values can be negative. This does not affect the algorithm, but it means -1 (not 0) must be the sentinel for "no greater element found." A value of 0 could be a legitimate answer.
Approach 1: Brute Force
Intuition
Do exactly what the problem says: for each element, scan to the right through the circular array looking for the first greater element. Since the array is circular, after reaching the end we wrap back to the beginning and keep going until we have checked every other position.
For each index i, we check up to n - 1 subsequent positions (the entire rest of the circular array). The moment we find a value greater than nums[i], we record it and move on. If we complete the full circle without finding anything greater, we record -1.
Algorithm
- Create a result array of size n, initialized to -1.
- For each index
ifrom 0 to n-1: - For each offset
jfrom 1 to n-1: - Compute the circular index as
(i + j) % n. - If the element at that circular index is greater than
nums[i], setresult[i]to that element and break out of the inner loop. - Return the result array.
Visualization and Code
Loading animation...
- Time Complexity: O(n^2). For each of the n elements, we potentially scan up to n-1 other elements in the circular array.
- Space Complexity: O(1). We only use the result array (required for output). No additional data structures are needed.
The brute force rescans the same elements repeatedly and discards what it learns on each pass. The next approach processes each element once and resolves several pending answers at a time using a stack.
Approach 2: Monotonic Stack
Intuition
Instead of asking "for element i, where is the next greater element?", we flip the question: "when I encounter element j, which previous elements does it resolve as their next greater element?"
As we scan through the array, we maintain a stack of elements that are still waiting for their next greater element. When we encounter a new element larger than the top of the stack, we have found the answer for that waiting element. We pop it, record the answer, and check the new top. We keep popping until the top is no longer smaller than the current element.
The stack stays in decreasing order from bottom to top (a monotonic decreasing stack). Before pushing a larger element, we first pop off every smaller element, since the current element is their next greater element. Whatever remains below is greater than the current element, so the order is preserved.
To handle the circular wrap-around, we iterate through the array twice. The second pass gives elements from the first pass a chance to find their answer in the wrapped-around portion. We use i % n to map indices back to the original array, and push indices only during the first pass to avoid duplicates.
When an index j pops index k off the stack, j is the first index after k (in circular order) with nums[j] > nums[k]. Any index between k and j was either popped earlier by something smaller, or was smaller than nums[k] and never sat above k. So nothing greater than nums[k] was skipped, which makes nums[j] the correct answer.
Two passes are enough because an element's next greater element is at most one full lap away. If nums[k] is not resolved by the end of the first pass, the only candidates left are the elements before it, which the second pass replays. An element still on the stack after the second pass has nothing greater anywhere, so it keeps its -1.
Algorithm
- Create a result array of size n, initialized to -1.
- Create an empty stack that will store indices.
- Iterate
ifrom 0 to 2n-1: - Compute the actual index as
i % n. - While the stack is not empty and
nums[i % n]is greater thannums[stack.top()]: - Pop the top index from the stack.
- Set
result[popped index]tonums[i % n]. - If
i < n, pushionto the stack (only push during the first pass). - Return the result array.
Visualization and Code
Loading animation...
- Time Complexity: O(n). We iterate 2n times, and each of the n indices is pushed onto the stack at most once and popped at most once. The total number of push and pop operations is at most 2n.
- Space Complexity: O(n). The stack can hold at most n indices in the worst case (a strictly decreasing array where nothing gets popped during the first pass).