LC 0556 [M] Next Greater Element III - ALawliet/algorithms GitHub Wiki

same idea as 31. Next Permutation

Let us start from example and see how our algorithm should work.
Imaigne n = 234157641. Our goal is to find next number with the same digits, which is greater than given one and which is the smallest one. It makes sense to try to take our number as close to original one as possible. Let us try to do it: can it start from 2......, yes, for example 24.... Can it start with 2341...? Yes, it can be 23417.... Can it start with 23415...? No, it can not, and the reason, that the rest what we have 7641 already biggest number given digits 7, 6, 4, 1.
So, we can see now, how our algorithm should work:

Start from the end and look for increasing pattern, it our case 7641.
If it happen, that all number has increasing pattern, there is no bigger number with the same digits, so we can return -1.
Now, we need to find the first digit in our ending, which is less or equal to digits[i-1]: we have ending 5 7641 and we are looking for the next number with the same digits. What can go instead of 5: it is 6! Let us change these two digits, so we have 6 7541 now. Finally, we need to reverse last ditits to get 6 1457 as our ending.
Complexity: time complexity is O(m), where m is number of digits in our number, space complexity O(m) as well.

i = start of decreasing suffix 5[7]641
i-1 = smaller number before the decreasing suffix [5]7641
j = first bigger number than i-1 in the decreasing suffix 57[6]41
swap i-1, j [6]7[5]41
reverse everything starting from i to the end of the decreasing suffix 6[1457]

class Solution:
    def nextGreaterElement(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 -1
        
        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 if ret < 1<<31 else -1

1<<31 == 2**31