Find next higher number using exact same digits

Problem

Given a number X find the number Y which is next higher number than X using the exact same digits as in X.

Example
For example: given 38276 return 38627

Solution

Method 1 - Brute force
The brute-force method is to generate the numbers with all digit permutations and consider all the higher numbers than the given number and return the minimum number from those higher numbers.

code -

int findNext(int n)
{
    int nextNum = INT_MAX;
    String nStr = Integer.toString(n);
     
    for(String perm : permutations(nStr)) {
        int pNum = Integer.valueOf(perm);
        if(pNum>n){
            nextNum = Math.min(pNum, nextNum);
        }          
    }
    if(nextNum == INT_MAX) {
        return -1;
    }
    else {
        return nextNum;
    }
}

Time complexity - O(polynomial)

Method 2 - Split the number and swapping the digits 

Consider the number X  =   989325321

1. Split the sequence of digits in two, such that the right sequence is as long as possible while remaining in decreasing order:
   

                              98932   5321

2. Take the last digit of the first sequence, and swap it with the smallest digit in the second that is bigger than it:
   

                              9893(2)   5(3)21
   

   
   After swapping 2 and 3
   

                              98933   5221
   

3. Sort the second sequence into increasing order:

                              98933   1225

   
   This is our number - the next higher number with same digits.
   

Time complexity - O(n), where n is number of digits


References

    Google Code Jam 2009 Round 1B