LeetCode 556: Next Greater Element III

Problem Restatement

We are given a positive integer n.

We need to rearrange its digits to form the smallest integer that is greater than n.

The new integer must use exactly the same digits as n.

If no greater integer can be formed, return -1.

If the answer is greater than the 32-bit signed integer limit, return -1.

The official constraint is:

1 <= n <= 2**31 - 1

The return value must also fit inside:

2**31 - 1

The problem examples include n = 12, output 21, and n = 21, output -1. The statement requires the smallest greater integer using exactly the same digits.

Input and Output

Example function shape:

def nextGreaterElement(n: int) -> int:
    ...

Examples

Example 1:

n = 12

The digits are:

["1", "2"]

The only greater arrangement is:

21

So the answer is:

21

Example 2:

n = 21

The digits are already in descending order:

2, 1

There is no way to rearrange them into a greater number.

So the answer is:

-1

Example 3:

n = 12443322

We want the next greater number, not just any greater number.

The answer is:

13222344

First Thought: Try All Permutations

One direct idea is to generate every permutation of the digits.

Then we can keep only the numbers greater than n, sort them, and return the smallest one.

This is correct for small inputs, but it is too expensive.

If n has d digits, there can be up to:

d!

permutations.

A 32-bit integer has at most 10 digits, so this may look possible, but handling duplicates, sorting, and converting many permutations is unnecessary. There is a direct linear algorithm.

Key Insight

This is the same idea as the classic next permutation algorithm.

We want the next number in lexicographic order of digit sequences.

To make the number just slightly larger, we should change the number as far to the right as possible.

Consider:

n = 12443322

Digits:

1 2 4 4 3 3 2 2

Scan from right to left and find the first position where a digit is smaller than the digit after it.

That position is the pivot.

Here:

2 < 4

at the second digit.

The suffix after that pivot is:

4 4 3 3 2 2

This suffix is in descending order, which means it is already the largest possible arrangement for those digits. To get the next greater number, we must increase the pivot slightly, then make the suffix as small as possible.

Algorithm

Convert n to a list of digit characters.

1. Find the pivot:

   1. Start from the second-to-last digit.
   2. Move left while digits[i] >= digits[i + 1].
   3. If no pivot exists, return -1.

2. Find the swap digit:

   1. Start from the last digit.
   2. Move left until finding a digit greater than digits[i].

3. Swap the pivot and the swap digit.

4. Reverse the suffix after the pivot.

5. Convert the digits back to an integer.

6. If the result is greater than 2^31 - 1, return -1. Otherwise, return the result.

Why Reversing the Suffix Works

Before the swap, the suffix after the pivot is in descending order.

After we swap the pivot with the smallest possible larger digit from the suffix, the suffix is still in descending order.

To get the smallest number greater than the original, the suffix must become as small as possible.

For digits, the smallest order is ascending order.

Since the suffix is descending, reversing it makes it ascending.

Correctness

The algorithm finds the rightmost pivot i such that:

digits[i] < digits[i + 1]

Every digit after i forms a non-increasing suffix. This means the suffix is already the largest possible arrangement of those suffix digits. Therefore, no rearrangement only inside the suffix can make the number greater.

So any greater number using the same digits must change position i or some earlier position. To make the increase as small as possible, we change the rightmost possible position, which is exactly i.

Next, the algorithm chooses the rightmost digit greater than digits[i]. Because the suffix is non-increasing, this is the smallest digit in the suffix that is still greater than the pivot. Swapping with it gives the smallest possible increase at position i.

Finally, the algorithm reverses the suffix to make it ascending. This produces the smallest possible suffix after increasing the pivot.

Therefore, the result is greater than n, uses exactly the same digits, and is the smallest such integer. If no pivot exists, all digits are in descending order, so no greater arrangement exists.

Complexity

Let d be the number of digits in n.

Since n is a 32-bit integer, d <= 10, but the algorithm is still linear in the number of digits.

Implementation

class Solution:
    def nextGreaterElement(self, 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:] = reversed(digits[i + 1:])

        ans = int("".join(digits))
        if ans > 2**31 - 1:
            return -1

        return ans

Code Explanation

We first convert the integer into a mutable list:

digits = list(str(n))

Then we find the pivot:

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

If no pivot exists, the digits are in descending order:

if i < 0:
    return -1

Then we find the digit to swap with the pivot:

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

Because the suffix is descending, scanning from the right finds the smallest digit greater than the pivot.

Then we swap:

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

Finally, we reverse the suffix:

digits[i + 1:] = reversed(digits[i + 1:])

This makes the suffix as small as possible.

After rebuilding the integer, we check the 32-bit limit:

ans = int("".join(digits))
if ans > 2**31 - 1:
    return -1

Testing

def run_tests():
    s = Solution()

    assert s.nextGreaterElement(12) == 21
    assert s.nextGreaterElement(21) == -1
    assert s.nextGreaterElement(123) == 132
    assert s.nextGreaterElement(12443322) == 13222344
    assert s.nextGreaterElement(1999999999) == -1
    assert s.nextGreaterElement(230241) == 230412
    assert s.nextGreaterElement(115) == 151
    assert s.nextGreaterElement(9) == -1

    print("all tests passed")

run_tests()