556. Next Greater Element III
Model: qwen3.5:9b
Topics: String
FAANG asked: 0
Acceptance rate: 33.5%
Problem Breakdown
We are given a positive integer n and need to find its “next lexicographical permutation” using exactly the same digits. Essentially, we want the smallest number larger than n. If no such arrangement exists (e.g., digits are in descending order), or if the resulting number exceeds the 32-bit signed integer limit (), we must return -1.
Key Constraints & Edge Cases:
- Overflow Handling: Python handles arbitrarily large integers, but LeetCode requires us to simulate a 32-bit environment. If our calculated result exceeds
INT_MAX(2147483647), we explicitly return -1. - No Greater Permutation: This happens if the digits are sorted in descending order (e.g., input is
21). We must detect this and return-1. - Single Digit: If
nhas only one digit, no greater permutation exists with same digits.
Intuition
A brute-force approach would be to generate all permutations of the digits, sort them, find the first one larger than n, check for overflow, and convert back. However, generating permutations is computationally infeasible even if D (number of digits) is small (~10), because many will exceed 32-bit limits or be duplicates.
The key insight comes from combinatorics: to find the smallest number greater than n, we want to change as few digits as possible and increase them by the minimal amount necessary.
This implies finding a “pivot” digit in the sequence that can be swapped with a larger digit immediately following it, while keeping all preceding digits unchanged. Once swapped, the remaining suffix must be arranged in ascending order (smallest lexicographical value) to ensure we get the next smallest number, not just any greater one.
This is exactly the logic of the standard “Next Permutation” algorithm applied to a list of characters/digits.
Approach
- Convert: Transform
ninto a mutable list of digits (characters). - Find Pivot (
i): Scan from right to left to find the first digit that is smaller than its immediate neighbor on the right (digits[i] < digits[i+1]). This identifies where we can increase the value slightly. If no suchiexists, return-1. - Find Swap Candidate (
j): In the suffix starting ati + 1, find the smallest digit that is strictly greater thandigits[i]. Since the suffix from step 2 is guaranteed to be in descending order (non-increasing), we can scan from right to left and pick the first element larger thandigits[i]. - Swap: Swap
digits[i]withdigits[j]. This increases the prefix value minimally. - Reverse Suffix: Reverse the sequence of digits starting at index
i + 1to sort them in ascending order. Since they were descending before, reversing makes them smallest possible for that new pivot. - Convert & Check Overflow: Join the list back into a string and convert to integer. Compare against . If larger, return
-1.
Complexity Analysis
- Time Complexity: , where D is the number of digits in
n(max ~10 for this constraint). We traverse the list a constant number of times. Note: While technically linear with respect to input length, since max digits are bounded by 32-bit integer constraints, it effectively behaves like . - Space Complexity: to store the digit array/list during processing.
Solution
def nextGreaterElement(n: int) -> int:
# Define maximum value for a signed 32-bit integer
INT_MAX = (1 << 31) - 1
# Convert number to list of characters for mutability
digits = list(str(n))
# Step 1: Find the first digit from right that is smaller than its neighbor on left.
# We scan backwards looking for a descent point where digits[i] < digits[i+1].
i = len(digits) - 2
while i >= 0 and digits[i] >= digits[i + 1]:
i -= 1
# If no such pivot exists, the number is in descending order (no greater permutation possible).
if i == -1:
return -1
# Step 2: Find the smallest digit to the right of 'i' that is larger than digits[i].
# Since suffix [i+1:] is non-increasing, we scan from end backwards.
j = len(digits) - 1
while digits[j] <= digits[i]:
j -= 1
# Step 3: Swap the pivot with this candidate to increase value minimally
digits[i], digits[j] = digits[j], digits[i]
# Step 4: Reverse the suffix starting at i+1 to make it ascending (smallest possible)
digits[i + 1:] = reversed(digits[i + 1:])
# Convert back to integer and check for overflow constraint
res = int("".join(digits))
return -1 if res > INT_MAX else res
# Example usage:
print(nextGreaterElement(12)) # Output: 21
print(nextGreaterElement(21)) # Output: -1
Edge Cases Handled
- Descending Order: If input is
n = 21, the loop for finding pivot (i) finishes at-1. We immediately return-1without modification. - Overflow: The result is explicitly compared against
(1 << 31) - 1. Even if Python computes a larger integer, we enforce the problem constraint by returning-1in that case (e.g., input205978467, next permutation might exceed limit). - Single Digit: If
n = 5, loop for pivot runs once withi=-1. Returns-1correctly. - Duplicate Digits: The logic handles duplicates naturally (e.g.,
2303). It finds the correct smallest greater permutation (3023) by strictly checkingdigits[j] <= digits[i]during swap selection, ensuring we pick the first valid larger digit from right-to-left.