Problem
Given an integer, find the next permutation of it in absolute order.
Examples
Example 1
Input: num = 48975
Output: 49578
Solution
Method 1 - Convert the number to array of digits
This problem is similar to Next Permutation. So, our approach can be:
- Convert the integer to a list of digits.
- Traverse the list from the end to find the first decreasing element.
- Traverse the list from the end again to find the element just larger than the found element and swap them.
- Reverse the sublist from the next position of the found element to the end.
- Convert the list of digits back to an integer.
Code
Java
public class Solution {
public int nextPermutation(int num) {
char[] digits = String.valueOf(num).toCharArray();
int n = digits.length;
if (n <= 1) return num;
// Step 1: Find the first decreasing element from the end
int i = n - 2;
while (i >= 0 && digits[i] >= digits[i + 1]) {
i--;
}
if (i >= 0) { // If there's any element to swap with
// Step 2: Find the element just larger than digits[i] to swap with
int j = n - 1;
while (j >= 0 && digits[j] <= digits[i]) {
j--;
}
// Step 3: Swap elements
char temp = digits[i];
digits[i] = digits[j];
digits[j] = temp;
}
// Step 4: Reverse the sublist from i + 1 to the end
reverse(digits, i + 1, n - 1);
// Convert char array back to integer
return Integer.parseInt(new String(digits));
}
private void reverse(char[] nums, int start, int end) {
while (start < end) {
char temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
}
Python
class Solution:
def nextPermutation(self, num: int) -> int:
digits = list(map(int, str(num)))
n = len(digits)
if n <= 1:
return num
# Step 1: Find the first decreasing element from the end
i = n - 2
while i >= 0 and digits[i] >= digits[i + 1]:
i -= 1
if i >= 0: # If there's any element to swap with
# Step 2: Find the element just larger than digits[i] to swap with
j = n - 1
while j >= 0 and digits[j] <= digits[i]:
j -= 1
# Step 3: Swap elements
digits[i], digits[j] = digits[j], digits[i]
# Step 4: Reverse the sublist from i + 1 to the end
self.reverse(digits, i + 1, n - 1)
# Convert list of digits back to an integer
return int(''.join(map(str, digits)))
def reverse(self, nums: List[int], start: int, end: int) -> None:
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1
Complexity
- ⏰ Time complexity:
O(n)
, wheren
is the number of digits in the integer, due to linear traversal and manipulation. - 🧺 Space complexity:
O(1)
, disregarding the input memory, as the operations are performed in place.