An integer array nums is treated as circular, so traversal continues from the first position after the final position. For every array position, find the first value encountered later in circular order with a strictly greater value.
Store -1 when a full circular search contains no greater value. Return all answers in the original position order.
Example 1
Input: nums = [1, 2, 1]
Output: [2, -1, 2]
Explanation: The first 1 reaches 2 directly. Value 2 has no greater value. The final 1 wraps around and reaches 2.
Example 2
Input: nums = [3, 3, 3]
Output: [-1, -1, -1]
Explanation: Equal values are not strictly greater, so every circular search ends without a valid answer.
Brute Force Approach
Since the array is circular, the search for the Next Greater Element can continue from the beginning after reaching the last index. Modulo indexing allows this wraparound without creating another array.
For each element, check only the next N - 1 positions, because the element should not be compared with itself. The first strictly greater value encountered is its Next Greater Element. If no such value is found, the answer remains -1.
Algorithm
Create an answer array of size
Nand initialize every position with-1, because some elements may not have a greater value in circular order.Consider each array index as the current starting position.
Check offsets from
1toN - 1, so every other position is visited exactly once.Calculate the candidate index using
(currentIndex + offset) % N, so the search wraps back to index0after reaching the end.Compare the candidate value with the current value.
When a strictly greater value is found:
Store that value in the corresponding answer position.
Stop searching because the first greater value encountered is the nearest one in circular order.
Keep
-1if no greater value is found.Return the completed answer array.
Dry Run
Next Greater Element 2 Brute
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Finds next greater values by circular scanning. vector<int> nextGreaterElements(vector<int>& nums) { int n = nums.size(); vector<int> answer(n, -1); // Process every position independently. for (int i = 0; i < n; i++) { // Check one round after the starting position. for (int offset = 1; offset < n; offset++) { int nextIndex = (i + offset) % n; // A larger value ends the nearest search. if (nums[nextIndex] > nums[i]) { answer[i] = nums[nextIndex]; break; } } } return answer; }};// Driver codeint main() { vector<int> nums = {2, 1, 2, 4, 3}; Solution obj; vector<int> answer = obj.nextGreaterElements(nums); for (int value : answer) { cout << value << " "; } cout << endl; return 0;}Note: Brute force may fail for large arrays. Repeated circular scans create quadratic work, so an online judge may report Time Limit Exceeded.
Complexity Analysis
Time Complexity: O(N2), because every position may inspect the other N - 1 positions during a full circular search.
Space Complexity: O(N), because the returned answer array stores one result per position; auxiliary space apart from the returned array is O(1).
Optimal Approach
The efficient way to find the Next Greater Element is already discussed in the Next Greater Element problem using a monotonic stack. The only additional challenge here is handling the circular nature of the array.
Handling circular arrays:
One way is to copy the array and append it again, but this uses extra space. Instead, we can hypothetically double the array using the modulus operator. Traverse from 2 * N - 1 to 0 and access elements using index % N.
In the first pass, only prepare the stack. In the second pass, use the stack top as the Next Greater Element if available; otherwise, store -1. After processing each element, push it into the stack for future comparisons.
Algorithm
Initialize an answer array of size
Nwith-1and an empty stack to store possible next-greater candidates.Traverse virtual indices from
2 * N - 1down to0, simulating two reverse passes for circular array coverage.Map each virtual index using
index % N, allowing access to valid array positions after crossing the first index.Remove stack values smaller than or equal to
nums[index], because such values cannot become a next greater answer for the current position or any farther-left position.Store the stack top in
answer[index]only during the real pass when a greater candidate remains available.Push
nums[index]after processing the current position, allowing the current value to become a candidate for positions farther left.Return the completed answer array after both virtual passes finish.
Dry Run
Next Greater Element II Optimal Approach
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Finds next greater values with a monotonic stack. vector<int> nextGreaterElements(vector<int>& nums) { int n = nums.size(); vector<int> answer(n, -1); stack<int> candidates; // Two reverse passes simulate circular order. for (int i = 2 * n - 1; i >= 0; i--) { int index = i % n; // Blocked values cannot be strictly greater. while (!candidates.empty() && candidates.top() <= nums[index]) { candidates.pop(); } // Only the real pass writes final answers. if (i < n && !candidates.empty()) { answer[index] = candidates.top(); } candidates.push(nums[index]); } return answer; }};// Driver codeint main() { vector<int> nums = {2, 1, 2, 4, 3}; Solution obj; vector<int> answer = obj.nextGreaterElements(nums); for (int value : answer) { cout << value << " "; } cout << endl; return 0;}Complexity Analysis
Time Complexity: O(N), because two passes perform 2N iterations and every stored value is pushed and popped only a constant number of times.
Space Complexity: O(N), because the monotonic stack and returned answer array can each contain N values.
Interview follow-up Questions
No. The comparison is strict. For nums = [2, 2], both answers are -1.
Be the first to add a comment.