DSA sheet · Stack · Monotonic stack pattern

Next Greater Element II (Circular)

This is the same question as Next Greater Element, with one twist: the array is circular. After the last element, you wrap around to the first one. The teacher's message is that the stack logic doesn't change at all. We only need a way to "see" the array twice: walk 2n steps instead of n, and only save answers for the real indices. Circular arrays come up often, so this trick is worth learning once and for all.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Stacks, the monotonic stack, and what "circular" means
• Part A · Copy the array twice, then run the normal stack
• Part B · Same idea without copying: index % n
• Part C · Revision page

Part 0 · Before starting

Stack in 30 seconds

A stack is a pile where you only touch the top: LIFO = Last In, First Out. In Python we use a plain list:

All four are O(1). Never pop or peek an empty stack: it raises IndexError. That's why we always write while st and … and if st:. Drawings: left = bottom, right = top.

The monotonic stack (recap from Problem 2)

To find the next greater element (the first strictly bigger value to the right) for every index:

1. Walk from the right, so the right side is already summarised in the stack.
2. Pop while the top is <= x. Those items are hidden behind x: x is closer and at least as tall, so they can never be anybody's answer again.
3. If anything is left, the top is the answer. Otherwise the answer is −1.
4. Push x.

The stack is always strictly decreasing from bottom to top, the visible skyline to the right of the current index. Each item is pushed once and popped at most once → O(n).

What is a circular array?

Picture the numbers written around a clock face. Going "right" means going clockwise. After the last number you come back to the first one. So when we look for the next greater element and run out of numbers on the right, we continue from index 0.

      index 0
        (1)
       ↗    ↘
  (1)  ←───  (2)
index 2      index 1      clockwise: 0 → 1 → 2 → 0 → 1 …

Part A · Copy the array twice, then run the normal stack

LeetCode 503

1The question in simple words

Given a circular array nums, return for every index the next greater number: the first value strictly bigger than it, searching clockwise (to the right, and wrapping around to the start). If none exists anywhere, return −1.

• Index 0 (value 1): the next value 2 is bigger → 2.
• Index 1 (value 2): to the right is 1, then wrap to 1 (index 0). Nothing is bigger than 2 → −1.
• Index 2 (value 1): nothing on its right. In the non-circular problem the answer would be −1, but here we wrap: index 0 is 1 (not bigger), index 1 is 2 (bigger) → 2. This is the only answer that changed because of the circle.

Second example: [1, 2, 3, 4, 3] → [2, 3, 4, −1, 4]. The last 3 wraps around: 1 ✗, 2 ✗, 3 ✗ (equal), 4 ✓.

2What the constraints tell us

• LeetCode: 1 ≤ n ≤ 10⁴ → the array is never empty, but n = 1 is possible (answer [-1], since nothing can be bigger than itself).
• Values from −10⁹ to 10⁹ → negative numbers are allowed, even −1 itself. That's fine: in the answer, LeetCode defines −1 as "not found", and the comparisons work the same for negative values.
• n ≤ 10⁴ means even O(n²) ≈ 10⁸ might squeeze through, but the stack gives O(n), so we use it.

3Intuition: "circular" = "the array written twice"

The teacher's trick: whenever a question says circular, imagine the array copied right after itself:

Now, from index 2, "going right and wrapping" is the same as simply going right in the doubled array: you meet index 3 (a copy of index 0), then index 4 (a copy of index 1, value 2) ✓. Walking clockwise around the circle and walking straight through the doubled array read the same numbers in the same order.

So we can run the ordinary next-greater stack on the doubled array. The only care: answers are only needed for indices 0 … n−1. Indices n … 2n−1 are copies. We still process them, but only to fill the stack.

4Building the logic from the example

5Approach steps

1. arr = nums + nums, ans = [-1] * n, empty stack.
2. For i from 2n−1 down to 0, with x = arr[i]:
3. While the stack is not empty and top ≤ x → pop.
4. If i < n (a real index) and the stack is not empty → ans[i] = top.
5. Push x (always, real or copy).
6. Return ans.

6Code (Python)

class Solution:
    def nextGreaterElements(self, nums):
        n = len(nums)
        arr = nums + nums                    # the circle, unrolled twice
        ans = [-1] * n                       # answers only for the real indices
        st = []
        for i in range(2 * n - 1, -1, -1):   # right to left over 2n items
            x = arr[i]
            while st and st[-1] <= x:        # hidden forever -> throw away
                st.pop()
            if i < n and st:                 # real index AND something bigger exists
                ans[i] = st[-1]
            st.append(x)
        return ans

7Code line by line

8Dry run on [1, 2, 1] (doubled: 1 2 1 | 1 2 1)

Look at the first picture: after the copy half, the stack already "knows" the values that follow index 2 around the circle (1, then 2). That's exactly what index 2 needed.

9Complexity & remember

• Time O(n): the loop runs 2n times. Each of the 2n values is pushed once and popped at most once, so at most 2n pops. About 4n steps in total, still linear.
• Space O(n): the stack, plus the doubled array (2n).

Part B · Same idea without copying: index % n

1The question

Same as Part A. We just want to avoid physically building nums + nums.

2What the constraints tell us

Same as Part A (n from 1 to 10⁴). Nothing new, so this part only changes how we read the values.

3Intuition: the copy is fake, so compute where it points

Index 3 of the doubled array is just a copy of index 0, index 4 of index 1, and index 5 of index 2. In general, doubled index i holds nums[i % n] (the remainder after dividing by n).

So we loop i over 0 … 2n−1 and read nums[i % n]. No second array is needed.

4Building the logic

Everything else (pop rule, push rule, the i < n check) is the same as Part A.

5Approach steps

1. ans = [-1] * n, empty stack.
2. For i from 2n−1 down to 0: x = nums[i % n].
3. Pop while top ≤ x.
4. If i < n and the stack is not empty → ans[i] = top.
5. Push x. Return ans.

6Code (Python)

class Solution:
    def nextGreaterElements(self, nums):
        n = len(nums)
        ans = [-1] * n
        st = []
        for i in range(2 * n - 1, -1, -1):
            x = nums[i % n]                  # fake second copy: fold the index back
            while st and st[-1] <= x:
                st.pop()
            if i < n and st:                 # save only for the real indices
                ans[i] = st[-1]
            st.append(x)
        return ans

7Code line by line

8Dry run on [1, 2, 3, 4, 3]

n = 5, so i goes 9 → 0, and the value is nums[i % 5].

Notice: the largest value (4) always ends with −1, even in a circle. Nothing anywhere is bigger than it.

9Complexity & remember

• Time O(n): 2n loop steps, and at most 2n pushes and 2n pops in total.
• Space O(n): just the stack and the answer. No doubled array this time.

Part C · Revision page

s = Solution()
print(s.nextGreaterElements([1, 2, 1]))          # [2, -1, 2]
print(s.nextGreaterElements([1, 2, 3, 4, 3]))    # [2, 3, 4, -1, 4]
print(s.nextGreaterElements([5]))                # [-1]
print(s.nextGreaterElements([3, 3, 3]))          # [-1, -1, -1]
print(s.nextGreaterElements([5, 4, 3, 2, 1]))    # [-1, 5, 5, 5, 5]

Based on this video: Next Greater Element II | Circular Array | Monotonic Stack