LeetCode 60. Permutation Sequence

Question

The set [1, 2, 3, ..., n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"

Example 3:

Input: n = 3, k = 1
Output: "123"

Constraints:

• 1 <= n <= 9
• 1 <= k <= n!

Source: https://leetcode.com/problems/permutation-sequence/

Solution

We find the result digit by digit. For each digit, we can determine its value by dividing k by the number of permutations of its suffix. By subtracting the number of skipped permutations from k, we keep narrowing k till we find a certain permutation.

Note that in each loop we need to removed current digit because we cannot reuse numbers. Also, permutations are in a lexicographic order, so we should keep nums sorted. Remove operations do not break the order of nums.

// Time Complexity, O(n)
public String getPermutation(int n, int k) {
    StringBuilder result = new StringBuilder();
    List<Integer> nums = new ArrayList<>();
    for (int i = 1; i <= n; i++) {
        nums.add(i);
    }
    // [0!, 1!, ..., (n-1)!]
    int[] factorials = new int[n];
    factorials[0] = 1;
    for (int i = 1; i < n; i++) {
        factorials[i] = i * factorials[i - 1];
    }

    // make k start from 0,
    // so that the result of k / factorials[n - pos - 1] has the same meaning as an index of nums
    k -= 1;
    // [1 (2 3 4 5)] (n-1)!=4!
    // [3 5 4 (1 2)] (n-3)!=2!
    // [3 5 4 2 1()] (n-5)!=0!
    for (int pos = 0; pos < n; pos++) {
        int index = k / factorials[n - pos - 1]; // skip suffix permutations as much as possible
        result.append(nums.get(index));
        nums.remove(index); // removing elements does not break the order of the list
        k -= index * factorials[n - pos - 1];
    }
    return result.toString();
}