##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/556.html

# 556. Next Greater Element III (Medium)

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


Related Topics:
String

Similar Questions:

## Solution 1.

• class Solution {
public int nextGreaterElement(int n) {
char[] array = String.valueOf(n).toCharArray();
boolean next = nextPermutation(array);
if (!next)
return -1;
String nextGreaterElementStr = new String(array);
long nextGreaterElementLong = Long.parseLong(nextGreaterElementStr);
if (nextGreaterElementLong > Integer.MAX_VALUE)
return -1;
else {
int nextGreaterElement = (int) nextGreaterElementLong;
return nextGreaterElement;
}
}

public boolean nextPermutation(char[] array) {
int length = array.length;
int index = -1;
char curChar = Character.MAX_VALUE;
for (int i = length - 1; i > 0; i--) {
int difference = array[i] - array[i - 1];
if (difference > 0) {
index = i - 1;
curChar = array[i - 1];
break;
}
}
if (index < 0) {
Arrays.sort(array);
return false;
}
int nextIndex = -1;
char nextChar = Character.MAX_VALUE;
for (int i = index + 1; i < length; i++) {
if (array[i] > curChar && array[i] < nextChar) {
nextIndex = i;
nextChar = array[i];
}
}
array[index] = nextChar;
array[nextIndex] = curChar;
Arrays.sort(array, index + 1, length);
return true;
}
}

############

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);
}
}
}

• // OJ: https://leetcode.com/problems/next-greater-element-iii/
// Time: O(1)
// Space: O(1)
class Solution {
public:
int nextGreaterElement(int n) {
auto s = to_string(n);
for (int i = s.size() - 2; i >= 0; --i) {
if (s[i] >= s[i + 1]) continue;
int j = lower_bound(s.begin() + i + 1, s.end(), s[i], greater<int>()) - s.begin() - 1;
swap(s[i], s[j]);
sort(s.begin() + i + 1, s.end());
long n = stol(s);
return n > INT_MAX ? -1 : n;
}
return -1;
}
};

• 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

############

class Solution(object):
def nextGreaterElement(self, n):
"""
:type n: int
:rtype: int
"""
num = n
n = list(str(n))
pos = leftMost = len(n) - 1
for i in reversed(range(0, len(n) - 1)):
if n[i] < n[i + 1]:
leftMost = i
break
for i in reversed(range(leftMost + 1, len(n))):
if n[i] > n[leftMost]:
pos = i
break

n[leftMost], n[pos] = n[pos], n[leftMost]
n[leftMost + 1:] = sorted(n[leftMost + 1:])
n = int("".join(n))
print
n
if n <= num or n > 0x7fffffff:
return -1
return n


• 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
}