Watch 10 video solutions for Next Greater Element III, a medium level problem involving Math, Two Pointers, String. This walkthrough by Pepcoding has 19,077 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 1:
Input: n = 12 Output: 21
Example 2:
Input: n = 21 Output: -1
Constraints:
1 <= n <= 231 - 1Problem Overview: Given a positive 32-bit integer n, rearrange its digits to form the next greater integer using exactly the same digits. If no such integer exists, or the result exceeds the 32-bit signed integer range, return -1.
Approach 1: Next Permutation (O(n) time, O(1) space)
This problem is essentially the classic next permutation task applied to the digits of an integer. Convert the number into a digit array or string. Traverse from right to left to find the first index where digits[i] < digits[i+1]. This position marks the pivot where a larger permutation can be formed. Then scan the suffix from the end to locate the smallest digit greater than digits[i], swap them, and reverse the suffix after i to make it the smallest possible arrangement. The algorithm performs a few linear scans over the digits, giving O(n) time with constant extra space. This technique is a common permutation trick when working with digit manipulation problems involving string processing and two pointers style scanning from both ends.
Approach 2: Mathematical Permutation Logic (O(n) time, O(1) space)
This approach derives the same idea directly through mathematical reasoning about digit order. Starting from the least significant digit, identify the first digit that breaks the non-increasing sequence when moving left. That digit is the pivot. The digits to the right are already in descending order, meaning they form the largest permutation of that suffix. To get the next greater number, swap the pivot with the smallest digit in that suffix that is larger than it. After the swap, reorder the suffix into ascending order so the resulting number is the smallest valid integer greater than the original. The process involves simple digit comparisons and swaps, making it efficient and memory-friendly. It highlights the role of permutation ordering in math-based digit manipulation problems.
Recommended for interviews: The Next Permutation approach is the expected solution. Interviewers often look for recognition that the task is identical to the next lexicographical permutation problem. Implementing the pivot search, swap, and suffix reversal in O(n) time demonstrates solid understanding of permutations and in-place array manipulation. The mathematical explanation helps justify why the algorithm works, but the next permutation implementation is typically what candidates code during interviews.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Next Permutation | O(n) | O(1) | General case. Standard algorithm for generating the next lexicographical permutation of digits. |
| Mathematical Permutation Logic | O(n) | O(1) | Useful for reasoning about digit order and permutation behavior without explicitly referencing the next permutation algorithm. |