Next Greater Element II

Practice Link

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.

Brute Force#

For each element, scan forward (circularly) to find the first element greater than it. Use modular arithmetic to wrap around the array. If no greater element is found after a full loop, store -1.

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, -1);

        for (int i = 0; i < n; i++) {
            for (int j = 1; j < n; j++) {
                if (nums[(i + j) % n] > nums[i]) {
                    ans[i] = nums[(i + j) % n];
                    break;
                }
            }
        }
        return ans;
    }
};

Time Complexity: O(n²)

Space Complexity: O(1) extra (excluding output)

Intuition#

• Everything exactly same as next greater element I, except now we have a circular array
• We will hypothetically assume an array of 2*n size and follow same steps.
• We only update the resultant array if current idx < n

Solution - Monotonic Stack#

The circular array is handled by simulating two passes through nums without actually duplicating it: iterate i from 2n-1 down to 0 and use i % n to access elements. The second pass (indices n to 2n-1) loads elements into the stack so they are available as "future" candidates for elements in the first pass. Results are written to ans[i] only when i < n to avoid writing out-of-bounds. Everything else mirrors the standard next-greater-element monotonic stack approach: pop smaller-or-equal entries and record the stack top as the next greater value.

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        stack<int> stk;
        int n = nums.size();
        vector<int> ans(n,-1);

        for(int i=2*n-1;i>=0;i--)
        {
            while(!stk.empty() && stk.top() <= nums[i%n])
                stk.pop();

            if(!stk.empty() && i<n)
                ans[i] = stk.top();

            stk.push(nums[i%n]);
        }
        return ans;
    }
};

Time Complexity: O(2n)

Space Complexity: O(n)

Follow-up: Left-to-Right Traversal#

The right-to-left solution resolves each index i immediately by checking what's already on the stack. Going left-to-right flips the model: instead of looking ahead, you push unresolved indices onto the stack and resolve them when a larger element arrives.

How the circular wrap changes: in the right-to-left version, the second pass (indices n to 2n-1) pre-loads future circular candidates into the stack. Left-to-right handles it differently: run two full passes (indices 0 to 2n-1), but only push new indices in the first pass (i < n). The second pass (i >= n) serves purely as the circular "wrap-around" — it can resolve pending indices but adds nothing new to the stack.

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, -1);
        stack<int> stk;  // indices of elements awaiting their next greater

        for (int i = 0; i < 2 * n; i++) {
            while (!stk.empty() && nums[stk.top()] < nums[i % n]) {
                ans[stk.top()] = nums[i % n];
                stk.pop();
            }
            if (i < n) stk.push(i);  // only enqueue real indices
        }
        return ans;
    }
};

Time Complexity: O(2n) — each index is pushed and popped at most once
Space Complexity: O(n)

Why the guard i < n matters: without it, indices n through 2n-1 would be pushed as duplicates of real indices, corrupting the answer array. The second pass is purely a "source of values" for resolving the remaining stack entries — not a source of new queries.