Next Greater Element III

Problem

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

Example 1:

Input: 12
Output: 21

Example 1:

Input: 21
Output: -1

Solution

public class Solution {
    public int nextGreaterElement(int n) {
        char[] nums = (n + "").toCharArray();
        int index = -1, len = nums.length;
        for (int i = 0; i < len - 1; i++) {
            if (nums[i] < nums[i + 1]) index = i;
        }
        if (index == -1) return -1;
        int smallestIndex = index + 1;
        for (int i = index + 2; i < len; i++) {
            if (nums[i] > nums[index] && nums[i] < nums[smallestIndex]) smallestIndex = i;
        }
        //Swap nums[index] and nums[smallestIndex]
        char temp = nums[index];
        nums[index] = nums[smallestIndex];
        nums[smallestIndex] = temp;
        //Sort the right side of swapping 
        Arrays.sort(nums, index + 1, len);
        long res = Long.parseLong(String.valueOf(nums)); //Has to be int to check whether it explodes 
        return res > Integer.MAX_VALUE ? -1 : (int)res;
    }
}

Analysis

We know that if each digit from given number is decreasing, then there is no valid result
Otherwise, we get the index where the digit begins increasing
Then we find the smallest digit on the right which is still greater than nums[index]
We swap this digit and nums[index]
After that, we sort the right side of swapping to get the exactly next greater element
At the end, we have to check whether the new number is exploded, therefore we use long
Notice that we get the String value by calling String.valueOf(nums) on char[] nums