algoadvance

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.

Example 1:

Input: n = 12
Output: 21

Example 2:

Input: n = 21
Output: -1

Constraints:

Clarifying Questions

  1. Q: What is the maximum value of n that may be provided?
    • A: n can go up to (2^{31} - 1) which is 2147483647.
  2. Q: Can n have leading zeros?
    • A: Since n is a positive integer, it should not have leading zeros except the trivial zero itself which is not within the given range.
  3. Q: Is the input n always a valid integer within the given range?
    • A: Yes, the input n will always be an integer within the range [1, 2^31 - 1].

Strategy

We need to find the next greater permutation of the number provided, or determine that no such number exists. The algorithm is similar to finding the next lexicographical permutation of a sequence.

  1. Identify Pivot: Traverse the number from the end to find the first digit that is smaller than the digit next to it. This is called the pivot.
  2. Find the Rightmost Successor: From the end again, find the smallest digit that is larger than the pivot.
  3. Swap: Swap the pivot with this digit.
  4. Reverse Suffix: Reverse the sequence after the original position of the pivot.

This algorithm ensures that we generate the next smallest permutation that is greater than the given number.

Code

def nextGreaterElement(n: int) -> int:
    num = list(str(n))
    length = len(num)
    
    # Step 1: Find the pivot point where the digit decreases
    i = length - 2
    while i >= 0 and num[i] >= num[i + 1]:
        i -= 1
    
    if i == -1:
        return -1  # No greater permutation
    
    # Step 2: Find the smallest number larger than num[i] to the right of i
    j = length - 1
    while num[j] <= num[i]:
        j -= 1
    
    # Step 3: Swap the pivot with this number
    num[i], num[j] = num[j], num[i]
    
    # Step 4: Reverse the sequence after the pivot
    num = num[:i + 1] + num[i + 1:][::-1]
    
    result = int(''.join(num))
    
    # Check if the result exceeds the 32-bit integer range
    if result > 2**31 - 1:
        return -1
    
    return result

# Example usage
print(nextGreaterElement(12))  # Output: 21
print(nextGreaterElement(21))  # Output: -1

Time Complexity

Hence, the overall time complexity is O(d) where d is the number of digits in the number. Given the constraints (d ≤ 10), this is efficient.

Space Complexity

The space complexity is O(d) due to the additional storage for the list of digits.

Try our interview co-pilot at AlgoAdvance.com