Difficulty: 🟡 Medium
Topics: Math, Two Pointers, String

Solution

LeetCode 556 - Next Greater Element III

Problem Understanding

This problem asks us to find the smallest integer that is strictly greater than a given integer n, while using exactly the same digits as n.

In other words, we are allowed to rearrange the digits of the number, but we cannot add or remove digits. Among all possible rearrangements that produce a larger number, we must return the smallest valid one.

For example, if n = 12, the possible rearrangements are:

12
21

The only number larger than 12 is 21, so the answer is 21.

If n = 21, the rearrangements are:

21
12

Neither rearrangement is greater than 21, so the answer is -1.

The problem also introduces an important restriction: the resulting number must fit inside a signed 32-bit integer. That means the final answer must be less than or equal to:

2^31 - 1 = 2147483647

If a valid larger permutation exists but exceeds this limit, we must return -1.

The input size is relatively small because the maximum possible integer has at most 10 digits. This means we do not need extremely advanced optimizations, but we still want an efficient and clean solution.

Several edge cases are important:

The digits may already be in descending order, such as 321, meaning no greater permutation exists.
Digits may repeat, such as 115.
The next permutation may overflow 32-bit integer range.
Very small inputs like single-digit numbers always return -1.
The correct answer must be the smallest larger permutation, not just any larger permutation.

This problem is essentially asking for the "next lexicographical permutation" of the digits.

Approaches

Brute Force Approach

A brute-force solution would generate every possible permutation of the digits, convert each permutation into an integer, filter out values greater than n, and then return the minimum among them.

This approach is correct because it exhaustively checks all possible digit arrangements. If a larger arrangement exists, the algorithm will eventually find it.

However, the number of permutations grows factorially with the number of digits. If the number has 10 digits, there can be up to:

10! = 3,628,800

possible permutations.

Generating all permutations, especially with repeated digits, becomes very inefficient. Sorting and filtering those permutations further increases the cost. Although the input size is limited, this approach is unnecessarily expensive.

Optimal Approach

The key observation is that we do not need to generate every permutation. We only need the next larger arrangement in lexicographical order.

This is exactly the classic "next permutation" algorithm.

The idea works because lexicographical ordering of digit sequences corresponds directly to numerical ordering for numbers with the same length.

The algorithm finds the first position from the right where the digits stop decreasing. That position identifies where we can make a slightly larger number.

Then we:

Swap that digit with the smallest larger digit to its right.
Reverse the suffix after that position to make it as small as possible.

This guarantees that we produce the smallest number larger than the original.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(d! × d)	O(d! × d)	Generates all permutations of digits
Optimal	O(d)	O(d)	Uses next permutation algorithm

Here, d is the number of digits.

Algorithm Walkthrough

Optimal Algorithm

Convert the integer into a list of digits.

Working with a mutable list makes swapping and reversing easier than manipulating integers directly. 2. Traverse the digits from right to left to find the pivot index.

We look for the first index i where:

digits[i] < digits[i + 1]

This identifies the point where the descending order breaks.

Everything to the right of this index is already in descending order, meaning it is currently the largest possible arrangement for that suffix. 3. If no such pivot exists, return -1.

If the entire number is in descending order, there is no larger permutation possible.

Example:

Find the smallest digit to the right of the pivot that is larger than the pivot digit.

We scan from the end toward the pivot because the suffix is descending. The first digit larger than the pivot is the correct choice. 5. Swap the pivot digit with that larger digit.

This creates a number that is larger than the original. 6. Reverse the suffix after the pivot index.

Before the swap, the suffix was descending. After the swap, reversing it produces the smallest possible ordering of those remaining digits.

This step guarantees the result is the smallest valid larger number. 7. Convert the digit list back into an integer. 8. Check for 32-bit overflow.

If the result exceeds 2147483647, return -1. 9. Otherwise, return the result.

Why it works

The algorithm works because it modifies the number in the smallest possible way that still increases its value.

The pivot identifies the rightmost position where an increase is possible. Swapping with the next larger digit creates the smallest increase at that position. Reversing the suffix then minimizes everything after the pivot.

This combination guarantees that the resulting number is the immediate next permutation, which is exactly the smallest greater integer using the same digits.

Python Solution

class Solution:
    def nextGreaterElement(self, n: int) -> int:
        digits = list(str(n))
        length = len(digits)

        # Step 1: Find pivot
        pivot = length - 2

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

        # No next permutation exists
        if pivot < 0:
            return -1

        # Step 2: Find smallest larger digit from the right
        swap_index = length - 1

        while digits[swap_index] <= digits[pivot]:
            swap_index -= 1

        # Step 3: Swap
        digits[pivot], digits[swap_index] = (
            digits[swap_index],
            digits[pivot],
        )

        # Step 4: Reverse suffix
        digits[pivot + 1:] = reversed(digits[pivot + 1:])

        result = int("".join(digits))

        # Step 5: Check 32-bit integer limit
        if result > 2**31 - 1:
            return -1

        return result

The implementation begins by converting the number into a list of characters so that individual digits can be modified efficiently.

The first loop searches from right to left for the pivot index. This identifies the first digit that can be increased while still producing a valid next permutation.

If no pivot is found, the digits are entirely descending, so the function immediately returns -1.

The second loop finds the smallest digit larger than the pivot digit by scanning from the right side. Because the suffix is descending, the first valid digit encountered is the optimal choice.

