Next higher number with same digits

Finding a next higher number with the same digits is one of the challenging problem to identify a solution with respect to  time space complexity . Any solution which provides in least time and least space would be suitable for the best fit of the solution.

There are multiple solution to this problem :

Solution 1 :

Simplest solution is to find the all permutations of the digits and sort the numbers and then compare with the given number to find next higher number .

Time complexity O(n!) for the solution and not at all suitable for practical cases.It would be worst solution to this problem.

Solution 2 :

Another solution with the O(n) time complexity and O(1) space would be as follow :

       

 public static void swap(char[]  charArray, int j , int k){

  char temp = charArray[j];

  charArray[j] = charArray[k];

  charArray[k] = temp;

 }

 public static void nextHigherInteger(Integer input){

  if(input == null || input<=0 ){

   return;

  }

  String s = input.toString();

  char[] charArr = s.toCharArray();

  int charLength = charArr.length;

  int breakPoint = 0;

  for (int i = charLength-1; i > 0; i--) {

   char last = charArr[i];

   char secondLast = charArr[i-1];

   if(secondLast < last ){

    breakPoint = i-1;

    break;

   } 

  }

  if(breakPoint == 0){

   System.out.println("This is the highest number");

   return;

  }

  String first = s.substring(0, breakPoint+1);

  String second = s.substring(breakPoint+1, charLength);

  char[] secondCharArra = second.toCharArray();

  Arrays.sort(secondCharArra);//sorting to the second substring

  StringBuffer sb2 =new StringBuffer();

  sb2.append(first);

  for (char c : secondCharArra) {

   sb2.append(c);

  }          

  char[] charArray = sb2.toString().toCharArray();

  int j = breakPoint;

  int k = ++breakPoint;

  while(true){

   if(charArray[j] < charArray[k]){

    swap(charArray, j, k);

    break;

   } else {

    k++;

   }

  }

  StringBuffer sb3 = new StringBuffer();

  for (char c : charArray) {

   sb3.append(c);

  }  

  System.out.println(sb3.toString());

 }

 public static void main(String[] args) {

  //nextHigherInteger(34722641);//34724126

  //nextHigherInteger(1234675);//1234756

  //nextHigherInteger(23514);//23541

  nextHigherInteger(38276);//38627

 }                                                                                          

Above mention solution is simple in terms of understanding the logic ,it uses following main points :

1 .  Traverse from tail till the higher sequence is break means from left to right traverse and check that left digit must be higher than right digit , at any point of its less , its a break/pivot point.

2. Divide two substring one for left to the break/pivot point and one for the right of the pivot point.

3. Sort the second string in the ascending order  and compare the first char to rightmost character of first string(x) , if its higher then swap them . If its is less then go for next char of the second string and compare them if its correct then swap it , similarly till the next higher number to  x is found. 

4. Merge first and second string  and your required number would this string.

Time complexity  : O(n) and space O(1) 
Sorting Method : Merge sort of Default Java