Problem Description

Given a positive 32-bit integer n, find the smallest integer that is strictly greater than n and contains exactly the same digits as n. If no such integer exists, return -1.

• Each digit must be used exactly as many times as in n (no digit can be repeated or omitted).
• If the result exceeds the 32-bit signed integer range, return -1.
• There is only one correct answer for each input.

Example:
Input: n = 12443322
Output: 13222344

Thought Process

At first glance, one might consider generating all permutations of the digits of n, sorting them, and picking the next greater one. However, this brute-force approach is highly inefficient due to the factorial growth in possibilities.

The problem is essentially about finding the "next lexicographical permutation" of the digits of n. This is a well-known problem that can be solved efficiently by manipulating the digits in place, similar to how you would find the next permutation in a sequence.

The main idea is to identify the rightmost place where you can make the number bigger by swapping digits, and then rearrange the remaining digits to make the smallest possible number that is still larger than the original.

Solution Approach

We use the "next permutation" algorithm, which works as follows:

1. Convert the number to a list of digits: This makes it easier to manipulate individual digits.
2. Find the first decreasing digit from the right: Traverse the list from right to left and find the first index i where digits[i] < digits[i+1]. This is the pivot point where we can make the number larger.
3. If no such digit is found: The digits are in descending order, so no larger permutation is possible. Return -1.
4. Find the smallest digit to the right of i that is larger than digits[i]: Swap these two digits.
5. Reverse the digits to the right of i: This ensures the smallest possible number is formed with the remaining digits.
6. Convert the list of digits back to an integer: If the result fits in a 32-bit signed integer, return it. Otherwise, return -1.

This approach is efficient and avoids unnecessary permutations.

Example Walkthrough

Let's walk through the example where n = 12443322:

1. Convert to digits: [1, 2, 4, 4, 3, 3, 2, 2]
2. Traverse from right: Find first decreasing digit.
   Compare: 2 < 2 (no), 3 < 2 (no), 3 < 3 (no), 4 < 3 (no), 4 < 4 (no), 2 < 4 (yes, at index 1)
3. Now, from the right, find the smallest digit greater than 2 (from index 2 onwards). That is 3 at index 5.
4. Swap digits at indices 1 and 5: [1, 3, 4, 4, 3, 2, 2, 2]
5. Reverse the digits right of index 1: [1, 3, 2, 2, 2, 3, 4, 4]
6. Join to form 13222344, which is the answer.

Time and Space Complexity

• Brute-force approach: Generating all permutations has time complexity O(n!) for n digits, which is infeasible for anything but very small numbers.
• Optimized approach: The next permutation algorithm runs in O(n) time and uses O(n) space for the digit array, where n is the number of digits in n. Each step (finding pivot, finding swap candidate, reversing) is linear in the number of digits.

Summary

By recognizing the problem as one of finding the next lexicographical permutation, we avoid brute-force permutation generation. The efficient "next permutation" algorithm finds the next greater number using the same digits in linear time by identifying a pivot, swapping, and reversing. This approach is both elegant and optimal for this class of problems.

Code Implementation

class Solution:
    def nextGreaterElement(self, n: int) -> int:
        digits = list(str(n))
        i = len(digits) - 2
        # Step 1: Find first decreasing digit from right
        while i >= 0 and digits[i] >= digits[i+1]:
            i -= 1
        if i == -1:
            return -1
        # Step 2: Find the smallest digit on right side > digits[i]
        j = len(digits) - 1
        while digits[j] <= digits[i]:
            j -= 1
        # Step 3: Swap
        digits[i], digits[j] = digits[j], digits[i]
        # Step 4: Reverse the right part
        digits[i+1:] = reversed(digits[i+1:])
        res = int(''.join(digits))
        return res if res <= 2**31 - 1 else -1
      

class Solution {
public:
    int nextGreaterElement(int n) {
        string digits = to_string(n);
        int i = digits.size() - 2;
        // Step 1: Find first decreasing digit from right
        while (i >= 0 && digits[i] >= digits[i+1]) {
            i--;
        }
        if (i == -1) return -1;
        // Step 2: Find the smallest digit on right side > digits[i]
        int j = digits.size() - 1;
        while (digits[j] <= digits[i]) {
            j--;
        }
        // Step 3: Swap
        swap(digits[i], digits[j]);
        // Step 4: Reverse the right part
        reverse(digits.begin() + i + 1, digits.end());
        long res = stol(digits);
        return (res <= INT_MAX) ? res : -1;
    }
};
      

class Solution {
    public int nextGreaterElement(int n) {
        char[] digits = Integer.toString(n).toCharArray();
        int i = digits.length - 2;
        // Step 1: Find first decreasing digit from right
        while (i >= 0 && digits[i] >= digits[i+1]) {
            i--;
        }
        if (i == -1) return -1;
        // Step 2: Find the smallest digit on right side > digits[i]
        int j = digits.length - 1;
        while (digits[j] <= digits[i]) {
            j--;
        }
        // Step 3: Swap
        char temp = digits[i];
        digits[i] = digits[j];
        digits[j] = temp;
        // Step 4: Reverse the right part
        int left = i + 1, right = digits.length - 1;
        while (left < right) {
            char t = digits[left];
            digits[left] = digits[right];
            digits[right] = t;
            left++;
            right--;
        }
        long res = Long.parseLong(new String(digits));
        return (res <= Integer.MAX_VALUE) ? (int)res : -1;
    }
}
      

var nextGreaterElement = function(n) {
    let digits = Array.from(String(n), Number);
    let i = digits.length - 2;
    // Step 1: Find first decreasing digit from right
    while (i >= 0 && digits[i] >= digits[i+1]) {
        i--;
    }
    if (i === -1) return -1;
    // Step 2: Find the smallest digit on right side > digits[i]
    let j = digits.length - 1;
    while (digits[j] <= digits[i]) {
        j--;
    }
    // Step 3: Swap
    [digits[i], digits[j]] = [digits[j], digits[i]];
    // Step 4: Reverse the right part
    let left = i + 1, right = digits.length - 1;
    while (left < right) {
        [digits[left], digits[right]] = [digits[right], digits[left]];
        left++;
        right--;
    }
    let res = parseInt(digits.join(''), 10);
    return res <= 0x7FFFFFFF ? res : -1;
};