Next Greater Element III: Next Permutation on Digits

LeetCode 556 asks you to find the next greater integer using the same set of digits. If you have already solved Next Permutation, you will recognize the core idea immediately: this is the same algorithm, applied to the digits of a number instead of the elements of an array. The only twist is a 32-bit overflow check at the end.

The problem

Given a positive integer n, find the smallest integer that is greater than n and has exactly the same digits. Return -1 if no such integer exists or if the result does not fit in a 32-bit signed integer (i.e., is greater than 2^31 - 1).

For example, given n = 230241, the answer is 230412. Given n = 21, the answer is -1 because the digits are already in descending order.

The approach

This is the "next permutation" algorithm applied to the digit list of a number. You treat each digit as an element in an array, then run four steps:

1. Find the pivot. Scan from the rightmost digit toward the left. Find the first position i where digits[i] is less than digits[i + 1]. Everything to the right of i is in non-increasing order, meaning that suffix is already at its maximum arrangement. Position i is where you can make the number larger.

2. Find the swap target. Scan from the right again, looking for the smallest digit in the suffix that is larger than digits[i]. Because the suffix is non-increasing, the first digit you encounter that exceeds digits[i] is the correct one.

3. Swap. Exchange digits[i] and the swap target. After the swap, the suffix remains non-increasing.

4. Reverse the suffix. Reverse everything after index i. This turns the suffix from its maximum arrangement into its minimum, producing the smallest possible tail and therefore the smallest number greater than the original.

If step 1 finds no pivot (every digit is in non-increasing order), the number is already the largest permutation of its digits. Return -1. After building the result, also check whether it exceeds 2^31 - 1.

The solution

def nextGreaterElement(n: int) -> int:
    digits = list(str(n))
    length = len(digits)
    i = length - 2

    while i >= 0 and digits[i] >= digits[i + 1]:
        i -= 1

    if i < 0:
        return -1

    j = length - 1
    while digits[j] <= digits[i]:
        j -= 1

    digits[i], digits[j] = digits[j], digits[i]

    digits[i + 1:] = digits[i + 1:][::-1]

    result = int("".join(digits))
    return result if result <= 2**31 - 1 else -1

The first while loop finds the pivot by scanning left until digits[i] is less than digits[i + 1]. If i drops below zero, the digits are fully non-increasing and no greater number exists.

When a pivot exists, the second while loop finds the swap target by scanning right to left through the suffix. Since the suffix is non-increasing, the first value greater than digits[i] is the smallest such value.

After swapping, the suffix is reversed using slice assignment. Finally, the digit list is joined back into an integer, and the overflow check ensures the result fits in 32 bits.

Step-by-step walkthrough

Starting from 230241, the pivot is digit 2 at index 3. The swap target is 4 at index 4. After swapping and reversing the suffix, the result is 230412, which is the smallest number greater than 230241 using the same digits.

Complexity analysis

Here d is the number of digits in n. Converting the integer to a list of characters takes O(d). Each scan (finding the pivot, finding the swap target, reversing the suffix) is at most one pass over the digits. Building the result string and converting back to an integer also takes O(d). The space is O(d) for storing the digit list.

The building blocks

Next permutation template

The reusable pattern here is the next permutation algorithm itself. Once you can write it from memory, this problem and several others become a matter of plugging it into the right context.

def next_permutation(arr):
    n = len(arr)
    i = n - 2

    while i >= 0 and arr[i] >= arr[i + 1]:
        i -= 1

    if i >= 0:
        j = n - 1
        while arr[j] <= arr[i]:
            j -= 1
        arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1:] = arr[i + 1:][::-1]

This template works on any list where you want the lexicographically next arrangement. For Next Greater Element III, you just wrap it with digit extraction and overflow checking.

Edge cases

• Digits already in descending order. For n = 4321, no pivot exists. Return -1.
• Result exceeds 2^31 - 1. For n = 2147483476, the next permutation of the digits might produce a number larger than 2147483647. You must check and return -1 if so.
• Single digit. For n = 9, there is only one digit. No rearrangement is possible. Return -1.
• Two digits. For n = 12, the pivot is at index 0, the swap target is at index 1. Swap gives [2, 1], suffix reversal does nothing. Return 21.
• Repeated digits. For n = 11, both digits are the same. The pivot search fails because digits[0] >= digits[1]. Return -1. For n = 1221, the pivot is at index 1 (value 2 is not less than 2, but value 1 is less than 2), so the pivot is at index 0 (value 1 is less than 2). The result is 2112.

From understanding to recall

You can trace through the four steps on paper. But can you write the full solution, including the digit extraction and overflow check, from scratch in two minutes?

The next permutation algorithm has small details that trip people up under pressure: the comparison direction when scanning for the pivot (>= not >), scanning right to left for the swap target, remembering to reverse after the swap. These are recall problems, not conceptual ones. Drilling the pattern with spaced repetition makes it automatic so that when you see this problem in an interview, you write it without hesitation.

Related posts

• Next Permutation - The direct array version of the same algorithm
• Next Greater Element I - Stack-based next greater element, different approach but related naming
• Permutation Sequence - Another problem requiring deep understanding of permutation ordering

CodeBricks breaks Next Greater Element III into its next permutation building block and drills it with spaced repetition. You type the solution from scratch, repeatedly, until the pivot-swap-reverse sequence is muscle memory. When this problem appears in your interview, you do not pause to think. You just write it.