MediumNeetCode150MathTwo PointersString
Next Greater Element III
Find next greater number with same digits.
Examples
Input
n = 12
Output
21
Next greater with same digits.
Constraints
- •
1 <= n <= 2^31-1 - •
-1 if no such number
Approaches
Generate all permutations.
CodeT: O(d! * d) | S: O(d) d=digits
Same as next permutation.
CodeT: O(d) | S: O(1)
Same approach.
CodeT: O(d) | S: O(1)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force | O(d! * d) | O(d) d=digits | Generate all permutations. |
| Next Permutation | O(d) | O(1) | Same as next permutation. |
| Next Permutation Optimized | O(d) | O(1) | Same approach. |
Brute Force
T: O(d! * d)S: O(d) d=digits
Generate all permutations.
Next Permutation
T: O(d)S: O(1)
Same as next permutation.
Next Permutation Optimized
T: O(d)S: O(1)
Same approach.
Common Mistakes
Not handling overflow
No greater permutation exists
Off-by-one in reverse