Welcome to Subscribe On Youtube

556. Next Greater Element III

Description

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 <= 231 - 1

Solutions

• Java
• C++
• Python
• Go

• class Solution {
      public int nextGreaterElement(int n) {
          char[] cs = String.valueOf(n).toCharArray();
          n = cs.length;
          int i = n - 2, j = n - 1;
          for (; i >= 0 && cs[i] >= cs[i + 1]; --i)
              ;
          if (i < 0) {
              return -1;
          }
          for (; cs[i] >= cs[j]; --j)
              ;
          swap(cs, i, j);
          reverse(cs, i + 1, n - 1);
          long ans = Long.parseLong(String.valueOf(cs));
          return ans > Integer.MAX_VALUE ? -1 : (int) ans;
      }
  
      private void swap(char[] cs, int i, int j) {
          char t = cs[i];
          cs[i] = cs[j];
          cs[j] = t;
      }
  
      private void reverse(char[] cs, int i, int j) {
          for (; i < j; ++i, --j) {
              swap(cs, i, j);
          }
      }
  }
  

• class Solution {
  public:
      int nextGreaterElement(int n) {
          string s = to_string(n);
          n = s.size();
          int i = n - 2, j = n - 1;
          for (; i >= 0 && s[i] >= s[i + 1]; --i)
              ;
          if (i < 0) return -1;
          for (; s[i] >= s[j]; --j)
              ;
          swap(s[i], s[j]);
          reverse(s.begin() + i + 1, s.end());
          long ans = stol(s);
          return ans > INT_MAX ? -1 : ans;
      }
  };
  

• class Solution:
      def nextGreaterElement(self, n: int) -> int:
          cs = list(str(n))
          n = len(cs)
          i, j = n - 2, n - 1
          while i >= 0 and cs[i] >= cs[i + 1]:
              i -= 1
          if i < 0:
              return -1
          while cs[i] >= cs[j]:
              j -= 1
          cs[i], cs[j] = cs[j], cs[i]
          cs[i + 1 :] = cs[i + 1 :][::-1]
          ans = int(''.join(cs))
          return -1 if ans > 2**31 - 1 else ans
  
  

• func nextGreaterElement(n int) int {
  	s := []byte(strconv.Itoa(n))
  	n = len(s)
  	i, j := n-2, n-1
  	for ; i >= 0 && s[i] >= s[i+1]; i-- {
  	}
  	if i < 0 {
  		return -1
  	}
  	for ; j >= 0 && s[i] >= s[j]; j-- {
  	}
  	s[i], s[j] = s[j], s[i]
  	for i, j = i+1, n-1; i < j; i, j = i+1, j-1 {
  		s[i], s[j] = s[j], s[i]
  	}
  	ans, _ := strconv.Atoi(string(s))
  	if ans > math.MaxInt32 {
  		return -1
  	}
  	return ans
  }
  

All Problems

All Solutions