Problem Statement

• 556. Next Greater Element III

Given a positive integer n, find the smallest integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive integer exists, return -1.

Note: The returned integer should fit in 32-bit integer. If there is a valid answer but it does not fit in 32-bit integer, return -1.

Examples:

• n = 12 → 21 (next greater permutation of digits)
• n = 21 → -1 (no greater permutation exists)
• n = 1234 → 1243
• n = 4321 → -1 (digits in descending order)

Constraints:

• 1 <= n <= 2^31 - 1

Algorithm Walkthrough

This problem is essentially finding the next permutation of digits in a number. We can reuse the Next Permutation algorithm with some modifications for integer handling and overflow checking.

Step-by-Step Process:

Step 1: Convert to Character Array

• Convert the integer to a character array to work with individual digits
• This allows us to apply the next permutation algorithm

Step 2: Find the Pivot

• Scan from right to left to find the largest index i such that digits[i] < digits[i + 1]
• This is the rightmost position where we can increase the value
• If no such index exists, the number is in descending order (largest permutation)

Step 3: Find the Swap Partner (if pivot exists)

• Find the largest index j such that digits[i] < digits[j]
• This gives us the smallest digit greater than digits[i] to swap with

Step 4: Swap

• Swap digits[i] and digits[j]

Step 5: Reverse the Suffix

• Reverse the subarray from digits[i + 1] to the end
• This ensures we get the smallest possible arrangement after the pivot

Step 6: Convert Back and Check Overflow

• Convert the character array back to integer
• Check if the result fits in 32-bit integer range
• Return -1 if overflow occurs

Example Walkthrough: n = 1234

1. Convert to array: ['1', '2', '3', '4']
2. Find pivot: digits[2] = '3' < digits[3] = '4', so i = 2
3. Find swap partner: digits[3] = '4' > digits[2] = '3', so j = 3
4. Swap: ['1', '2', '3', '4'] → ['1', '2', '4', '3']
5. Reverse suffix: Reverse from index 3: ['1', '2', '4', '3'] (nothing to reverse)
6. Convert back: 1243
7. Result: 1243

Example Walkthrough: n = 4321

1. Convert to array: ['4', '3', '2', '1']
2. Find pivot: No i where digits[i] < digits[i+1] (descending order)
3. No next permutation exists
4. Result: -1

Example Walkthrough: n = 2147483476

1. Convert to array: ['2', '1', '4', '7', '4', '8', '3', '4', '7', '6']
2. Apply next permutation algorithm: Would result in a number > 2^31 - 1
3. Overflow check fails
4. Result: -1

Complexity Analysis

Time Complexity: O(d)

• Where d is the number of digits in the integer
• Converting to string/array: O(d)
• Finding pivot: O(d) in worst case
• Finding swap partner: O(d) in worst case
• Reversing suffix: O(d) in worst case
• Converting back to integer: O(d)
• Overall: O(d)

Space Complexity: O(d)

• Character array to store digits: O(d)
• All other operations use constant space
• Note: We need extra space unlike the array version because we can't modify the integer in-place

Full Solution (Java)

public class Solution {
    public int nextGreaterElement(int n) {
        // Convert number to character array
        char[] digits = String.valueOf(n).toCharArray();

        // Step 1: Find the largest index i such that digits[i] < digits[i + 1]
        int i = digits.length - 2;
        while (i >= 0 && digits[i] >= digits[i + 1]) {
            i--;
        }

        // If no such index exists, no next greater element is possible
        if (i < 0) {
            return -1;
        }

        // Step 2: Find the largest index j such that digits[i] < digits[j]
        int j = digits.length - 1;
        while (digits[j] <= digits[i]) {
            j--;
        }

        // Step 3: Swap digits[i] and digits[j]
        swap(digits, i, j);

        // Step 4: Reverse the suffix starting at digits[i + 1]
        reverse(digits, i + 1);

        // Step 5: Convert back to integer and check for overflow
        try {
            long result = Long.parseLong(String.valueOf(digits));
            return (result > Integer.MAX_VALUE) ? -1 : (int) result;
        } catch (NumberFormatException e) {
            return -1;
        }
    }

    private void swap(char[] digits, int i, int j) {
        char temp = digits[i];
        digits[i] = digits[j];
        digits[j] = temp;
    }

    private void reverse(char[] digits, int start) {
        int end = digits.length - 1;
        while (start < end) {
            swap(digits, start, end);
            start++;
            end--;
        }
    }
}

Alternative Solution

// Alternative solution with manual overflow checking
class SolutionOptimized {
    public int nextGreaterElement(int n) {
        char[] digits = String.valueOf(n).toCharArray();

        // Find pivot
        int i = digits.length - 2;
        while (i >= 0 && digits[i] >= digits[i + 1]) {
            i--;
        }

        if (i < 0) return -1;

        // Find swap partner
        int j = digits.length - 1;
        while (digits[j] <= digits[i]) {
            j--;
        }

        // Swap
        swap(digits, i, j);

        // Reverse suffix
        reverse(digits, i + 1);

        // Manual conversion with overflow check
        long result = 0;
        for (char digit : digits) {
            result = result * 10 + (digit - '0');
            if (result > Integer.MAX_VALUE) {
                return -1;
            }
        }

        return (int) result;
    }

    private void swap(char[] digits, int i, int j) {
        char temp = digits[i];
        digits[i] = digits[j];
        digits[j] = temp;
    }

    private void reverse(char[] digits, int start) {
        int end = digits.length - 1;
        while (start < end) {
            swap(digits, start, end);
            start++;
            end--;
        }
    }
}

Key Points:

• String conversion: We convert the integer to a character array to apply the next permutation algorithm
• Overflow handling: Critical to check if the result exceeds Integer.MAX_VALUE (2^31 - 1)
• Edge cases: Handle numbers in descending order (no next greater element)
• Reusable logic: The core algorithm is identical to Next Permutation, adapted for integers
• Two approaches: Main solution uses Long.parseLong() for simplicity, optimized version does manual conversion with early overflow detection