Course4all
Join us on telegram
Home/dsa/Stack/Next Greater Element II

Next Greater Element II

Master this topic with zero to advance depth.

Next Greater Element II

Given a circular integer array nums, return the next greater number for every element. Circularly means after the last element, we search from the beginning.

Visual Representation

nums = [1, 2, 1] Pass 1: 1. Index 0 (1): Stack [0] 2. Index 1 (2): 2 > 1. ans[0]=2. Pop 0, Push 1. Stack [1] 3. Index 2 (1): 1 < 2. Push 2. Stack [1, 2] Pass 2 (Circular): 4. i=0 (1): 1 < 1 (top). Skip. 5. i=1 (2): 2 > 1 (top). ans[2]=2. Pop 2. Stack [1] Final Result: [2, -1, 2]
Medium

Examples

Input: nums = [1,2,1]
Output: [2,-1,2]
Approach 1

Level I: Brute Force (Double Pass Circular Scan)

Intuition

For each element, simulate the circular search by iterating up to 2N positions using modulo. When we find the first element greater than the current one, store the distance. This is straightforward but slower.

⏱ O(N^2) — for each of the N elements, we scan up to N positions circularly.💾 O(1) excluding the output array.
java
import java.util.Arrays;

public class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, -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]) { res[i] = nums[idx]; break; }
            }
        }
        return res;
    }
    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution().nextGreaterElements(new int[]{1,2,1})));
    }
}
Approach 2

Level II: Circular Brute Force (Modulo Operator)

Intuition

Instead of two physical passes or flattening the array, we can use the modulo operator % to wrap around. For each element at index i, we check elements from (i+1) % n to (i + n - 1) % n. This is the same complexity as Level I but emphasizes the use of modular arithmetic for circular data structures.

⏱ O(N^2)💾 O(1) excluding output array.
java
public class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = -1;
            for (int k = 1; k < n; k++) {
                if (nums[(i + k) % n] > nums[i]) {
                    res[i] = nums[(i + k) % n];
                    break;
                }
            }
        }
        return res;
    }
}
Approach 3

Level III: Optimal (Monotonic Stack, Double Pass)

Intuition

To handle the circularity, we can conceptually concatenate the array with itself. In practice, we iterate from 0 to 2N-1 and use modulo i % N to access elements. A monotonic stack stores indices of elements looking for their next greater neighbor.

⏱ O(N)💾 O(N)

Detailed Dry Run

ii % NValStackans Update
001[0]-
112[1]ans[0]=2
221[1, 2]-
301[1, 2]-
412[1]ans[2]=2
java
import java.util.*;

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(Arrays.toString(sol.nextGreaterElements(new int[]{1,2,1}))); // [2, -1, 2]
    }
}

⚠️ Common Pitfalls & Tips

Modding i % n is essential for circular behavior. Only push to the stack in the first pass i < n to avoid infinite loops or duplicates.

← Previous QuestionNext Greater Element I
Next Question →Largest Rectangle in Histogram