Next Greater Element III
Next Greater Element III is a medium arrays & hashing problem solved with the right to left traversal pattern.
The best approach, optimal (next permutation of the digits), runs in O(d) time and O(d) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every arrangement) up.
Problem
Given a positive integer n, return the smallest integer greater than n that uses exactly the same digits as n (each digit the same number of times).
If no such integer exists, or the smallest one does not fit in a signed 32-bit integer, return -1.
Examples
Example 1
- Input
n = 2763- Output
3267- Why
- Among rearrangements of the digits 2, 7, 6, 3, the smallest one larger than 2763 is 3267.
Example 2
- Input
n = 5310- Output
-1- Why
- The digits are already in descending order, so no rearrangement is larger.
Example 3
- Input
n = 2147483476- Output
2147483647- Why
- The next arrangement still fits in a signed 32-bit integer (it is exactly the largest one).
Constraints
1 <= n <= 2^31 - 1- Return
-1if no larger arrangement exists or if it does not fit in a signed 32-bit integer.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (try every arrangement) | O(d! · d) | O(d) |
| Optimal (next permutation of the digits) | O(d) | O(d) |
1Brute force (try every arrangement)
O(d! · d)Up to d! arrangements of the d ≤ 10 digits, each built in O(d).O(d)The recursion depth and the used flags.Generate every distinct arrangement of the digits with backtracking, convert each to a number, and keep the smallest one that is larger than n and still fits in 32 bits.
- Sort the digits; backtrack over unused positions, skipping a digit equal to its unused left neighbour to avoid duplicates.
- For each complete arrangement value v (as a long): if n < v <= 2^31 - 1, best = min(best, v).
- Return best, or -1 if none was found.
class Solution {
private long best;
private long target;
public int nextGreaterElement(int n) {
char[] digits = String.valueOf(n).toCharArray();
Arrays.sort(digits);
best = Long.MAX_VALUE;
target = n;
build(digits, new boolean[digits.length], 0, 0);
return best == Long.MAX_VALUE ? -1 : (int) best;
}
private void build(char[] digits, boolean[] used, int depth, long value) {
if (depth == digits.length) {
if (value > target && value <= Integer.MAX_VALUE) best = Math.min(best, value);
return;
}
for (int i = 0; i < digits.length; i++) {
if (used[i]) continue;
if (i > 0 && digits[i] == digits[i - 1] && !used[i - 1]) continue;
used[i] = true;
build(digits, used, depth + 1, value * 10 + (digits[i] - '0'));
used[i] = false;
}
}
}class Solution:
def nextGreaterElement(self, n: int) -> int:
digits = sorted(str(n))
self.best = None
self.target = n
self.build(digits, [False] * len(digits), 0, 0)
return -1 if self.best is None else self.best
def build(self, digits: List[str], used: List[bool], depth: int, value: int) -> None:
if depth == len(digits):
if self.target < value <= 2 ** 31 - 1 and (self.best is None or value < self.best):
self.best = value
return
for i in range(len(digits)):
if used[i]:
continue
if i > 0 and digits[i] == digits[i - 1] and not used[i - 1]:
continue
used[i] = True
self.build(digits, used, depth + 1, value * 10 + int(digits[i]))
used[i] = Falseclass Solution {
long long best, target;
public:
int nextGreaterElement(int n) {
string digits = to_string(n);
sort(digits.begin(), digits.end());
best = LLONG_MAX;
target = n;
vector<bool> used(digits.size(), false);
build(digits, used, 0, 0);
return best == LLONG_MAX ? -1 : (int)best;
}
private:
void build(const string& digits, vector<bool>& used, int depth, long long value) {
if (depth == (int)digits.size()) {
if (value > target && value <= INT_MAX) best = min(best, value);
return;
}
for (int i = 0; i < (int)digits.size(); i++) {
if (used[i]) continue;
if (i > 0 && digits[i] == digits[i - 1] && !used[i - 1]) continue;
used[i] = true;
build(digits, used, depth + 1, value * 10 + (digits[i] - '0'));
used[i] = false;
}
}
};function nextGreaterElement(n) {
const digits = String(n).split("").sort();
const used = new Array(digits.length).fill(false);
let best = Infinity;
function build(depth, value) {
if (depth === digits.length) {
if (value > n && value <= 2147483647) best = Math.min(best, value);
return;
}
for (let i = 0; i < digits.length; i++) {
if (used[i]) continue;
if (i > 0 && digits[i] === digits[i - 1] && !used[i - 1]) continue;
used[i] = true;
build(depth + 1, value * 10 + Number(digits[i]));
used[i] = false;
}
}
build(0, 0);
return best === Infinity ? -1 : best;
}2Optimal (next permutation of the digits)
O(d)A constant number of passes over the d ≤ 10 digits.O(d)The digit array.Scan from the right for the first position i with d[i] < d[i + 1]; if none exists the digits are non-increasing and the answer is -1. Swap d[i] with the rightmost digit larger than it, then reverse the suffix after i so it becomes the smallest possible. Convert with a long and reject values above 2^31 - 1.
- d = digits of n; i = len - 2; while i >= 0 and d[i] >= d[i + 1], i--.
- If i < 0, return -1.
- j = len - 1; while d[j] <= d[i], j--. Swap d[i], d[j].
- Reverse d[i + 1 …]; parse as long; return it if <= 2^31 - 1, else -1.
class Solution {
public int nextGreaterElement(int n) {
char[] d = String.valueOf(n).toCharArray();
int i = d.length - 2;
while (i >= 0 && d[i] >= d[i + 1]) i--;
if (i < 0) return -1;
int j = d.length - 1;
while (d[j] <= d[i]) j--;
char t = d[i]; d[i] = d[j]; d[j] = t;
for (int l = i + 1, r = d.length - 1; l < r; l++, r--) {
t = d[l]; d[l] = d[r]; d[r] = t;
}
long value = Long.parseLong(new String(d));
return value > Integer.MAX_VALUE ? -1 : (int) value;
}
}class Solution:
def nextGreaterElement(self, n: int) -> int:
d = list(str(n))
i = len(d) - 2
while i >= 0 and d[i] >= d[i + 1]:
i -= 1
if i < 0:
return -1
j = len(d) - 1
while d[j] <= d[i]:
j -= 1
d[i], d[j] = d[j], d[i]
d[i + 1:] = reversed(d[i + 1:])
value = int("".join(d))
return -1 if value > 2 ** 31 - 1 else valueclass Solution {
public:
int nextGreaterElement(int n) {
string d = to_string(n);
int i = (int)d.size() - 2;
while (i >= 0 && d[i] >= d[i + 1]) i--;
if (i < 0) return -1;
int j = (int)d.size() - 1;
while (d[j] <= d[i]) j--;
swap(d[i], d[j]);
reverse(d.begin() + i + 1, d.end());
long long value = stoll(d);
return value > INT_MAX ? -1 : (int)value;
}
};function nextGreaterElement(n) {
const d = String(n).split("");
let i = d.length - 2;
while (i >= 0 && d[i] >= d[i + 1]) i--;
if (i < 0) return -1;
let j = d.length - 1;
while (d[j] <= d[i]) j--;
[d[i], d[j]] = [d[j], d[i]];
for (let l = i + 1, r = d.length - 1; l < r; l++, r--) [d[l], d[r]] = [d[r], d[l]];
const value = Number(d.join(""));
return value > 2147483647 ? -1 : value;
}Edge cases to test
- Single digit, or digits in non-increasing order: -1
- Repeated digits, like 1221 or 115
- The next arrangement exceeds 2^31 - 1 (for example 2147483486 → 2147483648): -1
- Zeros in the number, like 1020
Hints
Hint 1
This is the next permutation of the digit sequence. Where does the rightmost change have to happen?
Hint 2
From the right, find the first digit that is smaller than the digit after it. Everything to its right is non-increasing.
Hint 3
Swap that digit with the smallest larger digit to its right, then reverse the suffix. Check the result against the 32-bit limit with a long.
FAQ
What is the best time complexity for Next Greater Element III?
Optimal (next permutation of the digits) runs in O(d) time and O(d) extra space. A constant number of passes over the d ≤ 10 digits.
Which pattern does Next Greater Element III use?
It is a arrays & hashing problem that uses the right to left traversal pattern. Other problems with the same pattern: Array Leaders, Product of Array Except Self, Next Permutation.
Is there a brute force solution for Next Greater Element III?
Yes. Brute force (try every arrangement) takes O(d! · d) time and O(d) space. Generate every distinct arrangement of the digits with backtracking, convert each to a number, and keep the smallest one that is larger than n and still fits in 32 bits.
Which edge cases should I test for Next Greater Element III?
Single digit, or digits in non-increasing order: -1; Repeated digits, like 1221 or 115; The next arrangement exceeds 2^31 - 1 (for example 2147483486 → 2147483648): -1; Zeros in the number, like 1020.