Problem

Given n and k, return the k-th permutation sequence of permutations of numbers {1, 2, .., n}.

OR

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
2
3
4
5
6

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

Given n and k, return the kth permutation sequence.

Examples

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

1
2
3
4
5
6

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

For example, given n = 3, k = 4, ans = “231”

More Examples

Example 1:

1
2

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

Example 2:

1
2

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

Example 3:

1
2

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

Constraints

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

Notes

Good questions to ask the interviewer:

  • What if n is greater than 10. How should multiple digit numbers be represented in string? –> In this case, just concatenate the number to the answer. So if n = 11, k = 1, ans = “1234567891011”
  • Whats the maximum value of n and k? –> In this case, k will be a positive integer thats less than INT_MAX. n is reasonable enough to make sure the answer does not bloat up a lot.

Solution

Method 1 – Naive (Repeated Next Permutation)

Intuition

The simplest way to find the k-th permutation is to start with the first permutation (sorted order) and repeatedly generate the next permutation k-1 times. This uses the standard next-permutation algorithm.

Approach

  1. Start with the sequence [1, 2, ..., n].
  2. Apply the next permutation operation k-1 times.
  3. Return the resulting sequence as the k-th permutation.

This approach is straightforward but inefficient for large n or k.

Complexity

  • ⏰ Time complexity: O(n * k) (since each next permutation is O(n), and we do it k-1 times; for k = n!, this is O(n * n!)).
  • 🧺 Space complexity: O(n) (for storing the current permutation).

Method 2 – Mathematical Construction

Intuition

I have discussed a similar problem of finding the next permutation sequence of a given permutation here - Next permutation of a number. We have also discussed - Next even permutation of a number.

Before reading this article further I strongly suggest to read my previous post to find Permutation Rank. Basically given a permutation we compute how many permutations is possible to fix a number in a particular position of the array. Then we sum total such permutations for all positions to get the rank of the permutation. Now, in this question we are asking for the reverse question i.e. given the rank, find the permutation.

Instead of generating all possible permutations, we use factorial math to directly determine the k-th permutation. The main insight is that for n numbers, the first digit determines blocks of (n-1)! permutations. By dividing k by these blocks, we can select the correct digit for each position.

Let’s break down the process with a detailed example:

Suppose n = 4 and k = 8. The full list of permutations for [1, 2, 3, 4] in lexicographic order is:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

 1. [1, 2, 3, 4]
 2. [1, 2, 4, 3]
 3. [1, 3, 2, 4]
 4. [1, 3, 4, 2]
 5. [1, 4, 2, 3]
 6. [1, 4, 3, 2]
 7. [2, 1, 3, 4]
 8. [2, 1, 4, 3]
 9. [2, 3, 1, 4]
10. [2, 3, 4, 1]
11. [2, 4, 1, 3]
12. [2, 4, 3, 1]
13. [3, 1, 2, 4]
14. [3, 1, 4, 2]
15. [3, 2, 1, 4]
16. [3, 2, 4, 1]
17. [3, 4, 1, 2]
18. [3, 4, 2, 1]
19. [4, 1, 2, 3]
20. [4, 1, 3, 2]
21. [4, 2, 1, 3]
22. [4, 2, 3, 1]
23. [4, 3, 1, 2]
24. [4, 3, 2, 1]

Step-by-step reasoning:

  1. There are 4! = 24 total permutations. For the first digit, each number fixes (4-1)! = 6 permutations. So, the first 6 permutations start with 1, the next 6 with 2, and so on.
  2. Since k = 8, and we use zero-based indexing (k-1 = 7), the first digit is at index 7/6 = 1, which is 2. So, our answer starts with 2.
  3. Remove 2 from the list. Now, the remaining numbers are [1, 3, 4], and k' = 7 % 6 = 1.
  4. For the second digit, each number fixes (3-1)! = 2 permutations. The index is 1/2 = 0, so we pick 1. Our answer is now [2, 1].
  5. Remove 1. Remaining numbers: [3, 4], k’’ = 1 % 2 = 1.
  6. For the third digit, each number fixes (2-1)! = 1 permutation. The index is 1/1 = 1, so we pick 4. Our answer is [2, 1, 4].
  7. Remove 4. Remaining number: [3], k’’’ = 1 % 1 = 0.
  8. The last digit is 3. Final answer: [2, 1, 4, 3].

This process generalizes for any n and k, allowing us to build the k-th permutation efficiently by selecting digits one by one using division and modulo operations with factorials.

