Next Greater Element II

MediumStackmonotonic stack circular

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a **circular** integer array nums. Because the array is circular, the element that follows the last entry is the first entry (index 0), and traversal wraps around from the end back to the beginning. For every position i, find the **next greater element** of nums[i]. The next greater element is the first value you encounter that is strictly larger than nums[i] when scanning forward from i, continuing past the end of the array and wrapping around. The search may pass through every other element, but it stops at the first strictly larger value. If no such value exists anywhere in the array, the answer for that position is -1. Return an array answer of the same length as nums, where answer[i] holds the next greater element for nums[i]. A value is its own predecessor only once: while searching from index i you may visit up to n - 1 other positions, but you never count nums[i] itself as a candidate.

Examples

Input: nums = [1,2,1]
Output: [2,-1,2]
For the first 1, the next greater value is 2. For the 2, no larger value exists even after wrapping, so the answer is -1. For the last 1, wrapping around reaches the 2 at the front, giving 2.
Input: nums = [1,2,3,4,3]
Output: [2,3,4,-1,4]
The 4 has no larger value anywhere, so its answer is -1. The trailing 3 wraps around to find the 4 at the front.
Input: nums = [5,4,3,2,1]
Output: [-1,5,5,5,5]
5 is the maximum so it gets -1. Every smaller value wraps around to find the 5 at the front.

Constraints

  • `1 <= nums.length <= 10^4`
  • `-10^9 <= nums[i] <= 10^9`
  • The array is treated as circular: the next index after `n - 1` is `0`.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.