After swapping, the suffix is reversed to transform it into ascending order. This ensures the resulting number is the smallest possible larger arrangement.

Finally, the digits are joined back into an integer, and the overflow check ensures compliance with the 32-bit signed integer constraint.

Go Solution

func nextGreaterElement(n int) int {
	digits := []byte(strconv.Itoa(n))
	length := len(digits)

	// Step 1: Find pivot
	pivot := length - 2

	for pivot >= 0 && digits[pivot] >= digits[pivot+1] {
		pivot--
	}

	// No next permutation exists
	if pivot < 0 {
		return -1
	}

	// Step 2: Find smallest larger digit
	swapIndex := length - 1

	for digits[swapIndex] <= digits[pivot] {
		swapIndex--
	}

	// Step 3: Swap
	digits[pivot], digits[swapIndex] =
		digits[swapIndex], digits[pivot]

	// Step 4: Reverse suffix
	left := pivot + 1
	right := length - 1

	for left < right {
		digits[left], digits[right] =
			digits[right], digits[left]

		left++
		right--
	}

	result, _ := strconv.Atoi(string(digits))

	// Step 5: Check 32-bit integer limit
	if result > math.MaxInt32 {
		return -1
	}

	return result
}

The Go implementation follows the same logic as the Python version, but there are a few language-specific differences.

Go strings are immutable, so the number is converted into a []byte slice for efficient in-place modifications.

Instead of Python slicing and reversing, the suffix reversal is implemented manually using two pointers.

Go also requires explicit conversion between strings and integers using the strconv package.

The overflow check uses math.MaxInt32, which improves readability compared to hardcoding the value.

Worked Examples

Example 1

Input:

n = 12

Initial digits:

['1', '2']

Step 1: Find Pivot

We scan from right to left.

Index	Comparison	Result
0	1 < 2	Pivot found at index 0

Pivot digit:

Step 2: Find Swap Digit

Scan from the right for the first digit greater than 1.

Index	Digit	Greater Than 1?
1	2	Yes

Swap index:

Step 3: Swap

Before swap:

['1', '2']

After swap:

['2', '1']

Step 4: Reverse Suffix

Suffix after pivot:

['1']

Reversing does not change anything.

Final digits:

['2', '1']

Result:

Example 2

Input:

n = 21

Initial digits:

['2', '1']

Step 1: Find Pivot

Index	Comparison	Result
0	2 >= 1	Continue

No pivot exists.

The digits are entirely descending, meaning this is already the largest possible arrangement.

Result:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(d)	Each digit is visited a constant number of times
Space	O(d)	Digits are stored in a mutable list or slice

The algorithm performs several linear scans across the digits:

One scan to find the pivot
One scan to find the swap index
One reversal of the suffix

Each operation is linear in the number of digits, and the number of digits is at most 10. Therefore, the runtime is extremely efficient.

The space complexity comes from storing the digits separately from the original integer representation.

Test Cases

solution = Solution()

assert solution.nextGreaterElement(12) == 21  # Basic increasing digits
assert solution.nextGreaterElement(21) == -1  # Already maximum permutation
assert solution.nextGreaterElement(123) == 132  # Simple next permutation
assert solution.nextGreaterElement(321) == -1  # Fully descending digits
assert solution.nextGreaterElement(115) == 151  # Repeated digits
assert solution.nextGreaterElement(230241) == 230412  # Complex pivot position
assert solution.nextGreaterElement(12443322) == 13222344  # Larger repeated digits
assert solution.nextGreaterElement(1) == -1  # Single digit
assert solution.nextGreaterElement(1999999999) == -1  # Overflow after permutation
assert solution.nextGreaterElement(2147483476) == 2147483647  # Max valid 32-bit result
assert solution.nextGreaterElement(2147483647) == -1  # Overflow boundary
assert solution.nextGreaterElement(534976) == 536479  # Standard next permutation case

Test	Why
`12`	Smallest nontrivial increasing case
`21`	No larger permutation exists
`123`	Standard ascending input
`321`	Fully descending input
`115`	Repeated digits
`230241`	Pivot occurs in middle
`12443322`	Complex repeated suffix
`1`	Single-digit edge case
`1999999999`	Valid permutation exceeds 32-bit limit
`2147483476`	Largest valid answer within limit
`2147483647`	Boundary overflow case
`534976`	Common next permutation example

Edge Cases

One important edge case occurs when the digits are already in descending order. For example, 54321 has no larger permutation because it is already the maximum possible arrangement of those digits. A naive implementation might still attempt swaps and accidentally produce an invalid result. The algorithm handles this by searching for a pivot index. If no pivot exists, it immediately returns -1.

Another tricky case involves repeated digits, such as 115. Duplicate values can easily cause incorrect swaps if the algorithm simply chooses any larger digit instead of the smallest larger digit. The implementation correctly scans from the right side and selects the first digit larger than the pivot, which guarantees the minimal increase necessary for the next permutation.

Overflow handling is also critical. Consider 1999999999. A larger permutation exists, but the resulting number exceeds the 32-bit signed integer limit. Without the overflow check, the algorithm would incorrectly return an invalid answer. The implementation explicitly compares the result against 2^31 - 1 and returns -1 if the value is too large.

A final edge case is single-digit input. Numbers like 7 cannot produce a larger arrangement because there is only one possible permutation. The pivot search naturally fails in this scenario, and the algorithm correctly returns -1.