Given a positive integer n, find the smallest integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive integer exists, return -1.
Note that the returned integer should fit in 32-bit integer, if there is a valid answer but it does not fit in 32-bit integer, return -1.
Example 1:
Input: n = 12
Output: 21
Example 2:
Input: n = 21
Output: -1
Constraints:
-
1 <= n <= 231 - 1
SOLUTION:
class Solution:
def nextGreaterElement(self, n: int) -> int:
digits = [int(c) for c in str(n)]
k = len(digits)
i = k - 1
while i > 0:
if digits[i - 1] < digits[i]:
break
i -= 1
if i == 0:
return -1
closest = i
for j in range(i, k):
if digits[j] > digits[i - 1] and digits[j] - digits[i - 1] <= digits[closest] - digits[i - 1]:
closest = j
digits[i - 1], digits[closest] = digits[closest], digits[i - 1]
op = 0
for d in range(i):
op = 10 * op + digits[d]
for d in range(k - 1, i - 1, -1):
op = 10 * op + digits[d]
return op if op <= ((1 << 31) - 1) else -1
Top comments (0)