BackTrackingProblem 19 of 19
Find the K-th Permutation Sequence of first N natural numbers
Problem Statement
Given two integers n and k, find the k-th permutation sequence of numbers from 1 to n. The permutations are numbered in lexicographical order starting from 1.
Example:
Input: n = 3, k = 3
Output: "213"
Explanation:
All permutations of [1,2,3] in order:
1. "123"
2. "132"
3. "213" <- k=3
4. "231"
5. "312"
6. "321"
Input: n = 4, k = 9
Output: "2314"
Approach 1: Brute Force (Generate All Permutations)
Intuition
Generate all permutations using backtracking and return the k-th one. This is inefficient as we generate all permutations.
Algorithm
- Generate permutations using standard backtracking
- Count permutations generated
- Return when count equals k
java
class Solution {
private int count;
private String result;
public void permute(char[] nums, int index, int k) {
if (index == nums.length) {
count++;
if (count == k) {
result = new String(nums);
}
return;
}
for (int i = index; i < nums.length && count < k; i++) {
char temp = nums[index];
nums[index] = nums[i];
nums[i] = temp;
permute(nums, index + 1, k);
temp = nums[index];
nums[index] = nums[i];
nums[i] = temp;
}
}
public String getPermutation(int n, int k) {
char[] nums = new char[n];
for (int i = 0; i < n; i++) {
nums[i] = (char)('1' + i);
}
count = 0;
result = "";
permute(nums, 0, k);
return result;
}
}Complexity Analysis
- Time Complexity: O(n × n!) - Generate up to k permutations
- Space Complexity: O(n) - Recursion stack
Approach 2: Optimal (Mathematical Approach)
Intuition
Use the fact that permutations are grouped by their first digit. With n numbers, fixing the first digit gives (n-1)! permutations. We can directly calculate which digit should be at each position.
Algorithm
- k-th permutation means we skip k-1 permutations
- For first position, (n-1)! permutations start with each digit
- index = (k-1) / (n-1)! gives the digit at first position
- Update k = (k-1) % (n-1)! and repeat for next positions
java
import java.util.*;
class Solution {
public String getPermutation(int n, int k) {
// Calculate factorials
int[] factorial = new int[n + 1];
factorial[0] = 1;
for (int i = 1; i <= n; i++) {
factorial[i] = factorial[i - 1] * i;
}
// Available numbers
List<Integer> numbers = new ArrayList<>();
for (int i = 1; i <= n; i++) {
numbers.add(i);
}
k--; // Convert to 0-indexed
StringBuilder result = new StringBuilder();
for (int i = n; i >= 1; i--) {
// How many permutations per group
int groupSize = factorial[i - 1];
// Which group (0-indexed)
int index = k / groupSize;
// Add the digit at this index
result.append(numbers.get(index));
// Remove used number
numbers.remove(index);
// Update k for next iteration
k = k % groupSize;
}
return result.toString();
}
}Complexity Analysis
- Time Complexity: O(n²) - n iterations, each removal is O(n)
- Space Complexity: O(n) - Factorial array and numbers list
Walkthrough Example
For n = 4, k = 9:
Initial: numbers = [1, 2, 3, 4], k = 8 (0-indexed)
Step 1: i = 4
groupSize = 3! = 6
index = 8 / 6 = 1 → pick numbers[1] = 2
result = "2"
numbers = [1, 3, 4]
k = 8 % 6 = 2
Step 2: i = 3
groupSize = 2! = 2
index = 2 / 2 = 1 → pick numbers[1] = 3
result = "23"
numbers = [1, 4]
k = 2 % 2 = 0
Step 3: i = 2
groupSize = 1! = 1
index = 0 / 1 = 0 → pick numbers[0] = 1
result = "231"
numbers = [4]
k = 0 % 1 = 0
Step 4: i = 1
groupSize = 0! = 1
index = 0 / 1 = 0 → pick numbers[0] = 4
result = "2314"
numbers = []
k = 0 % 1 = 0
Final: "2314"
Using LinkedList for O(n) Total Removal
Key Takeaways
- Factorial Pattern: n! permutations, (n-1)! start with each digit
- 0-indexed k: Convert k to 0-indexed for easier calculation
- Division Pattern: k / groupSize gives index, k % groupSize gives remainder
- Number Removal: Remove used numbers to avoid repetition
- LeetCode #60: Permutation Sequence
- Direct Calculation: No need to generate all permutations