Algorithm
Problem Name: 556. Next Greater Element III
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
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int nextGreaterElement(int n) {
string s = to_string(n);
stack < char>q;
stack<int>idx;
for (int i = s.size() - 1; i >= 0; --i) {
if (q.empty() || q.top() < = s[i]) {
q.push(s[i]);
idx.push(i);
} else {
int pos = -1;
while (!q.empty() && q.top() > s[i]) {
pos = idx.top();
q.pop();
idx.pop();
}
swap(s[i], s[pos]);
sort(s.begin() + i + 1, s.end());
long l = stol(s);
if (l > INT_MAX) return -1;
return l;
}
}
return -1;
}
};
class Solution {
public:
int nextGreaterElement(int n) {
string s = to_string(n);
next_permutation(s.begin(), s.end());
auto res = stol(s);
return (res > INT_MAX || res < = n) ? -1 : res;
return -1;
}
};
Input
Output
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int nextGreaterElement(int n) {
char[] digits = String.valueOf(n).toCharArray();
int idx = digits.length - 2;
while (idx >= 0) {
if (Character.getNumericValue(digits[idx]) < Character.getNumericValue(digits[idx + 1])) {
int secondIdx = digits.length - 1;
while (secondIdx >= idx && digits[secondIdx] <= digits[idx]) {
secondIdx--;
}
swap(digits, idx, secondIdx);
int start = idx + 1;
int end = digits.length - 1;
while (start < end) {
swap(digits, start++, end--);
}
try {
return Integer.parseInt(new String(digits));
} catch (Exception e) {
return -1;
}
}
idx--;
}
return -1;
}
private void swap(char[] digits, int idxOne, int idxTwo) {
char temp = digits[idxOne];
digits[idxOne] = digits[idxTwo];
digits[idxTwo] = temp;
}
}
Input
Output
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const nextGreaterElement = function(n) {
let i, j;
const arr = (n + "").split("").map(el => +el);
for (i = arr.length - 2; i >= 0; i--) {
if (arr[i] < arr[i + 1]) {
break;
}
}
if (i < 0) return -1;
j = arr.length - 1;
while (arr[j] < = arr[i]) {
j--;
}
swap(arr, i, j);
reverse(arr, i + 1, arr.length - 1);
const res = arr.reduce((ac, el) => ac + el, "");
return res > Math.pow(2, 31) - 1 ? -1 : +res
};
function swap(arr, i, j) {
arr[i] ^= arr[j];
arr[j] ^= arr[i];
arr[i] ^= arr[j];
}
function reverse(arr, start, end) {
let l = start;
let h = end;
while (l < h) {
swap(arr, l++, h--);
}
}
Input
Output
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def nextGreaterElement(self, n):
arr = [c for c in str(n)]
for l in range(len(arr) - 2, -1, -1):
r = len(arr) - 1
while l < r and arr[r] <= arr[l]:
r -= 1
if l != r:
arr[l], arr[r] = arr[r], arr[l]
arr[l + 1:] = sorted(arr[l + 1:])
num = int("".join(arr))
return num if -2 ** 31 <= num <= 2 ** 31 - 1 else -1
return -1
Input
Output