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 - 1This 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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) (due to sorting in worst case)
Space Complexity: O(1) (in-place swap and conversion)
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) (as it checks for minimum swap position for small digits segment)
Space Complexity: O(n) (array storage)
| Approach | Complexity |
|---|---|
| Approach 1: Next Permutation | Time Complexity: O(n log n) (due to sorting in worst case) |
| Approach 2: Mathematical Permutation Logic | Time Complexity: O(n^2) (as it checks for minimum swap position for small digits segment) |
How many LeetCode problems should you solve? #leetcode #techinterview #developer #softwareengineer • CrioDo • 304,599 views views
Watch 9 more video solutions →Practice Next Greater Element III with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor