556. Next Greater Element III - Detailed Explanation

Problem Statement

Given a positive 32-bit integer n, you need to find the smallest 32-bit integer that is greater than n and can be formed by rearranging its digits. If no such number exists or the result exceeds the 32-bit integer range (2^31 - 1), return -1.

Examples

• Example 1:

  • Input: n = 12
  • Output: 21
  • Explanation: The digits "1" and "2" can be rearranged to form "21", which is the next greater number than "12".

• Example 2:

  • Input: n = 21
  • Output: -1
  • Explanation: No rearrangement of "21" produces a number greater than "21" (its digits are in descending order).

• Example 3:

  • Input: n = 534976
  • Output: 536479
  • Explanation: Rearranging the digits of "534976" gives "536479" as the smallest number greater than "534976".

Constraints

• 1 ≤ n ≤ 2³¹ - 1
• The answer must also be a 32-bit integer. If it isn’t, return -1.

Hints

• Think of Next Permutation:
  The problem is essentially asking you to compute the next permutation of the number’s digits.

• Traverse from Right to Left:
  To find the "pivot" where the digits stop increasing from right to left, scan from the end toward the beginning.

• Swap and Reverse:
  Once the pivot is found, swap it with the smallest digit in the suffix that is greater than the pivot, then reverse the suffix to get the smallest greater number.

• Handle Overflow:
  After forming the candidate number, ensure it is within the 32-bit integer range. If not, return -1.

Multiple Approaches

Approach 1: Next Permutation Algorithm

This is the most efficient approach and follows these steps:

1. Convert the integer to an array of digits.

2. Find the Pivot:
   Scan from right to left to find the first digit (pivot) that is less than the digit immediately after it.

3. Find the Rightmost Successor:
   From the right end, find the smallest digit that is greater than the pivot.

4. Swap:
   Swap the pivot with that digit.

5. Reverse Suffix:
   Reverse the digits to the right of the pivot's original position to form the smallest number.

6. Reassemble and Check:
   Convert the digits back to an integer. If the result exceeds 2^31 - 1, return -1.

Approach 2: Brute Force (Not Recommended)

One might consider generating all permutations of the digits, sorting them, and then picking the next greater one. However, this approach is exponential in time complexity (O(n!)) and impractical even for numbers with moderate digit counts (up to 10 digits in the worst case). Thus, the next permutation approach is far more optimal.

Step-by-Step Walkthrough with Example

Consider n = 534976. We will break down the next permutation algorithm step by step.

Step 1: Convert to Digits

Digits: [5, 3, 4, 9, 7, 6]

Step 2: Find the Pivot

• Traverse from the end to the beginning:
  • Compare 7 and 6: 7 > 6 → continue.
  • Compare 9 and 7: 9 > 7 → continue.
  • Compare 4 and 9: 4 < 9 → Pivot found at index 2 (digit = 4).

Step 3: Find the Rightmost Successor

• In the suffix (digits after index 2): [9, 7, 6], find the smallest digit greater than 4.
• Traverse from the end:
  • 6 > 4 → candidate.
  • 7 > 4 but 6 is smaller than 7.
  • 9 > 4.
• Choose digit 6 at index 5 as it is the rightmost digit greater than 4.

Step 4: Swap Pivot and Successor

• Swap digit 4 (index 2) and digit 6 (index 5):

  Before swap: [5, 3, 4, 9, 7, 6]
  After swap: [5, 3, 6, 9, 7, 4]

Step 5: Reverse the Suffix

• Reverse the digits after index 2 (positions 3 to end). Suffix before reverse: [9, 7, 4]
• Reversed suffix: [4, 7, 9]
• Final digits: [5, 3, 6, 4, 7, 9]

Step 6: Convert Back to Integer and Check

• The number formed is 536479.
• Since 536479 > 534976 and is within the 32-bit integer range, it is the answer.

Complexity Analysis

• Time Complexity: O(d), where d is the number of digits in n. Since d is at most 10 (for 32-bit integers), the algorithm is very efficient.
• Space Complexity: O(d) for storing the digits. The additional space is minimal.