Next Greater Element III
Medium · Two Pointers · Explanation and code example
Next Permutation of Decimal Digits
How it works
The rightmost digit that is smaller than its successor is the pivot for the smallest increase. Swap it with the smallest larger digit in the suffix, then reverse that descending suffix to minimize the remaining digits. Reject if no larger permutation or if the result exceeds signed 32-bit range.
Steps
- Find the rightmost increasing pivot.
- Swap it with the rightmost larger suffix digit.
- Reverse the suffix and validate the numeric result.
Complexity
- Time: O(d), for d digits.
- Space: O(d) for the digit string/list.
Things to watch for
- Use exactly the original digits.
- A fully descending digit sequence has no answer.
- Check INT_MAX after constructing the permutation.
Python code example
class Solution:
def nextGreaterElement(self, n: int) -> int:
def nextPermutation(s: list[str]) -> str:
i = len(s) - 2
while i >= 0:
if s[i] < s[i + 1]:
break
i -= 1
if i >= 0:
for j in range(len(s) - 1, i, -1):
if s[j] > s[i]:
break
s[i], s[j] = s[j], s[i]
reverse(s, i + 1, len(s) - 1)
return ''.join(s)
def reverse(s: list[str], l: int, r: int):
while l < r:
s[l], s[r] = s[r], s[l]
l += 1
r -= 1
s = nextPermutation(list(str(n)))
ans = int(s)
return -1 if ans > 2**31 - 1 or ans <= n else ans
C++ code example
class Solution {
public:
int nextGreaterElement(int n) {
string s = to_string(n);
ranges::next_permutation(s);
const long ans = stol(s);
return ans > INT_MAX || ans <= n ? -1 : ans;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.