We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Next Greater Element III

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem requires finding the next permutation of the digits of n that is greater than n.
  • The solution can be approached using the "next permutation" algorithm, which involves rearranging the digits.
  • The constraints of the problem ensure that we only work with positive integers less than 2^31.

Space and Time Complexity

Time Complexity: O(k), where k is the number of digits in the integer n.
Space Complexity: O(1), since we are modifying the digits in place without using additional data structures.

Solution

To solve this problem, we can utilize the next permutation algorithm. The steps involved are as follows:

  1. Convert the integer to a list of its digits.
  2. Identify the first pair of adjacent digits (from right to left) where the left digit is smaller than the right digit. This identifies the point where we need to make a swap to create a larger number.
  3. If no such pair exists, return -1 as it means we are at the highest permutation.
  4. Find the smallest digit to the right of this identified position that is larger than the identified left digit and swap them.
  5. Reverse the digits to the right of the original position to get the smallest possible number.
  6. Convert the list of digits back to an integer and check if it is within the 32-bit integer range.

Code Solutions

def nextGreaterElement(n: int) -> int:
    digits = list(str(n))
    length = len(digits)
    
    # Step 1: Find the first decreasing element from the end
    for i in range(length - 2, -1, -1):
        if digits[i] < digits[i + 1]:
            break
    else:
        return -1  # No greater permutation
    
    # Step 2: Find the element just larger than digits[i]
    for j in range(length - 1, i, -1):
        if digits[j] > digits[i]:
            # Step 3: Swap
            digits[i], digits[j] = digits[j], digits[i]
            break
    
    # Step 4: Reverse the digits after position i
    digits[i + 1:] = reversed(digits[i + 1:])
    
    # Convert back to integer
    result = int(''.join(digits))
    
    # Check for 32-bit integer overflow
    return result if result < 2**31 else -1
← Back to All Questions