Sponsored
Sponsored
This approach uses the concept of finding the next permutation of the digits of the number. We traverse the digits from right to left to find the first digit that is smaller than the digit next to it. Once found, we swap it with the smallest larger digit on its right and then reverse the sequence following the swapped digit.
Time Complexity: O(n log n) (due to sorting in worst case)
Space Complexity: O(1) (in-place swap and conversion)
1def nextGreaterElement(n: int) -> int:
2 digits = list(str(n))
3 i = len(digits) - 2
4 while i >= 0 and digits[i] >= digits[i + 1]:
5 i -= 1
6 if i == -1:
7 return -1
8 j = len(digits) - 1
9 while digits[j] <= digits[i]:
10 j -= 1
11 digits[i], digits[j] = digits[j], digits[i]
12 digits[i + 1:] = reversed(digits[i + 1:])
13 result = int(''.join(digits))
14 return result if result <= 2**31 - 1 else -1
15
16print(nextGreaterElement(12))The Python solution converts the number into a list of digits for ease of manipulation. The core logic finds the right index to swap and then reverses the list from there. The final calculation checks against Python's integer overflow, though Python handles large integers naturally.
This approach entails understanding mathematical permutation generation principles. First, identify the point where the digits stop increasing when moving left-to-right, then swap it. Finally, regenerate that segment to form the smallest sequential increase.
Time Complexity: O(n^2) (as it checks for minimum swap position for small digits segment)
Space Complexity: O(n) (array storage)
1
Python's straightforward handling of larger integers aids as we build permutations with clever slice reusing, compounding shortened permutations backwards.