556. Next Greater Element III

Problem Description

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 that 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.

Example 1:

Input: n = 12
Output: 21

Example 2:

Input: n = 21
Output: -1

Constraints:

• 1 <= n <= 2³¹ - 1

Python Solution

class Solution:
    def nextGreaterElement(self, n: int) -> int:
        # Convert to list of digits
        digits = list(str(n))
        length = len(digits)
        
        # Find first pair from right where left < right
        i = length - 2
        while i >= 0 and digits[i] >= digits[i + 1]:
            i -= 1
            
        # If no such pair found, return -1
        if i < 0:
            return -1
            
        # Find smallest digit on right side of i that is greater than digits[i]
        j = length - 1
        while digits[j] <= digits[i]:
            j -= 1
            
        # Swap the digits
        digits[i], digits[j] = digits[j], digits[i]
        
        # Reverse the subarray to the right of i
        left = i + 1
        right = length - 1
        while left < right:
            digits[left], digits[right] = digits[right], digits[left]
            left += 1
            right -= 1
            
        # Convert back to integer and check constraints
        result = int(''.join(digits))
        return result if result <= 2**31 - 1 else -1

Java Solution

class Solution {
    public int nextGreaterElement(int n) {
        char[] digits = String.valueOf(n).toCharArray();
        int length = digits.length;
        
        // Find first pair from right where left < right
        int i = length - 2;
        while (i >= 0 && digits[i] >= digits[i + 1]) {
            i--;
        }
        
        // If no such pair found, return -1
        if (i < 0) {
            return -1;
        }
        
        // Find smallest digit on right side of i that is greater than digits[i]
        int j = length - 1;
        while (digits[j] <= digits[i]) {
            j--;
        }
        
        // Swap the digits
        char temp = digits[i];
        digits[i] = digits[j];
        digits[j] = temp;
        
        // Reverse the subarray to the right of i
        reverse(digits, i + 1, length - 1);
        
        // Convert back to integer and check constraints
        try {
            return Integer.parseInt(new String(digits));
        } catch (Exception e) {
            return -1;
        }
    }
    
    private void reverse(char[] arr, int start, int end) {
        while (start < end) {
            char temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
    }
}

C++ Solution

class Solution {
public:
    int nextGreaterElement(int n) {
        string digits = to_string(n);
        int length = digits.length();
        
        // Find first pair from right where left < right
        int i = length - 2;
        while (i >= 0 && digits[i] >= digits[i + 1]) {
            i--;
        }
        
        // If no such pair found, return -1
        if (i < 0) {
            return -1;
        }
        
        // Find smallest digit on right side of i that is greater than digits[i]
        int j = length - 1;
        while (digits[j] <= digits[i]) {
            j--;
        }
        
        // Swap the digits
        swap(digits[i], digits[j]);
        
        // Reverse the subarray to the right of i
        reverse(digits.begin() + i + 1, digits.end());
        
        // Convert back to integer and check constraints
        long result = stol(digits);
        return result > INT_MAX ? -1 : result;
    }
};

JavaScript Solution

/**
 * @param {number} n
 * @return {number}
 */
var nextGreaterElement = function(n) {
    const digits = String(n).split('');
    const length = digits.length;
    
    // Find first pair from right where left < right
    let i = length - 2;
    while (i >= 0 && digits[i] >= digits[i + 1]) {
        i--;
    }
    
    // If no such pair found, return -1
    if (i < 0) {
        return -1;
    }
    
    // Find smallest digit on right side of i that is greater than digits[i]
    let j = length - 1;
    while (digits[j] <= digits[i]) {
        j--;
    }
    
    // Swap the digits
    [digits[i], digits[j]] = [digits[j], digits[i]];
    
    // Reverse the subarray to the right of i
    const left = i + 1;
    const right = length - 1;
    while (left < right) {
        [digits[left], digits[right]] = [digits[right], digits[left]];
        left++;
        right--;
    }
    
    // Convert back to integer and check constraints
    const result = parseInt(digits.join(''));
    return result <= 2**31 - 1 ? result : -1;
};

C# Solution

public class Solution {
    public int NextGreaterElement(int n) {
        char[] digits = n.ToString().ToCharArray();
        int length = digits.Length;
        
        // Find first pair from right where left < right
        int i = length - 2;
        while (i >= 0 && digits[i] >= digits[i + 1]) {
            i--;
        }
        
        // If no such pair found, return -1
        if (i < 0) {
            return -1;
        }
        
        // Find smallest digit on right side of i that is greater than digits[i]
        int j = length - 1;
        while (digits[j] <= digits[i]) {
            j--;
        }
        
        // Swap the digits
        char temp = digits[i];
        digits[i] = digits[j];
        digits[j] = temp;
        
        // Reverse the subarray to the right of i
        Array.Reverse(digits, i + 1, length - i - 1);
        
        // Convert back to integer and check constraints
        try {
            return int.Parse(new string(digits));
        } catch {
            return -1;
        }
    }
}