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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Next Greater Element III

Number: 556

Difficulty: Medium

Paid? No

Companies: Amazon, DoorDash, Meta, Microsoft, TikTok, Mitsogo, Adobe, Google, Goldman Sachs, Tekion, Bloomberg

Problem Description

Given a positive integer n, determine the smallest integer that has exactly the same digits as n and is greater in value than n. If no such integer exists or the result does not fit in a 32-bit integer, return -1.

Key Insights

  • Transform the problem into finding the next permutation of the digit sequence of n.
  • Traverse the digits from right to left to find the first digit that is smaller than its next digit (this becomes the pivot).
  • If no pivot exists (i.e., the digits are in non-increasing order), then no next greater permutation exists.
  • Once the pivot is found, locate the smallest digit greater than the pivot in the suffix.
  • Swap the pivot with this digit and reverse the suffix to form the smallest possible number greater than n.
  • Finally, check if the result fits within the 32-bit integer range.

Space and Time Complexity

Time Complexity: O(d) where d is the number of digits in n (in worst-case each digit is processed multiple times) Space Complexity: O(d) if considering the space to store the digits; otherwise, O(1) extra space if the digits are processed in place.

Solution

The solution relies on generating the next permutation of the digits of n. Here’s the approach:

  1. Convert n to a list of characters (digits).
  2. Starting from the end, find the first digit that is smaller than the digit immediately after it (this is the pivot).
  3. If no pivot is found, return -1 because n is the largest possible permutation.
  4. From the end of the list, find the first digit that is greater than the pivot.
  5. Swap the pivot with that digit.
  6. Reverse the subarray after the pivot position to get the smallest order.
  7. Convert the list back to an integer and check the 32-bit integer limitation. Data structures used include an array (or list) to hold the digits, and the algorithm mainly uses two-pointer techniques for reverse operations.

Code Solutions

# Python solution for Next Greater Element III

def nextGreaterElement(n: int) -> int:
    # Convert integer to list of characters for easier manipulation
    digits = list(str(n))
    length = len(digits)
    
    # Step 1: Find the pivot where the next digit is greater
    pivot = -1
    for i in range(length - 2, -1, -1):
        if digits[i] < digits[i + 1]:
            pivot = i
            break
    # If pivot is not found, no greater permutation exists
    if pivot == -1:
        return -1
    
    # Step 2: Find the digit (from the end) that is greater than the pivot
    for j in range(length - 1, pivot, -1):
        if digits[j] > digits[pivot]:
            # Step 3: Swap the found digit with pivot
            digits[pivot], digits[j] = digits[j], digits[pivot]
            break
    
    # Step 4: Reverse the portion after the pivot to get the smallest order
    digits[pivot + 1:] = digits[pivot + 1:][::-1]
    
    # Convert the list back to integer
    result = int("".join(digits))
    
    # Check for 32-bit integer limit
    if result >= 2**31:
        return -1
    return result

# Example usage:
# print(nextGreaterElement(12))  # Output: 21
← Back to All Questions