LC556 Next Greater Element III

class Solution:
    def nextGreaterElement(self, n: int) -> int:
        # time O(NlgN) worst 2N,  space O(N), where N is # digits ?
        # notice, 32bit max interger is 2^31 -1 
        # step1,  reverse digits, find target number with, idx smaller than lower digit
        # step2, reverve its lower digit then loop to lower digit until find the smallest number bigger than target number,mark as smallest 
        # step3, swap smallest number and target number
        # step4,  start from target_idx-1, to  idx =0 sort to make sure lower index has larger number 
        # step5, reverse list and convert into string, compare with max 32 bit number 
        if n < 10:
            return -1
        s = list(str(n)[::-1])
        size = len(s)
        smallest = None
        for i in range(size-1):
            if s[i+1] <s[i]:
                print('i',i)
                smallest = s[i]
                small_idx = i
                idx = i+1
                break
        if not smallest:
            return -1
    
        for j in range(small_idx+1):
            if smallest > s[j] and s[j] > s[idx]:
                smallest = s[j]
                small_idx = j
        s[idx],s[small_idx] = s[small_idx],s[idx]
        s[:idx] = sorted(s[:idx],reverse=True)
        res = int(''.join(s[::-1])) 
        if res > 2**31-1:
            return -1
        else:
            return res