Next Greater Element III

#leetcode #dsa #theabbie

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