LeetCode 503: Next Greater Element II Solution in Python – A Step-by-Step Guide

What Is LeetCode 503: Next Greater Element II?

In LeetCode 503: Next Greater Element II, you’re given a circular array of integers, meaning after the last element, you loop back to the first. For each number, you need to find the next greater element ahead of it—or return -1 if none exists. For example, in [1, 2, 1], the next greater element for 1 is 2, for 2 is -1 (nothing bigger), and for the last 1 is 2 (circling back). This problem builds on LeetCode 496: Next Greater Element I, adding the circular twist.

Problem Statement

• Input: List of integers nums (circular).
• Output: List of integers—next greater element for each position, or -1 if none.
• Rules: Array is circular; search wraps around to the start.

Constraints

• 1 <= nums.length <= 10⁴
• -10⁹ <= nums[i] <= 10⁹

Examples

• Input: [1,2,1]
• Output: [2,-1,2]
• 1 → 2, 2 → -1, 1 → 2 (circular).
• Input: [1,2,3,4,3]
• Output: [2,3,4,-1,4]
• Each finds the next bigger value, wrapping if needed.
• Input: [5,4,3,2,1]
• Output: [-1,5,5,5,5]
• Only 5 has no greater; others loop to 5.

Understanding the Problem: Spinning for Bigger Numbers

To solve LeetCode 503 in Python, we need a function that processes each element in a circular array and finds the next greater value, looping back if necessary. A naive approach might check every element ahead for each position, but with up to 10⁴ elements, that’s too slow. Instead, we’ll use:

• Best Solution (Monotonic Stack): O(n) time, O(n) space—fast and clever.
• Alternative Solution (Brute Force): O(n²) time, O(1) space—simpler but inefficient.

Let’s dive into the stack solution with a breakdown that’s easy to follow!

Best Solution: Monotonic Stack with Circular Handling

Why the Monotonic Stack Wins

The monotonic stack is the top choice for LeetCode 503 because it’s efficient—O(n) time and O(n) space. It processes each element once (with a double pass for circularity), using a stack to track elements waiting for their next greater value. The circular twist is handled by simulating a double array or using modulo—super smart and fast! It’s like keeping a list of numbers waiting for a bigger friend to show up.

How It Works

Picture this as a spinning game:

• Step 1: Setup:
• Use a stack to hold indices of elements in decreasing order (monotonic).
• Initialize result array with -1s.
• Step 2: Double Pass:
• Iterate the array twice (or use modulo) to handle circularity.
• For each element, pop stack elements smaller than it, updating their next greater value.
• Step 3: Push:
• Push current index onto stack if not popped.
• Why It Works:
• Stack keeps track of unresolved elements.
• Circularity ensures every element gets a chance to find its next greater.

It’s like a Ferris wheel where smaller numbers hop off when a bigger one rolls by!

Step-by-Step Example

Example: [1,2,1]

• Init:
• stack = [], result = [-1, -1, -1], n = 3.
• First Pass (i = 0 to 2):
• i=0, nums[0]=1: Stack empty, push 0. stack = [0].
• i=1, nums[1]=2: 1 < 2, pop 0, result[0] = 2, push 1. stack = [1].
• i=2, nums[2]=1: 2 > 1, push 2. stack = [1, 2].
• Second Pass (i = 0 to 1):
• i=0, nums[0]=1: 1 = 1 < 2, no pop.
• i=1, nums[1]=2: 1 < 2, pop 2, result[2] = 2, 2 = 2, stop (i ≥ stack top).
• Result: [2, -1, 2].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [-1] * n  # Default to -1
        stack = []         # Monotonic stack of indices

        # Step 1: Two passes for circularity
        for i in range(2 * n):
            curr = nums[i % n]  # Circular access

            # Step 2: Pop smaller elements
            while stack and nums[stack[-1]] < curr:
                result[stack.pop()] = curr  # Update next greater

            # Step 3: Push current index (first pass only)
            if i < n:
                stack.append(i)

        return result

• Line 4: Result array starts with -1s (no greater found yet).
• Line 5: Stack holds indices of elements waiting.
• Line 8: Loop 2n times to simulate circularity.
• Line 9: Use modulo to wrap around.
• Lines 11-12: Pop stack if current is greater, update result.
• Lines 15-16: Push index in first pass only (avoids duplicates).
• Time Complexity: O(n)—each element pushed/popped once.
• Space Complexity: O(n)—stack size.

It’s like a spinning stack sorter!

Alternative Solution: Brute Force with Circular Iteration

Why an Alternative Approach?

The brute-force solution checks every element ahead for each position, looping back as needed. It’s O(n²) time and O(1) space (excluding output)—simple to understand but slow for large arrays. Perfect if you’re just starting and want clarity over speed.

How It Works

Think of this as a manual spin:

• Step 1: For each index i:
• Look ahead (circularly) for the next greater value.
• Step 2: If found, record it; if not, use -1.
• Step 3: Repeat for all positions.

It’s like spinning the wheel by hand for each number!

Step-by-Step Example

Example: [1,2,1]

• Init: result = [-1, -1, -1], n = 3.
• i=0, nums[0]=1: Check 2 (greater, stop), result[0] = 2.
• i=1, nums[1]=2: Check 1, 2 (loop), 1, 2—no greater, result[1] = -1.
• i=2, nums[2]=1: Check 1, 2 (greater), result[2] = 2.
• Result: [2, -1, 2].

Code for Brute Force

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [-1] * n

        for i in range(n):
            # Check all elements ahead circularly
            for j in range(1, n):
                next_idx = (i + j) % n
                if nums[next_idx] > nums[i]:
                    result[i] = nums[next_idx]
                    break

        return result

• Time Complexity: O(n²)—n positions, up to n checks each.
• Space Complexity: O(1)—just the result array.

It’s a slow but steady spinner!

Comparing the Two Solutions

• Monotonic Stack (Best):
• Pros: O(n) time, efficient.
• Cons: Stack logic.
• Brute Force (Alternative):
• Pros: O(n²) time, super simple.
• Cons: Too slow for big arrays.

Stack wins hands down!

Additional Examples and Edge Cases

• [1]: [-1]—no greater.
• [1,1,1]: [-1,-1,-1]—all same.
• [2,1,2]: [2,2,2]—circular ties.

Stack handles them all smoothly.

Complexity Recap

• Stack: Time O(n), Space O(n).
• Brute Force: Time O(n²), Space O(1).

Stack is the efficiency champ!

Key Takeaways

• Stacks: Monotonic = magic—learn at Python Basics!
• Circularity: Modulo or double pass.
• Greedy: Next greater is local.
• Fun: Spinning arrays rock!

Final Thoughts: Spin to Win!

LeetCode 503: Next Greater Element II in Python is a delightful stack challenge. The monotonic stack nails it with speed, while brute force keeps it basic. Want more? Try LeetCode 496: Next Greater Element I or LeetCode 739: Daily Temperatures. Ready to spin? Head to Solve LeetCode 503 on LeetCode and find those greater elements today!