Problem Description

Given a positive integer n, find the smallest integer that:

1. Contains exactly the same digits as n (using each digit the same number of times)
2. Is greater in value than n

If no such integer exists, return -1.

Additionally, the returned integer must fit within a 32-bit signed integer range (maximum value of 2^31 - 1). If a valid answer exists but exceeds this range, return -1.

For example:

• If n = 12, the next greater integer with the same digits is 21
• If n = 21, no greater integer can be formed with digits 2 and 1, so return -1
• If n = 123, the next greater integer is 132

The algorithm works by:

1. Converting the number to a list of digit characters for manipulation
2. Finding the rightmost digit that is smaller than its next digit (scanning from right to left) - this is the pivot point i
3. If no such digit exists (digits are in descending order), no greater number is possible
4. Finding the smallest digit to the right of position i that is still greater than cs[i] - this is position j
5. Swapping the digits at positions i and j
6. Reversing all digits after position i to get the smallest possible arrangement
7. Checking if the result fits in 32-bit integer range before returning

Intuition

To find the next greater number with the same digits, think about how numbers increase in value. When we count: 123, 124, 125... each increment changes the rightmost digits first. But we're restricted to using only the existing digits.

Consider the number 12543. To make it bigger while using the same digits, we need to find where we can make a "smart swap". Reading from right to left, we see: 3, 4, 5, 2, 1. The digits 5, 4, 3 are in descending order - we can't rearrange them to make the number bigger without changing digits to their left. But when we reach 2, we notice that 2 < 5, meaning we can swap 2 with a larger digit to its right.

The key insight is finding the rightmost position where a digit is smaller than some digit to its right. This is our "pivot point" - position i. This digit at position i needs to be increased to make the overall number larger.

But we can't just swap with any larger digit. We want the next greater number, so we need to:

1. Find the smallest digit to the right of i that's still larger than cs[i] - this gives us the minimal increase
2. After swapping, the digits to the right of position i should be arranged in ascending order to create the smallest possible number with those remaining digits

For example, with 12543:

• The pivot is at position 1 (digit 2)
• The smallest digit greater than 2 to its right is 3
• Swap: 13542
• Sort remaining digits in ascending order: 13245

This approach guarantees we get the very next number in the sequence of all permutations of the given digits.

Learn more about Math and Two Pointers patterns.

Solution Approach

The implementation follows these steps:

1. Convert to digit array: Convert the integer n to a list of character digits cs for easier manipulation. This allows us to work with individual digits and perform swaps.

2. Find the pivot point: Starting from the second-to-last position (i = n - 2), scan leftward to find the first digit that is smaller than its right neighbor:

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

   If i < 0, all digits are in non-increasing order (like 4321), meaning no greater permutation exists, so return -1.

3. Find the swap target: From the rightmost position (j = n - 1), scan leftward to find the smallest digit that is still greater than cs[i]:

   while cs[i] >= cs[j]:
       j -= 1

   This ensures we get the minimal increase when we swap.

4. Perform the swap: Exchange the digits at positions i and j:

   cs[i], cs[j] = cs[j], cs[i]

5. Minimize the remaining digits: Reverse all digits after position i to arrange them in ascending order:

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

   This works because after finding the pivot, all digits to its right were in descending order. After the swap, they remain in descending order, so reversing gives us ascending order - the smallest possible arrangement.

6. Build and validate the result: Convert the digit array back to an integer and check if it fits within the 32-bit signed integer range (2^31 - 1):

   ans = int(''.join(cs))
   return -1 if ans > 2**31 - 1 else ans

The time complexity is O(n) where n is the number of digits, and space complexity is O(n) for storing the digit array.

Example Walkthrough

Let's walk through the algorithm with n = 12543:

Step 1: Convert to digit array

• cs = ['1', '2', '5', '4', '3']

Step 2: Find the pivot point (i)

• Start from index 3 (second-to-last): cs[3] = '4', cs[4] = '3'
• Is '4' >= '3'? Yes, so move left (i = 2)
• Check index 2: cs[2] = '5', cs[3] = '4'
• Is '5' >= '4'? Yes, so move left (i = 1)
• Check index 1: cs[1] = '2', cs[2] = '5'
• Is '2' >= '5'? No! We found our pivot at i = 1

