LeetCode 556: Next Greater Element III Solution in Python – A Step-by-Step Guide

What Is LeetCode 556: Next Greater Element III?

In LeetCode 556: Next Greater Element III, you’re given an integer n, and your task is to return the smallest integer greater than n that can be formed by permuting its digits, or -1 if no such number exists within 32-bit integer bounds. For example, with n = 12, the next greater permutation is 21, but for n = 21, there’s no greater permutation, so return -1. This problem builds on LeetCode 31: Next Permutation for finding the next lexicographical permutation but adds constraints for integer overflow.

Problem Statement

• Input: n (int)—positive integer.
• Output: Integer—next greater permutation or -1 if none exists.
• Rules: Use same digits; result must be > n and ≤ 2³¹ - 1 (32-bit int max); otherwise return -1.

Constraints

• 1 <= n <= 10⁹

Examples

• Input: n = 12
• Output: 21
• Next permutation of "12" is "21".
• Input: n = 21
• Output: -1
• No greater permutation than "21".
• Input: n = 12443322
• Output: 13222344
• Next greater permutation of digits.

Understanding the Problem: Finding the Next Permutation

To solve LeetCode 556: Next Greater Element III in Python, we need to find the smallest integer greater than n by permuting its digits, ensuring it fits within 32-bit integer bounds (≤ 2³¹ - 1). A naive approach might generate all permutations (O(n!)), but with n up to 10⁹ (up to 9 digits), this is impractical. Instead, we can use the same logic as finding the next lexicographical permutation: identify a pivot where digits decrease, swap with the smallest greater digit to the right, and sort the rest. We’ll explore:

• Best Solution (Greedy Digit Swapping with Reversal): O(n) time, O(n) space—fast and optimal (n = digits).
• Alternative Solution (Brute-Force Permutation Check): O(n!) time, O(n) space—thorough but inefficient.

Let’s dive into the greedy solution with a friendly breakdown!

Best Solution: Greedy Digit Swapping with Reversal

Why Greedy Wins

The greedy digit swapping with reversal is the best for LeetCode 556 because it finds the next greater permutation in O(n) time and O(n) space (where n is the number of digits) by identifying the first decreasing point from the right, swapping it with the smallest greater digit to its right, and reversing the remaining digits to ensure the smallest increase. It’s like tweaking a number just enough to step up while keeping it minimal!

How It Works

Think of this as a number-tweaking recipe:

• Step 1: Convert to Digits:
• Turn integer n into a list of digits (e.g., 124 → [1, 2, 4]).
• Step 2: Find Pivot:
• From right, find first index i where digits[i] < digits[i+1] (decreasing point).
• If none, return -1 (already max permutation).
• Step 3: Find Swap Target:
• From right, find smallest digit > digits[i] after i, get its index j.
• Step 4: Swap and Reverse:
• Swap digits[i] and digits[j].
• Reverse digits[i+1:] to minimize the increase.
• Step 5: Check Bounds and Return:
• Convert back to integer; if ≤ 2³¹ - 1, return it, else -1.
• Why It Works:
• Next permutation is smallest increase by swapping and sorting tail.
• Linear scan ensures efficiency.

It’s like a digit-shuffling optimizer!

Step-by-Step Example

Example: n = 12443322

• Step 1: Digits = [1, 2, 4, 4, 3, 3, 2, 2].
• Step 2: Find pivot:
• From right: 2=2, 2<3 (i=5, digits[5]=3 < digits[6]=2, but check further).
• Continue: 3=3, 3>2, 4>3, 4=4, 2<4 (i=1, digits[1]=2 < digits[2]=4).
• Step 3: Find target:
• After i=1: [4, 4, 3, 3, 2, 2], smallest > 2 is 3 (j=4).
• Step 4: Swap and reverse:
• Swap [1, 2, 4, 4, 3, 3, 2, 2] → [1, 3, 4, 4, 2, 3, 2, 2].
• Reverse [4, 4, 2, 3, 2, 2] → [2, 2, 3, 2, 4, 4].
• Result = [1, 3, 2, 2, 3, 2, 4, 4].
• Step 5: Convert: 13222344, < 2³¹ - 1, return 13222344.
• Result: 13222344.

