Next Smaller Number With the Same Digits in Java

The challenge

Write a function that takes a positive integer and returns the next smaller positive integer containing the same digits.

For example:

nextSmaller(21) == 12
nextSmaller(531) == 513
nextSmaller(2071) == 2017

Return -1 (for Haskell: return Nothing, for Rust: return None), when there is no smaller number that contains the same digits. Also return -1 when the next smaller number with the same digits would require the leading digit to be zero.

nextSmaller(9) == -1
nextSmaller(111) == -1
nextSmaller(135) == -1
nextSmaller(1027) == -1 // 0721 is out since we don't write numbers with leading zeros

• some tests will include very large numbers.
• test data only employs positive integers.

The solution in Java

Option 1:

import java.util.Arrays;
import java.util.Collections;
import java.util.stream.Stream;

public class Solution {
  public static long nextSmaller(long n) {
        Integer[] val = Long.toString(n).chars().map(c -> c - '0').boxed().toArray(Integer[]::new);
        int len = val.length;
        for (int i = len - 1; i > 0; i--) {
            if (val[i - 1] > val[i]) {
                int maxIdx = i;
                for (int j = i + 1; j < len; j++) {
                    if (val[i - 1] > val[j] && val[j] > val[maxIdx]) maxIdx = j;
                }
                val[i - 1] = val[i - 1] + val[maxIdx];
                val[i - 1] = val[i - 1] - (val[maxIdx] = val[i - 1] - val[maxIdx]);

                Arrays.sort(val, i, len, Collections.reverseOrder());
                return val[0] == 0 ? - 1L : Long.valueOf(String.join("", Stream.of(val).map(String::valueOf).toArray(String[]::new)));
            }
        }
        return -1L;
    }
}

Option 2:

public class Solution {
  public static long nextSmaller(long n) {
    final char[] cs = Long.toString(n).toCharArray();
    
    for (int l = cs.length, p = l-1, i; 0 < (i = p); p--) {
      while (i < l && cs[i] < cs[p-1])
        i++;
      
      if (p < i)
        return (p-1 == 0 && cs[i-1] == '0') ? -1 :
          Long.parseLong(new StringBuilder(l)
            .append(cs, p, i-1 - p).append(cs[p-1])
            .append(cs, i, l - i).append(cs[i-1])
            .reverse().insert(0, cs, 0, p-1).toString());
    }
    
    return -1;
  }
}

Option 3:

public class Solution {
  public static long nextSmaller(long n) {
    final char[] chars = Long.toString(n).toCharArray();
    
    for (int i = chars.length; 0 < i; i--) {
      char digit = chars[i-1];
      
      for (int j = i; j < chars.length; j++) {
        if (chars[j] < digit) {
          chars[i-1] = chars[j];
          chars[j] = digit;
          return (chars[0] == '0') ? -1 : Long.parseLong(new String(chars));
        }
      }
      
      System.arraycopy(chars, i, chars, i-1, chars.length - i);
      chars[chars.length-1] = digit;
    }
    
    return -1;
  }
}

Test cases to validate our solution

import org.junit.Test;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;

public class SolutionTests {
    @Test
    public void basicTests() {
         assertEquals(12, Solution.nextSmaller(21));
         assertEquals(790, Solution.nextSmaller(907));
         assertEquals(513, Solution.nextSmaller(531));
         assertEquals(-1, Solution.nextSmaller(1027));
         assertEquals(414, Solution.nextSmaller(441));
         assertEquals(123456789, Solution.nextSmaller(123456798));
    }      
}