Next Greater Element III — Solution in Python, Java & C++
Next Greater Element III solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Next Greater Element III is a medium coding problem on strings, math and two pointers, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Strings, Math, Two Pointers
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a positive integer n, find the smallest integer that uses exactly the same digits and is greater than n.
If no such integer exists, or it does not fit in a signed 32-bit integer, return -1.
Example 1
Input: n = 12
Output: 21
Example 2
Input: n = 21
Output: -1
Example 3
Input: n = 230241
Output: 230412
Constraints
1 <= n <= 2147483647
Hints for Next Greater Element III
Hint 1
This is the "next permutation" algorithm applied to the digit string.
Hint 2
Scan from the right for the first digit smaller than its successor — that is the pivot.
Hint 3
Swap it with the smallest digit to its right that still exceeds it, then reverse everything after the pivot; finally check the 32-bit bound.
How to solve Next Greater Element III
Next permutation on the digit string: find the pivot from the right, swap it with the smallest larger digit after it, reverse the suffix, then check the 32-bit bound.
Approach
- Find the rightmost
iwithd[i] < d[i+1]; return -1 if none. - Find the rightmost
j > iwithd[j] > d[i]and swap. - Reverse
d[i+1:]and rebuild the number, returning -1 if it exceeds2³¹ - 1.
Why it works
The suffix after the pivot is the largest arrangement of its digits, so the next number must raise the pivot minimally and then minimise the suffix, which is what the swap-and-reverse does.
Complexity
- Time —
O(digits) - Space —
O(digits)
Pitfalls
- The overflow check must happen even though the input fits.
Reference solution
Python
def nextGreaterElement(n: int) -> int:
digits = [int(c) for c in str(n)]
i = len(digits) - 2
while i >= 0 and digits[i] >= digits[i + 1]:
i -= 1
if i < 0:
return -1
j = len(digits) - 1
while digits[j] <= digits[i]:
j -= 1
digits[i], digits[j] = digits[j], digits[i]
digits[i + 1:] = reversed(digits[i + 1:])
value = 0
for d in digits:
value = value * 10 + d
if value > 2147483647:
return -1
return valueJava
public static int nextGreaterElement(int n) {
char[] digits = String.valueOf(n).toCharArray();
int i = digits.length - 2;
while (i >= 0 && digits[i] >= digits[i + 1]) i--;
if (i < 0) return -1;
int j = digits.length - 1;
while (digits[j] <= digits[i]) j--;
char t = digits[i];
digits[i] = digits[j];
digits[j] = t;
int lo = i + 1, hi = digits.length - 1;
while (lo < hi) {
char u = digits[lo];
digits[lo] = digits[hi];
digits[hi] = u;
lo++;
hi--;
}
long value = 0;
for (char c : digits) {
value = value * 10 + (c - '0');
if (value > 2147483647L) return -1;
}
return (int) value;
}C++
int nextGreaterElement(int n) {
string digits = to_string(n);
int i = (int) digits.size() - 2;
while (i >= 0 && digits[i] >= digits[i + 1]) i--;
if (i < 0) return -1;
int j = (int) digits.size() - 1;
while (digits[j] <= digits[i]) j--;
swap(digits[i], digits[j]);
reverse(digits.begin() + i + 1, digits.end());
long long value = 0;
for (char c : digits) {
value = value * 10 + (c - '0');
if (value > 2147483647LL) return -1;
}
return (int) value;
}JavaScript
var nextGreaterElement = function(n) {
const digits = String(n).split("").map(Number);
let i = digits.length - 2;
while (i >= 0 && digits[i] >= digits[i + 1]) i--;
if (i < 0) return -1;
let j = digits.length - 1;
while (digits[j] <= digits[i]) j--;
const t = digits[i];
digits[i] = digits[j];
digits[j] = t;
const tail = digits.slice(i + 1).reverse();
const out = digits.slice(0, i + 1).concat(tail);
let value = 0;
for (let k = 0; k < out.length; k++) {
value = value * 10 + out[k];
if (value > 2147483647) return -1;
}
return value;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Two Pointers Technique