Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Next Greater Element II

MEDIUMProblemSolveExternal Links

Description

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.

Examples

Example 1

Input: nums = [1, 2, 1]

Output: [2, -1, 2]

Explanation: The first 1's next greater number is 2 (at index 1). The number 2 cannot find a next greater number anywhere in the circular array, so its answer is -1. The second 1's next greater number requires a circular search — wrapping back to the beginning finds 2 at index 1.

Example 2

Input: nums = [1, 2, 3, 4, 3]

Output: [2, 3, 4, -1, 4]

Explanation: Each element looks to the right (circularly) for the first element strictly greater than itself. The element 4 at index 3 is the maximum — no element in the circular array exceeds it, so its answer is -1. The last element 3 wraps around and finds 4 at index 3.

Constraints

  • 1 ≤ nums.length ≤ 10^4
  • -10^9 ≤ nums[i] ≤ 10^9

Editorial

Brute Force

Intuition

The most straightforward way to solve this problem is to simulate exactly what the problem asks: for each element, scan forward through the circular array until you find something larger.

Imagine standing in a circle of people, each holding a number card. For each person, you look clockwise around the circle one person at a time, asking: 'Is your number bigger than mine?' The first person who says 'yes' is your answer. If you go all the way around and nobody's number is bigger, the answer is -1.

To handle the circular nature programmatically, we use the modulo operator. Instead of literally connecting the end of the array back to the beginning, we compute the index as (i + j) % n, which naturally wraps around. For each element at index i, we check at most n-1 other elements (every element except itself).

Step-by-Step Explanation

Let's trace through nums = [3, 1, 2, 4]:

Step 1: Fix i=0 (value 3). Search circularly for the first element greater than 3.

  • j=1: nums[1]=1. Is 1 > 3? No.
  • j=2: nums[2]=2. Is 2 > 3? No.
  • j=3: nums[3]=4. Is 4 > 3? Yes! ans[0] = 4.

Step 2: Fix i=1 (value 1). Search for the first element greater than 1.

  • j=2: nums[2]=2. Is 2 > 1? Yes! ans[1] = 2.

Step 3: Fix i=2 (value 2). Search for the first element greater than 2.

  • j=3: nums[3]=4. Is 4 > 2? Yes! ans[2] = 4.

Step 4: Fix i=3 (value 4). Search circularly — this is where the circular property matters.

  • j=0 (wrapped): nums[0]=3. Is 3 > 4? No.
  • j=1 (wrapped): nums[1]=1. Is 1 > 4? No.
  • j=2 (wrapped): nums[2]=2. Is 2 > 4? No.
  • All elements checked. No element is greater than 4. ans[3] = -1.

Result: [4, 2, 4, -1]

Brute Force — Circular Scan for Each Element — Watch how the brute force checks each element one by one, scanning circularly through the rest of the array to find the first greater element. Notice how element 4 (the maximum) requires checking all other elements before concluding no answer exists.

Algorithm

  1. Create a result array of size n, initialized with -1
  2. For each index i from 0 to n-1:
    • For each offset j from 1 to n-1:
      • Compute circular index: idx = (i + j) % n
      • If nums[idx] > nums[i], set result[i] = nums[idx] and break
  3. Return the result array

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n, -1);
        
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < n; j++) {
                int idx = (i + j) % n;
                if (nums[idx] > nums[i]) {
                    result[i] = nums[idx];
                    break;
                }
            }
        }
        
        return result;
    }
};
class Solution:
    def nextGreaterElements(self, nums: list[int]) -> list[int]:
        n = len(nums)
        result = [-1] * n
        
        for i in range(n):
            for j in range(1, n):
                idx = (i + j) % n
                if nums[idx] > nums[i]:
                    result[i] = nums[idx]
                    break
        
        return result
import java.util.Arrays;

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < n; j++) {
                int idx = (i + j) % n;
                if (nums[idx] > nums[i]) {
                    result[i] = nums[idx];
                    break;
                }
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n²)

For each of the n elements, the inner loop scans up to n-1 elements in the worst case (when the current element is the maximum and no greater element exists). Total comparisons in the worst case: n × (n-1), which simplifies to O(n²).

Space Complexity: O(1)

We use only a few integer variables (i, j, idx) beyond the output array. The result array is required by the problem and does not count as auxiliary space. Therefore, extra space is constant.

Why This Approach Is Not Efficient

The brute force performs up to n-1 comparisons for each of n elements. With n up to 10^4, that's roughly 10^8 operations in the worst case — dangerously close to exceeding typical time limits.

The core inefficiency is that we throw away useful information between iterations. When processing element i, we discover relationships between elements (which ones are bigger, which are smaller), but we discard all of this when we move to element i+1 and start searching from scratch.

Consider what happens with the maximum element: it forces a complete scan of all n-1 other elements, and every one of those comparisons is wasted because they all fail. If we could somehow remember which elements are 'useful candidates' for being the next greater element, we could skip the redundant comparisons entirely.

Key insight: a monotonic stack lets us maintain a shrinking set of candidates. Instead of n separate searches of O(n) each, the stack processes all elements in O(n) total — each element enters and leaves the stack at most twice.

