Back to Problems

Next Greater Element II

Medium
monotonic-stack

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.

Key Insight: To handle the circular nature, iterate through the array twice (conceptually concatenating it with itself). Use modulo arithmetic to wrap around. The monotonic stack tracks indices, and we only need to assign results in the first pass.

Example 1

Input: nums = [1,2,1]
Output: [2,-1,2]
Explanation: For 1 at index 0: next greater is 2. For 2: no greater exists even circularly. For 1 at index 2: wraps around to find 2.

Example 2

Input: nums = [1,2,3,4,3]
Output: [2,3,4,-1,4]
Explanation: For 4: no greater exists in circular array. For 3 at end: wraps around to find 4.

Constraints

  • •1 <= nums.length <= 10^4
  • •-10^9 <= nums[i] <= 10^9
Show Hints (4)
Hint 1: How can we simulate a circular array without actually duplicating it?
Hint 2: Iterate through the array twice (2*n iterations) and use index % n to access elements.
Hint 3: Maintain a monotonic decreasing stack of indices.
Hint 4: Only assign results for indices in the first pass (i < n) to avoid duplicates.
Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor
Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?