Next Greater Element II

Medium
69.

Next Greater Element II

Next Greater Element II is a medium coding problem on arrays, stack and monotonic stack.

Given a circular integer array nums, return the next greater number for every element. Searching wraps around the array; if no greater number exists, output -1 for that element.

Example 1

Input
nums = [1,2,1]
Output
[2,-1,2]
Explanation
The last 1 wraps around to find 2.

Example 2

Input
nums = [1,2,3,4,3]
Output
[2,3,4,-1,4]

Constraints

  • 1 <= nums.length <= 30
  • -100 <= nums[i] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var nextGreaterElements = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Next Greater Element II — Solution in Python, Java & C++

Next Greater Element II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Next Greater Element II is a medium coding problem on arrays, stack and monotonic stack.

  • Difficulty: Medium
  • Topics: Arrays, Stack, Monotonic Stack
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given a circular integer array nums, return the next greater number for every element. Searching wraps around the array; if no greater number exists, output -1 for that element.

Example 1

Input: nums = [1,2,1]
Output: [2,-1,2]
Explanation: The last 1 wraps around to find 2.

Example 2

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

Constraints

  • 1 <= nums.length <= 30
  • -100 <= nums[i] <= 100

Hints for Next Greater Element II

  1. Hint 1

    Iterate the array twice (indices modulo n) to simulate the wrap-around.

  2. Hint 2

    Only push indices during the first pass; the second pass just resolves.

How to solve Next Greater Element II

This is the standard monotonic-stack scan with one twist: the search wraps. Rather than physically concatenating the array to itself, walk 2n steps and index with i % n. The second lap gives every element left unresolved its chance to see the elements that come before it in the original order.

Approach

  1. Fill the answer array with -1, the value for elements that never find anything greater.
  2. Keep a stack of indices whose next greater element is still unknown.
  3. Loop i from 0 to 2n - 1 and take x = nums[i % n].
  4. While the stack is non-empty and the value at the top index is less than x, pop and set that index's answer to x.
  5. Push i only while i < n. The second lap resolves; it never adds new work.

Why it works

Two laps suffice because the next greater element is at most n - 1 steps away — beyond that you are back where you started. Restricting pushes to the first lap keeps exactly one stack entry per index, so no index is answered twice and the second lap only drains what the first left behind. Whatever survives both laps is a maximum of the array and correctly keeps -1.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Pushing during the second lap is the classic bug: indices get duplicated and can be overwritten with a later, non-nearest value.
  • Store indices, not values — you need the position to write the answer, and duplicate values are allowed here.
  • Use nums[i % n] for the value but the raw i < n test for pushing; mixing the two up breaks the wrap.

Reference solution

Python

from typing import List

def nextGreaterElements(nums: List[int]) -> List[int]:
    n = len(nums)
    out = [-1] * n
    st = []
    for i in range(2 * n):
        x = nums[i % n]
        while st and nums[st[-1]] < x:
            out[st.pop()] = x
        if i < n:
            st.append(i)
    return out

Java

public static int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] out = new int[n];
    Arrays.fill(out, -1);
    Deque<Integer> st = new ArrayDeque<>();
    for (int i = 0; i < 2 * n; i++) {
        int x = nums[i % n];
        while (!st.isEmpty() && nums[st.peek()] < x) out[st.pop()] = x;
        if (i < n) st.push(i);
    }
    return out;
}

C++

vector<int> nextGreaterElements(vector<int>& nums) {
    int n = nums.size();
    vector<int> out(n, -1);
    vector<int> st;
    for (int i = 0; i < 2 * n; i++) {
        int x = nums[i % n];
        while (!st.empty() && nums[st.back()] < x) {
            out[st.back()] = x;
            st.pop_back();
        }
        if (i < n) st.push_back(i);
    }
    return out;
}

JavaScript

var nextGreaterElements = function(nums) {
    const n = nums.length;
    const out = new Array(n).fill(-1);
    const st = [];
    for (let i = 0; i < 2 * n; i++) {
        const x = nums[i % n];
        while (st.length > 0 && nums[st[st.length - 1]] < x) out[st.pop()] = x;
        if (i < n) st.push(i);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Stack Data Structure