Bar chart comparing O(n²) brute force vs O(n) monotonic stack approach for n=10,000
Bar chart comparing O(n²) brute force vs O(n) monotonic stack approach for n=10,000

Optimal Approach - Monotonic Stack

Intuition

Instead of searching forward from each element, we flip the perspective: traverse the array from right to left and maintain a stack of 'candidate' next-greater elements.

Think of it this way. You're walking backward through a line of buildings, keeping a notebook of buildings you've passed. When you reach a new building, you look at your notebook and cross out every building that's shorter than or equal to the current one. Why? Because those shorter buildings are now hidden behind the current building — they can never be the 'first taller building' for anything further to the left. Whatever remains at the top of your notebook is the answer for the current building.

The stack naturally maintains a decreasing order from bottom to top (a monotonic decreasing stack). At any point, the stack contains only elements that could potentially be the next greater element for something to the left. Smaller elements get discarded because they become irrelevant once a larger element appears closer.

To handle the circular nature, we traverse the array twice. By iterating from index 2n-1 down to 0 and using i % n, we simulate one complete wrap around the array. The first pass (indices n-1 to 0) processes elements normally. The second pass (indices 2n-1 to n) pre-loads the stack with elements from the right side, so that when the first pass runs, the stack already contains the circular candidates.

Concept diagram showing a circular array with elements being processed right-to-left into a monotonic decreasing stack
Concept diagram showing a circular array with elements being processed right-to-left into a monotonic decreasing stack

Step-by-Step Explanation

Let's trace nums = [3, 1, 2, 4] using a monotonic decreasing stack, traversing the doubled array from right to left (i = 7 down to 0, using i % 4 for the actual index):

Step 1 (i=7, idx=3, val=4): Stack is empty — no candidate exists to the right. Push 4. Stack: [4].

Step 2 (i=6, idx=2, val=2): Stack top is 4. Since 4 > 2, we found the next greater element! ans[2] = 4. Push 2. Stack: [4, 2].

Step 3 (i=5, idx=1, val=1): Stack top is 2. Since 2 > 1, found it! ans[1] = 2. Push 1. Stack: [4, 2, 1].

Step 4 (i=4, idx=0, val=3): Pop 1 (1 ≤ 3) — too small to be anyone's answer. Pop 2 (2 ≤ 3) — also too small. Stack top is 4. Since 4 > 3, found it! ans[0] = 4. Push 3. Stack: [4, 3].

  • First pass complete. ans = [4, 2, 4, -1]. Only index 3 (the maximum) is unresolved.

Step 5 (i=3, idx=3, val=4 — second pass): Pop 3 (3 ≤ 4). Pop 4 (4 ≤ 4). Stack is now empty — no element in the entire circular array is greater than 4. ans[3] stays -1. Push 4.

Step 6: Remaining iterations (i=2 to i=0) reprocess elements but only confirm existing answers. Final result: [4, 2, 4, -1].

Monotonic Stack — Right-to-Left Traversal with Circular Handling — Watch how the monotonic decreasing stack efficiently finds next greater elements by discarding irrelevant candidates. Each element is pushed and popped at most twice across both passes, achieving O(n) total operations.

Algorithm

  1. Create a result array of size n, initialized with -1
  2. Create an empty stack (will store values, not indices)
  3. Iterate i from 2n-1 down to 0:
    • Compute idx = i % n (maps doubled index to actual array position)
    • While stack is not empty AND stack top ≤ nums[idx]: pop from stack
    • If stack is not empty: result[idx] = stack top (the next greater element)
    • Push nums[idx] onto the stack
  4. Return the result array

Code

#include <vector>
#include <stack>
using namespace std;

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n, -1);
        stack<int> stk;
        
        for (int i = 2 * n - 1; i >= 0; i--) {
            int idx = i % n;
            while (!stk.empty() && stk.top() <= nums[idx]) {
                stk.pop();
            }
            if (!stk.empty()) {
                result[idx] = stk.top();
            }
            stk.push(nums[idx]);
        }
        
        return result;
    }
};
class Solution:
    def nextGreaterElements(self, nums: list[int]) -> list[int]:
        n = len(nums)
        result = [-1] * n
        stack = []
        
        for i in range(2 * n - 1, -1, -1):
            idx = i % n
            while stack and stack[-1] <= nums[idx]:
                stack.pop()
            if stack:
                result[idx] = stack[-1]
            stack.append(nums[idx])
        
        return result
import java.util.Arrays;
import java.util.Stack;

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 2 * n - 1; i >= 0; i--) {
            int idx = i % n;
            while (!stack.isEmpty() && stack.peek() <= nums[idx]) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                result[idx] = stack.peek();
            }
            stack.push(nums[idx]);
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

Although we iterate 2n times and each iteration may pop elements from the stack, the total number of push and pop operations across all iterations is at most 2n each (every element is pushed at most twice — once per pass — and popped at most twice). The while loop's total work across all iterations is bounded by the total number of pops, which is O(n). Therefore, the overall time complexity is O(n).

Space Complexity: O(n)

The stack can hold at most n elements at any point (in the worst case, all elements are in decreasing order and none get popped during the first pass). The result array is the required output and does not count as auxiliary space. Thus, extra space is O(n) for the stack.