LeetCode 556: Next Greater Element III ·

Table of Contents

Meta Data
#

Difficulty: medium First Attempt: 2025-04-13

Total time: 5:00.00

Intuition
#

This is the classic Next Permutation problem, but with one additional constraint:
the number must fit within a 32-bit signed integer.
Therefore, we need to perform an extra check at the end of the algorithm to ensure the result is valid.

Approach
#

class Solution:
    def nextGreaterElement(self, n: int) -> int:
        digits = list(str(n))

        i = len(digits)-2
        while i != -1 and digits[i]>=digits[i+1]:
            i -= 1

        if i == -1:
            return -1

        j = len(digits)-1
        while digits[i]>=digits[j]: 
            j -=1

        digits[i], digits[j] = digits[j], digits[i]
        digits[i+1:] = reversed(digits[i+1:])
        res = int("".join(digits))

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