2Brute2Best
🔥0

Next Greater Element II (circular)

Medium·LeetCode #503 Pro OnlySlight Variation
LeetCode
01

Problem Statement

You get an array nums that is circular: after the last element, you continue from the first one again.

For each element, find its next greater number: the first number bigger than it that you meet while walking forward from it, wrapping around the end if needed. If no such number exists anywhere, the answer is -1.

Input

An integer array nums (values can repeat and can be negative).

Output

An array ans of the same length, where ans[i] is the next greater number of nums[i] going round the circle, or -1.

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

The first 1 sees 2 right away. 2 is the biggest, so -1. The last 1 wraps around to the start, passes 1, and finds 2.

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

The last 3 has nothing after it in a straight line, but wrapping around it meets 1, 2, then 4.

Constraints
  • • 1 ≤ nums.length ≤ 10^4
  • • −10^9 ≤ nums[i] ≤ 10^9
02

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“next greater number”
→ First bigger value going forward → decreasing monotonic stack.
“circular array”
→ After the end you continue at the start → walk twice with `i % n`.
“values can repeat”
→ Store indices, not values, and pop only on strictly bigger.
03

Approach Complexity Ladder

Brute Force — walk round the circle from each elementO(N²)O(1)

For each i, check the next n − 1 positions using % n

Optimal — decreasing stack over two lapsO(N)O(N)

Run the next-greater stack for i = 0 … 2n − 1 with nums[i % n]; push only in lap 1

Brute Force Intuition

For each index i, check positions (i+1) % n, (i+2) % n, … for n − 1 steps. The first bigger value is the answer. If none is found, it stays -1.

Recognition rule for this sub-pattern:

Need the first bigger value to the right (or left). Keep a decreasing stack; a bigger arrival resolves everyone smaller.
Remember this · Monotonic Stack
Trigger
Next/previous greater or smaller element, spans, histogram areas, "for each element, how far does it dominate?"
Think
When a new element arrives, which older elements can never be the answer again?
Key question
Is my stack increasing or decreasing, and what do I record when I pop?
Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms
Interactive step-by-step playback with pointer & array state transitions
52 comprehensive LLD chapters
Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions
40 C++ basics labs & hardware memory models
Vtables, byte layouts, assembly insights, and multi-threading race conditions
Production-ready C++23 source code
Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways
Create Free AccountLog in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Monotonic Stack translate into production architectures and low-level memory mechanics.

LLD Architecture

Undo / Redo Framework (Command Pattern)

State snapshot management and history stack unwinding.

Explore Track
C++ Internals

Move Semantics & Rvalue References

Eliminating deep copies when pushing and popping complex objects on stacks.

Explore Track
Daily TemperaturesCar Fleet