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 - 1The key idea behind #556 Next Greater Element III is recognizing that the problem is essentially asking for the next lexicographically greater permutation of the digits of the given integer. Instead of brute‑forcing all permutations, we can use a structured approach similar to the classic next_permutation algorithm.
Start by converting the number into a digit sequence (string or array). Scan from right to left to find the first position where the digits stop decreasing. This position acts as the pivot. Then locate the smallest digit on the right side that is larger than this pivot and swap them. Finally, reverse the suffix to make it the smallest possible order.
After reconstructing the integer, ensure the result fits within the 32-bit signed integer range. If no pivot exists, it means the digits are already in descending order and no greater permutation is possible.
This approach efficiently computes the answer in linear time relative to the number of digits.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Next Permutation on Digits | O(d) | O(d) |
CrioDo
This approach uses the concept of finding the next permutation of the digits of the number. We traverse the digits from right to left to find the first digit that is smaller than the digit next to it. Once found, we swap it with the smallest larger digit on its right and then reverse the sequence following the swapped digit.
Time Complexity: O(n log n) (due to sorting in worst case)
Space Complexity: O(1) (in-place swap and conversion)
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5int compare(const void* a, const
The solution involves converting the integer to a string and manipulating the characters to find the next permutation. We ensure to swap the digits right before reversing the tail end. We also handle possible overflow scenarios by checking if the result exceeds the 32-bit limit.
This approach entails understanding mathematical permutation generation principles. First, identify the point where the digits stop increasing when moving left-to-right, then swap it. Finally, regenerate that segment to form the smallest sequential increase.
Time Complexity: O(n^2) (as it checks for minimum swap position for small digits segment)
Space Complexity: O(n) (array storage)
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of permutation and digit-rearrangement problems appear in many technical interviews, including FAANG companies. This question tests understanding of permutations, greedy logic, and careful edge-case handling.
The optimal approach uses the next permutation technique on the digits of the number. By identifying a pivot, swapping it with the next larger digit on the right, and reversing the suffix, we can efficiently generate the smallest greater number using the same digits.
The problem asks for the smallest number greater than the given one using the same digits. This exactly matches the definition of the next lexicographical permutation, making the next permutation algorithm a natural and efficient solution.
Most solutions convert the integer into a string or an array of digits. This allows easy traversal, swapping, and reversing operations needed for implementing the next permutation logic.
This method parses digits from the number to locate the next higher permutation swap, initiating a reverse rotation to create the smallest increment. It precisely tracks indices, ensuring accurate results.