Next Greater Element III

LeetCode Q 556 - Next Greater Element III

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 2: Input: 21 ; Output: -1

Solution

• Transfer the number into a string
• Traverse from the end of the string and find a valley point in number
• Traverse from the end of the string, find the smallest digit that is larger than the valley point and swap them
• From the next point of the vally position, sort the right digits

Code

public int nextGreaterElement(int n) {
  char[] chs = (n + "").toCharArray();

  int i;
  for (i = chs.length - 2; i >= 0; i--) {
    if (chs[i] < chs[i + 1])  break;
  }

  if (i == -1) return -1; // digits are in descending order, e.g. 4321

  // find the smallest number larger than chs[i];
  int min = i + 1, j = i + 2;
  while (j < chs.length) {
    if (chs[j] > chs[i] && chs[j] <= chs[min])
        min = j;
    j++;
  }

  // swap
  char temp = chs[i];
  chs[i] = chs[min];
  chs[min] = temp;

  // sort
  Arrays.sort(chs, i + 1, chs.length);
    
  long val = Long.parseLong(new String(chs));
  return (val <= Integer.MAX_VALUE) ? (int) val : -1;
}