Previous Smaller Element (Mutation)

Question

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

Example 1:

Input: 12
Output: -1


Example 2:

Input: 21
Output: 12

Solution

public int PreviousSmallerElement(int n) {
    char[] cArr = String.valueOf(n).toCharArray();

    //find nums[i]>nums[i+1] ,e.g. (3) 1 2 3 4 5
    int i = cArr.length-2;
    while(i>=0 && cArr[i]<=cArr[i+1]) i--;
    if(i==-1) return -1; // cannnot construct pre smaller 

    // method 1: sort cArr[i:] 
    // Arrays.sort(cArr,i,cArr.length);
    // reverse(cArr,i,cArr.length-1);


    // method 2: in place swap
    int j = cArr.length-1;
    while(j>i) {
        if(cArr[i]>cArr[j]) {
            swap(cArr,i,j);
            break;
        }
        j--;
    }
    reverse(cArr,i+1,cArr.length-1);


    return Integer.valueOf(new String(cArr));
}