Problem statement

https://binarysearch.com/problems/Next-Integer-Permutation/

Solution

Equal to Leetcode 0556. Next Greater Element III.

Complexity

It is O(log n) for time and space.

Code

class Solution:
    def solve(self, n):
        digits = list(str(n))
        i = len(digits) - 1
        while i-1 >= 0 and digits[i] <= digits[i-1]:
            i -= 1
            
        if i == 0: return int("".join(sorted(digits)))
        
        j = i
        while j+1 < len(digits) and digits[j+1] > digits[i-1]:
            j += 1
        
        digits[i-1], digits[j] = digits[j], digits[i-1]
        digits[i:] = digits[i:][::-1]
        ret = int(''.join(digits))

        return ret