Approach

  1. Start with a list of numbers from 1 to n.
  2. Precompute factorials up to n to help determine the number of permutations for each position.
  3. Adjust k to be zero-based (subtract 1).
  4. For each position:
    • Find the index of the number to use by dividing k by the factorial of the remaining positions.
    • Append the selected number to the result and remove it from the list.
    • Update k to reflect the remaining permutations.
  5. Return the constructed permutation as a string.
Examples

Suppose n = 4, k = 8. The list of all permutations (lexicographically) is:

1
2
3
4
5
6
7
8
9

 1. [1, 2, 3, 4]
 2. [1, 2, 4, 3]
 3. [1, 3, 2, 4]
 4. [1, 3, 4, 2]
 5. [1, 4, 2, 3]
 6. [1, 4, 3, 2]
 7. [2, 1, 3, 4]
 8. [2, 1, 4, 3]
 ...

To find the 8th permutation:

  • The first digit is the second number (since 7/6 = 1, zero-based), so start with 2.
  • Remove 2, update k, and repeat for the next positions.
  • Continue until all positions are filled.
  • The result is [2, 1, 4, 3].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> nums;
        vector<int> fact(n + 1, 1);
        for (int i = 1; i <= n; ++i) {
            nums.push_back(i);
            fact[i] = fact[i - 1] * i;
        }
        k -= 1;
        string ans;
        for (int i = 1; i <= n; ++i) {
            int idx = k / fact[n - i];
            ans += to_string(nums[idx]);
            nums.erase(nums.begin() + idx);
            k -= idx * fact[n - i];
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func getPermutation(n int, k int) string {
    nums := make([]int, n)
    fact := make([]int, n+1)
    fact[0] = 1
    for i := 1; i <= n; i++ {
        nums[i-1] = i
        fact[i] = fact[i-1] * i
    }
    k--
    ans := ""
    for i := 1; i <= n; i++ {
        idx := k / fact[n-i]
        ans += strconv.Itoa(nums[idx])
        nums = append(nums[:idx], nums[idx+1:]...)
        k -= idx * fact[n-i]
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public String getPermutation(int n, int k) {
        List<Integer> nums = new ArrayList<>();
        int[] fact = new int[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++) {
            nums.add(i);
            fact[i] = fact[i - 1] * i;
        }
        k--;
        StringBuilder ans = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            int idx = k / fact[n - i];
            ans.append(nums.get(idx));
            nums.remove(idx);
            k -= idx * fact[n - i];
        }
        return ans.toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun getPermutation(n: Int, k: Int): String {
        val nums = MutableList(n) { it + 1 }
        val fact = IntArray(n + 1) { 1 }
        for (i in 1..n) fact[i] = fact[i - 1] * i
        var kk = k - 1
        val ans = StringBuilder()
        for (i in 1..n) {
            val idx = kk / fact[n - i]
            ans.append(nums[idx])
            nums.removeAt(idx)
            kk -= idx * fact[n - i]
        }
        return ans.toString()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        nums = [i for i in range(1, n + 1)]
        fact = [1] * (n + 1)
        for i in range(1, n + 1):
            fact[i] = fact[i - 1] * i
        k -= 1
        ans = []
        for i in range(1, n + 1):
            idx = k // fact[n - i]
            ans.append(str(nums[idx]))
            nums.pop(idx)
            k -= idx * fact[n - i]
        return ''.join(ans)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn get_permutation(n: i32, k: i32) -> String {
        let mut nums: Vec<i32> = (1..=n).collect();
        let mut fact = vec![1; (n + 1) as usize];
        for i in 1..=n as usize {
            fact[i] = fact[i - 1] * i as i32;
        }
        let mut kk = k - 1;
        let mut ans = String::new();
        for i in 1..=n {
            let idx = (kk / fact[(n - i) as usize]) as usize;
            ans.push_str(&nums[idx].to_string());
            nums.remove(idx);
            kk -= (idx as i32) * fact[(n - i) as usize];
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    getPermutation(n: number, k: number): string {
        const nums: number[] = [];
        const fact: number[] = [1];
        for (let i = 1; i <= n; i++) {
            nums.push(i);
            fact[i] = fact[i - 1] * i;
        }
        k -= 1;
        let ans = '';
        for (let i = 1; i <= n; i++) {
            const idx = Math.floor(k / fact[n - i]);
            ans += nums[idx].toString();
            nums.splice(idx, 1);
            k -= idx * fact[n - i];
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2) — For each of n positions, we may need to remove an element from a list, which is O(n) in the worst case.
  • 🧺 Space complexity: O(n) — We use arrays/lists to store the numbers and factorials, both of size n.