Problem Overview

You are given two integers n and k.
You need to return the k-th permutation sequence (in lexicographic order) of the numbers [1, 2, 3, ..., n].

Example 1:

Input: n = 3, k = 3
Output: "213"
Explanation:
All permutations of [1,2,3] in order are:
1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"
The 3rd one is "213".

Example 2:

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

Example 3:

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

---

Intuition / Approach

The naive way would be to generate all permutations using backtracking and then pick the k-th one.
However, that approach has O(n! * n) time complexity — infeasible for large n.

Instead, we can directly compute the k-th permutation mathematically using factorials and index calculations.

---

Core Idea

There are n! total permutations for n numbers.
If you fix the first number, there are (n - 1)! permutations for the remaining numbers.

So:

• The first (n - 1)! permutations start with 1
• The next (n - 1)! permutations start with 2
• And so on…

By using factorial grouping, we can determine:

• Which digit should appear first
• Then remove that digit and repeat for the next position

This approach lets us skip entire groups of permutations without generating them.

---

Mathematical Reasoning

1. Start with numbers [1, 2, ..., n]
2. Compute (n - 1)! = number of permutations for each possible starting number.
3. Determine the index of the first number as: index = (k - 1) / (n - 1)! (we subtract 1 because k is 1-based)
4. Pick that number, remove it from the list, and update: k = k - index * (n - 1)!
5. Repeat this for the remaining (n – 1) numbers.

---

Step-by-Step Example

Input: n = 4, k = 9

Step 1:
Numbers = [1, 2, 3, 4]
Factorials: [1, 1, 2, 6, 24]
(We’ll use these to calculate groups.)

Step 2:
Each block of permutations for a starting number = (4 – 1)! = 6

Since k = 9,
index = (k - 1) / 6 = 8 / 6 = 1
So the first digit is numbers[1] = 2.
Remove 2 → numbers = [1, 3, 4]
Update k = 9 - 1*6 = 3.

Step 3:
Now we’re finding the 3rd permutation among [1, 3, 4].
Block size = (3 – 1)! = 2.
index = (3 - 1) / 2 = 1
Pick numbers[1] = 3 → result = “23”
Remove 3 → numbers = [1, 4]
Update k = 3 - 1*2 = 1.

Step 4:
Now we’re finding the 1st permutation of [1, 4].
Block size = (2 – 1)! = 1
index = (1 - 1) / 1 = 0
Pick numbers[0] = 1 → result = “231”
Remove 1 → numbers = [4]
Remaining → result = “2314”

Final Answer: "2314"

---

Algorithm Explanation

1. Compute factorials up to n.
2. Create a list of numbers [1, 2, ..., n].
3. Convert k from 1-based to 0-based by k--.
4. For each position i from n down to 1:
   • Compute index = k / (i - 1)!
   • Append numbers[index] to the result.
   • Remove numbers[index] from the list.
   • Update k = k % (i - 1)!
5. Return the final string.

---

Java Code Implementation

import java.util.*;

public class Solution {
    public String getPermutation(int n, int k) {
        List<Integer> numbers = new ArrayList<>();
        int[] factorial = new int[n + 1];
        factorial[0] = 1;

        // Precompute factorials
        for (int i = 1; i <= n; i++) {
            factorial[i] = factorial[i - 1] * i;
            numbers.add(i);
        }

        k--; // convert to 0-based index
        StringBuilder result = new StringBuilder();

        for (int i = n; i >= 1; i--) {
            int index = k / factorial[i - 1];
            result.append(numbers.get(index));
            numbers.remove(index);
            k = k % factorial[i - 1];
        }

        return result.toString();
    }
}

---

Dry Run Example

Input: n = 3, k = 3

Step	numbers	factorial[i-1]	k	index	pick	result	updated k
1	[1,2,3]	2	2	1	2	“2”	0
2	[1,3]	1	0	0	1	“21”	0
3	[3]	1	0	0	3	“213”	—

Output: "213"

---

Time and Space Complexity

Complexity	Description
Time Complexity	O(n²) — because we remove elements from a list (O(n)) for each of the n positions.
Space Complexity	O(n) — to store factorials and available numbers.

---

Key Takeaways

• Instead of generating permutations, we can mathematically jump to the k-th one.
• Factorial-based grouping helps find which digit to pick at each step.
• This problem is a perfect example of using combinatorial mathematics to reduce complexity from exponential to polynomial.