Example: n = 21

• Digits: [2, 1].
• Pivot: None (2 > 1, decreasing).
• Result: -1.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeclass Solution:
    def nextGreaterElement(self, n: int) -> int:
        # Step 1: Convert to digits list
        digits = list(str(n))
        length = len(digits)

        # Step 2: Find pivot (first decreasing point from right)
        i = length - 2
        while i >= 0 and digits[i] >= digits[i + 1]:
            i -= 1
        if i < 0:  # No pivot, already max
            return -1

        # Step 3: Find smallest digit > pivot to right
        j = length - 1
        while j > i and digits[j] <= digits[i]:
            j -= 1

        # Step 4: Swap pivot and target
        digits[i], digits[j] = digits[j], digits[i]

        # Step 5: Reverse digits after pivot
        left, right = i + 1, length - 1
        while left < right:
            digits[left], digits[right] = digits[right], digits[left]
            left += 1
            right -= 1

        # Step 6: Convert back and check bounds
        result = int("".join(digits))
        return result if result <= 2**31 - 1 else -1

• Line 4: Convert integer to digit list.
• Lines 7-10: Find pivot i where digits decrease from right.
• Lines 13-16: Find smallest greater digit j after i.
• Line 19: Swap digits at i and j.
• Lines 22-26: Reverse digits after i.
• Lines 29-30: Convert to int, check 32-bit bound.
• Time Complexity: O(n)—linear scans and reversal.
• Space Complexity: O(n)—digit list.

It’s like a digit-permutation wizard!

Alternative Solution: Brute-Force Permutation Check

Why an Alternative Approach?

The brute-force permutation check generates all possible permutations of the digits, finds the next greater one, and checks bounds, running in O(n!) time and O(n) space. It’s exhaustive but impractical for larger numbers, making it a good baseline for small inputs or understanding permutation logic.

How It Works

Picture this as a digit-shuffling explorer:

• Step 1: Convert to digits.
• Step 2: Generate all permutations.
• Step 3: Find next greater number.
• Step 4: Check bounds and return.

It’s like a permutation-testing lab!

Step-by-Step Example

Example: n = 12

• Digits: [1, 2].
• Permutations: [1, 2], [2, 1].
• Sorted: [1, 2], [2, 1].
• Next: 21 > 12.
• Result: 21.

Code for Brute-Force Approach

Copy codefrom itertools import permutations

class Solution:
    def nextGreaterElement(self, n: int) -> int:
        digits = list(str(n))
        perms = sorted(set(int("".join(p)) for p in permutations(digits)))

        for perm in perms:
            if perm > n:
                return perm if perm <= 2**31 - 1 else -1
        return -1

• Line 5: Generate all permutations, convert to ints, sort.
• Lines 7-9: Find next greater, check bounds.
• Time Complexity: O(n!)—permutation generation.
• Space Complexity: O(n)—digit list.

It’s a brute-force permutation checker!

Comparing the Two Solutions

• Greedy (Best):
• Pros: O(n), O(n), fast.
• Cons: Logic-based.
• Brute-Force (Alternative):
• Pros: O(n!), O(n), exhaustive.
• Cons: Impractical for large n.

Greedy wins for efficiency!

Additional Examples and Edge Cases

• 1: -1.
• 1234: 1243.
• 1999999999: -1 (overflow).

Greedy handles them all!

Complexity Recap

• Greedy: Time O(n), Space O(n).
• Brute-Force: Time O(n!), Space O(n).

Greedy’s the speed champ!

Key Takeaways

• Greedy: Smart swapping—learn at Python Basics!
• Brute-Force: Full permute.
• Numbers: Permutations are fun.
• Python: Greedy or brute, your pick!

Final Thoughts: Find That Next Number!

LeetCode 556: Next Greater Element III in Python is a clever permutation challenge. Greedy digit swapping with reversal is your fast track, while brute-force offers a thorough dive. Want more? Try LeetCode 31: Next Permutation or LeetCode 46: Permutations. Ready to permute? Head to Solve LeetCode 556 on LeetCode and find that next number today!