556. Next Greater Element III (Python)

Related Topic

String.

Description

Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive 32-bit integer exists, you need to return -1.

Sample I/O

Example 1

Input: 12
Output: 21

Example 2

Input: 21
Output: -1

Methodology

This is an extention question of 503. Next Greater Element II Instand of using stack, this question is using string operator.

To find the next greater element for a integer, we can split it into individual digits. We iterate the list from right to left and find the first digit that in descending order and this digit we called flag is going to be the one that we need to replace to make it a little bigger. Now we need to find the replacement digit from flag digit’s right side. Since right side is always in asecending order (from right end), it will be easy to start from right to left again. Now we iterate each digit from right and left until we reach to the flag. There are some conditins to consider. If there is only one digit or if all dights on the right are same, then we will swap the flag and its first right digit. Otherwise, we just find the one that greater than flag then swap those two and reverse the new right side. Other conditions will return -1. Don’t forget to check it is greater than 32-bit which 2^31-1. Python support string digit calculation.

def nextGreaterElement(self, n: int) -> int:
        n = [x for x in str(n)]
        size = len(n)
        ans = -1
        for i in range(size-1,-1,-1):
            if n[i-1] < n[i] and i>0:
                if i == size-1 or n[-1]==n[i]: 
                    n[i-1], n[i]=n[i],n[i-1]
                    ans = int(''.join(n))
                    return -1 if ans > 2147483647 else ans
                else:
                    for j in range(size-1, i-1, -1):
                        if n[j]>n[i-1]:
                            n[i-1], n[j]=n[j],n[i-1]
                            break 
                    ans = int(''.join(n[:i]+n[i:][::-1]))
                return -1 if ans > 2147483647 else ans
        return ans

BigO

The total cost will be O(n).