Next Greater Element II
Task example: Next Greater Element II
For each position, move right through the array, continuing at the beginning when you reach the end. Return the first strictly larger value you encounter. Write -1 if no such value exists.
nums = [1,2,1] answer = [2,-1,2]
The last 1 wraps past the first 1 before reaching 2. Equal values do not count.
View LeetCode 50301 / Brute force
Brute force: video explanation
nums = [1,2,1] answer = [2,-1,2]
Prefer reading? Follow the steps below.
- Start at index i and check the next n - 1 positions in order. Use (i + distance) % n to wrap back to index zero.
- When a candidate exceeds nums[i], store its value and stop this walk. If no candidate qualifies, keep -1.
- For the last 1, check index 0 first. Skip the equal 1, then record the 2 at index 1.
Time complexity · O(n²)
Each of n positions can inspect n - 1 candidates. An all-equal array forces every comparison.
Space complexity · O(1)
Apart from the returned array, the scan uses only indices.
PYTHONLive code trace
02 / Monotonic stack (optimal)
Monotonic stack: video explanation
nums = [1,2,1] answer = [2,-1,2]
Prefer reading? Follow the steps below.
- Read the array twice using step % n. On the first pass, push unresolved indices. Their values decrease or stay equal from bottom to top.
- While the current value is strictly larger than the value at the top index, pop that index and fill its answer. It has been waiting since its first visit.
- On the second pass, resolve waiting indices without pushing more. For the last 1, the second visit to 2 supplies the answer.
One arriving value can resolve several indices, so the stack avoids starting a separate search at every position.
Time complexity · O(n)
There are 2n visits. Each index is pushed once and popped at most once.
Space complexity · O(n)
The stack can hold n indices. This excludes the required output array.
PYTHONLive code trace