Step 3: Find the swap target (j)

• Start from the rightmost index 4: cs[4] = '3'
• Is cs[1] = '2' >= '3'? No, so j = 4
• We found the smallest digit greater than '2' to the right of position 1

Step 4: Perform the swap

• Swap cs[1] and cs[4]: ['1', '3', '5', '4', '2']

Step 5: Minimize remaining digits

• Reverse digits after position 1: cs[2:] = ['5', '4', '2']
• After reversal: ['2', '4', '5']
• Final array: ['1', '3', '2', '4', '5']

Step 6: Build and validate result

• Convert to integer: 13245
• Check if 13245 <= 2^31 - 1? Yes
• Return 13245

The answer 13245 is indeed the next greater number using the same digits as 12543.

Solution Implementation

Time and Space Complexity

Time Complexity: O(d) where d is the number of digits in the input number

• Converting integer to string: O(d)
• First while loop to find the rightmost digit that's smaller than its next digit: O(d) in worst case
• Second while loop to find the smallest digit greater than cs[i] from the right: O(d) in worst case
• Swapping two elements: O(1)
• Reversing the suffix cs[i+1:]: O(d) in worst case
• Converting string back to integer: O(d)
• Overall: O(d) + O(d) + O(d) + O(1) + O(d) + O(d) = O(d)

Space Complexity: O(d) where d is the number of digits in the input number

• The list cs stores all digits of the input number: O(d)
• The reversed suffix operation creates a new list temporarily: O(d)
• String join operation creates a new string: O(d)
• Overall auxiliary space: O(d)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow Not Handled Early

A common mistake is not checking for integer overflow before converting the final result. Some implementations might crash or produce incorrect results when the rearranged number exceeds the 32-bit limit.

Pitfall Example:

# Incorrect: May cause issues with very large numbers
result = int(''.join(digits))
return result  # Forgot to check overflow!

Solution: Always validate against 2^31 - 1 before returning:

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

2. Incorrect Pivot Finding Logic

Many implementations incorrectly search for the pivot from left to right instead of right to left, which can miss the correct swap position.

Pitfall Example:

# Incorrect: Starting from the beginning
pivot_index = 0
while pivot_index < length - 1 and digits[pivot_index] >= digits[pivot_index + 1]:
    pivot_index += 1

Solution: Always scan from right to left to find the rightmost valid pivot:

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

3. Not Finding the Optimal Swap Target

After finding the pivot, some solutions swap with any larger digit instead of the smallest digit that's still larger than the pivot, resulting in a number that's not the immediate next greater.

Pitfall Example:

# Incorrect: Just finding any larger digit
for j in range(pivot_index + 1, length):
    if digits[j] > digits[pivot_index]:
        swap_index = j
        break  # This might not be the optimal choice

Solution: Scan from right to left to find the smallest digit greater than the pivot:

swap_index = length - 1
while digits[pivot_index] >= digits[swap_index]:
    swap_index -= 1

4. Forgetting to Reverse After Swap

A critical mistake is forgetting to reverse the digits after the pivot position, which results in a larger number than necessary.

Pitfall Example:

# Incorrect: Just swapping without reversing
digits[pivot_index], digits[swap_index] = digits[swap_index], digits[pivot_index]
# Missing the reversal step!
result = int(''.join(digits))

Solution: Always reverse the suffix after swapping to minimize the result:

digits[pivot_index], digits[swap_index] = digits[swap_index], digits[pivot_index]
digits[pivot_index + 1:] = digits[pivot_index + 1:][::-1]

5. Edge Case: Single Digit Numbers

Not handling single-digit numbers properly can cause index out of bounds errors.

Pitfall Example:

# May fail for n = 5 (single digit)
pivot_index = length - 2  # This becomes -1 for single digits

Solution: The current implementation handles this correctly as the while loop condition pivot_index >= 0 prevents issues, and single digits will correctly return -1 since no greater permutation exists.