Skip to content

556. Next Greater Element III

Difficulty Topics

Description

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

next-greater-element-iii.py
class Solution:
    def nextGreaterElement(self, n: int) -> int:
        s = list(str(n))

        i = len(s) - 2
        while i >= 0 and s[i] >= s[i+1]:
            i -= 1

        if i < 0: return -1

        j = len(s) - 1
        while s[j] <= s[i]:
            j -= 1

        s[i],s[j] = s[j],s[i]

        s[i+1:] = reversed(s[i+1:])

        res = int("".join(s))

        return res if res < (1 << 31) else -1