556. Next Greater Element III

Problem Statement

link: LeetCode.cn LeetCode Given a positive integer n, find the smallest integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive integer exists, return -1.

Note that the returned integer should fit in 32-bit integer, if there is a valid answer but it does not fit in 32-bit integer, return -1.

Example:

Input: n = 12 Output: 21

Input: n = 21 Output: -1

Solution Approach

To find the next greater element of a given positive integer, we traverse the digits from right to left to identify the first decreasing digit. Then, we swap it with the smallest digit to its right that is greater than itself. After that, we sort the digits to the right of the swapped digit in ascending order. This process ensures we obtain the smallest integer greater than the original.

Algorithm

1. Traverse the digits from right to left to find the first decreasing digit. This identifies the pivot point where the digits to its right can be rearranged to form a larger number.
2. Once the pivot digit is found, swap it with the smallest digit to its right that is greater than itself. This ensures that the new number formed will be greater than the original number.
3. Sort the digits to the right of the pivot point in ascending order. This ensures that the new number is the smallest possible integer greater than the original number.

Implement

    class Solution:
  def nextGreaterElement(self, n: int) -> int:
      # 1 2 4 3 2 1
      #   --- find most right side up trend i 2 4
      #.    find the firt n > i swap
      #     sort i + 1 ~ end
      s = list(str(n))
      i = len(s) - 2
      while i >= 0:
          if s[i] < s[i + 1]:
              break
          i -= 1
      if i == -1:
          return -1
      for j in range(len(s) - 1, i, -1):
          if s[j] > s[i]:
              s[j], s[i] = s[i], s[j]
              break
      s[i + 1:] = s[i + 1:][::-1]
      res = ''.join(s)
      return int(res) if int(res) <= 2**31 - 1 else -1

    
    

Twitter  facebook  Email