556. Next Greater Element III.md

556. Next Greater Element III

---

leetcode Daily Challenge on December 23th, 2020.

---

Difficulty : Medium

Related Topics : String

---

Given a positive integer n, find the smallest integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive integer exists, return -1.

Note that the returned integer should fit in 32-bit integer, if there is a valid answer but it does not fit in 32-bit integer, return -1.

Example 1:

Input: n = 12
Output: 21

Example 2:

Input: n = 21
Output: -1

Constraints:

• 1 <= n <= 2^31 - 1

---

Solution

• mine
  • Java
    • Runtime: 0 ms, faster than 100.00%,Memory Usage: 36.4 MB, less than 10.00% of Java online submissions

      //O(N)time O(N)space
      //N is String.valueOf(n)'s length
      public int nextGreaterElement(int n) {
          //2^32 < 10^10
          int[] t = new int[10];
          int l = t.length;
          int temp = n;
          //chang n as array
          while (l > 0 && temp > 0) {
              l--;
              t[l] = temp % 10;
              temp /= 10;
          }
          for (int i = t.length - 1; i > l; i--) {
              if (t[i] > t[i - 1]) {
                  //find the index which is bigger than front one
                  int tempIndex = i;
                  //find the min one who is bigger than t[i-1]
                  for (int j = i; j < t.length; j++) {
                      if (t[j] > t[i - 1] && t[j] < t[tempIndex]) {
                          tempIndex = j;
                      }
                  }
                  //change t[i -1] t[tempIndex]
                  temp = t[i - 1];
                  t[i - 1] = t[tempIndex];
                  t[tempIndex] = temp;
                  //get the element after i - 1
                  int[] arr = new int[t.length - i];
                  System.arraycopy(t, i, arr, 0, t.length - i);
                  //sort
                  Arrays.sort(arr);
                  //copy arr to t[i] - t[len-1]
                  System.arraycopy(arr, 0, t, i, arr.length);
                  break;
              }
          }
          //get the new number
          int res = 0;
          for (int i : t) {
              res = res * 10 + i;
          }
          //if the new one is bigger the n return it  or return -1
          return res <= n ? -1 : res;
      }
      

---

• the most votes

• Runtime: 4 ms, faster than 41.54%, Memory Usage: 36.3 MB, less than 10.00% of Java online submissions

  public int nextGreaterElement(int n) {
      char[] number = (n + "").toCharArray();
  
      int i, j;
      // I) Start from the right most digit and 
      // find the first digit that is
      // smaller than the digit next to it.
      for (i = number.length-1; i > 0; i--)
          if (number[i-1] < number[i])
             break;
  
      // If no such digit is found, its the edge case 1.
      if (i == 0)
          return -1;
  
       // II) Find the smallest digit on right side of (i-1)'th 
       // digit that is greater than number[i-1]
      int x = number[i-1], smallest = i;
      for (j = i+1; j < number.length; j++)
          if (number[j] > x && number[j] <= number[smallest])
              smallest = j;
  
      // III) Swap the above found smallest digit with 
      // number[i-1]
      char temp = number[i-1];
      number[i-1] = number[smallest];
      number[smallest] = temp;
  
      // IV) Sort the digits after (i-1) in ascending order
      Arrays.sort(number, i, number.length);
  
      long val = Long.parseLong(new String(number));
      return (val <= Integer.MAX_VALUE) ? (int) val : -1;
  }
  

---