Problem

Given an integer, find the next permutation of it in absolute order.

Examples

Example 1

1
2

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:

  1. Convert the integer to a list of digits.
  2. Traverse the list from the end to find the first decreasing element.
  3. Traverse the list from the end again to find the element just larger than the found element and swap them.
  4. Reverse the sublist from the next position of the found element to the end.
  5. Convert the list of digits back to an integer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

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--;
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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), where n 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.