Permutation Sequence
HardPrompt
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:
"123""132""213""231""312""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 <= 91 <= k <= n!
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves generating all possible permutations of the numbers from 1 to n. We can use a recursive backtracking algorithm to find every permutation. As we generate them, we store them in a list. Since the standard backtracking approach of picking the smallest available number first generates permutations in lexicographical order, the k-th permutation will be the element at index k-1 in our list.
Algorithm
- Create a list to store the resulting permutations.
- Implement a recursive helper function, say
backtrack(current_permutation, remaining_numbers). - The base case for the recursion is when
remaining_numbersis empty. At this point, a full permutation has been formed, so we add it to our list of permutations. - In the recursive step, iterate through the
remaining_numbers. For each number, add it to thecurrent_permutation, remove it fromremaining_numbers, and make a recursive call. - After the recursive call returns, backtrack by removing the number from
current_permutationand adding it back toremaining_numbersto explore other possibilities. - The initial call will be with an empty permutation and a list of numbers from 1 to
n. - After the recursion completes, the list will contain all
n!permutations in order. Return the string at indexk-1.
Walkthrough
class Solution { public String getPermutation(int n, int k) { List<String> permutations = new ArrayList<>(); boolean[] used = new boolean[n + 1]; generatePermutations(new StringBuilder(), n, permutations, used); return permutations.get(k - 1); } private void generatePermutations(StringBuilder current, int n, List<String> result, boolean[] used) { if (current.length() == n) { result.add(current.toString()); return; } for (int i = 1; i <= n; i++) { if (!used[i]) { used[i] = true; current.append(i); generatePermutations(current, n, result, used); // Backtrack current.deleteCharAt(current.length() - 1); used[i] = false; } } }}Complexity
Time
O(n * n!)
Space
O(n * n!)
Trade-offs
Pros
Simple to understand if you are familiar with backtracking.
Cons
Extremely inefficient for larger
n(even forn=9,9!is large).It will likely result in a "Time Limit Exceeded" or "Memory Limit Exceeded" error on most platforms.
This method avoids generating all permutations at once. Instead, it starts with the first permutation (which is "123...n") and then iteratively finds the next lexicographical permutation k-1 times.
Algorithm
- Create the first permutation by concatenating numbers from 1 to
n. - Loop
k-1times. In each iteration, find the next lexicographical permutation of the current one. - The algorithm to find the next permutation is as follows:
a. Find the largest index
isuch thatperm[i] < perm[i+1]. If no such index exists, this is the last permutation. b. Find the largest indexj > isuch thatperm[i] < perm[j]. c. Swap the elements atiandj. d. Reverse the sub-array from indexi+1to the end. - After the loop finishes, the current permutation is the
k-th one.
Walkthrough
class Solution { public String getPermutation(int n, int k) { int[] nums = new int[n]; for (int i = 0; i < n; i++) { nums[i] = i + 1; } for (int i = 1; i < k; i++) { nextPermutation(nums); } StringBuilder sb = new StringBuilder(); for (int num : nums) { sb.append(num); } return sb.toString(); } private void nextPermutation(int[] nums) { int i = nums.length - 2; while (i >= 0 && nums[i] >= nums[i + 1]) { i--; } if (i >= 0) { int j = nums.length - 1; while (nums[j] <= nums[i]) { j--; } swap(nums, i, j); } reverse(nums, i + 1); } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } private void reverse(int[] nums, int start) { int i = start, j = nums.length - 1; while (i < j) { swap(nums, i, j); i++; j--; } }}Complexity
Time
O(k * n)
Space
O(n)
Trade-offs
Pros
More space-efficient than the full backtracking approach.
Faster if
kis small.
Cons
Still too slow if
kis large, leading to a "Time Limit Exceeded" error.
This is the most efficient approach. It mathematically constructs the k-th permutation directly without generating any other permutations. The idea is to determine each digit of the permutation one by one, from left to right. For n numbers, there are n! permutations. These can be divided into n blocks, where each block consists of (n-1)! permutations that start with the same number. By using k and the size of these blocks, we can determine which block the k-th permutation falls into, and thus determine the first digit of our result. We then update k to be the index within that block and repeat the process for the remaining numbers.
Algorithm
- Create a list of available numbers,
[1, 2, ..., n]. - Pre-compute factorials up to
(n-1)!. - Adjust
kto be 0-indexed by subtracting 1 (k--). This simplifies index calculations. - Iterate from
ndown to 1. In each stepi: a. Calculate the size of the permutation blocks for the remainingi-1numbers:blockSize = (i-1)!. b. The index of the number to pick from the current list of available numbers isindex = k / blockSize. c. Append the number atindexto the result. d. Remove that number from the list of available numbers. e. Updatekfor the next iteration:k = k % blockSize. - Return the constructed permutation string.
Walkthrough
class Solution { public String getPermutation(int n, int k) { List<Integer> numbers = new ArrayList<>(); int[] factorial = new int[n + 1]; StringBuilder sb = new StringBuilder(); // Create a list of numbers to get indices for (int i = 1; i <= n; i++) { numbers.add(i); } // Pre-compute factorials factorial[0] = 1; for (int i = 1; i <= n; i++) { // Note: n! can be large, but for n<=9, it fits in an int factorial[i] = factorial[i - 1] * i; } // Adjust k to be 0-indexed k--; for (int i = n; i >= 1; i--) { int blockSize = factorial[i - 1]; int index = k / blockSize; sb.append(numbers.get(index)); numbers.remove(index); k = k % blockSize; } return sb.toString(); }}Complexity
Time
O(n^2)
Space
O(n)
Trade-offs
Pros
Very efficient and guaranteed to pass within the time limits for the given constraints.
Directly calculates the result without unnecessary computations.
Cons
The logic is less intuitive than brute-force and requires understanding the mathematical properties of permutations.
Solutions
Solution
public class Solution { public string GetPermutation ( int n , int k ) { var ans = new StringBuilder (); int vis = 0 ; for ( int i = 0 ; i < n ; ++ i ) { int fact = 1 ; for ( int j = 1 ; j < n - i ; ++ j ) { fact *= j ; } for ( int j = 1 ; j <= n ; ++ j ) { if ((( vis >> j ) & 1 ) == 0 ) { if ( k > fact ) { k -= fact ; } else { ans . Append ( j ); vis |= 1 << j ; break ; } } } } return ans . ToString (); } }class Solution { public String getPermutation ( int n , int k ) { StringBuilder ans = new StringBuilder (); boolean [] vis = new boolean [ n + 1 ]; for ( int i = 0 ; i < n ; ++ i ) { int fact = 1 ; for ( int j = 1 ; j < n - i ; ++ j ) { fact *= j ; } for ( int j = 1 ; j <= n ; ++ j ) { if (! vis [ j ]) { if ( k > fact ) { k -= fact ; } else { ans . append ( j ); vis [ j ] = true ; break ; } } } } return ans . toString (); } }class Solution { public: string getPermutation ( int n , int k ) { string ans ; bitset < 10 > vis ; for ( int i = 0 ; i < n ; ++ i ) { int fact = 1 ; for ( int j = 1 ; j < n - i ; ++ j ) fact *= j ; for ( int j = 1 ; j <= n ; ++ j ) { if ( vis [ j ]) continue ; if ( k > fact ) k -= fact ; else { ans += to_string ( j ); vis [ j ] = 1 ; break ; } } } return ans ; } };class Solution : def getPermutation ( self , n : int , k : int ) -> str : nums = list ( range ( 1 , n + 1 )) factorial = [ 1 ] * ( n + 1 ) for i in range ( 1 , n + 1 ): factorial [ i ] = factorial [ i - 1 ] * i result = [] k -= 1 for i in range ( n , 0 , - 1 ): digit = k // factorial [ i - 1 ] result . append ( str ( nums [ digit ])) nums . pop ( digit ) k %= factorial [ i - 1 ] return '' . join ( result ) ########## class Solution : def getPermutation ( self , n : int , k : int ) -> str : ans = [] vis = [ False ] * ( n + 1 ) for i in range ( n ): fact = 1 for j in range ( 1 , n - i ): fact *= j for j in range ( 1 , n + 1 ): if not vis [ j ]: if k > fact : k -= fact else : ans . append ( str ( j )) vis [ j ] = True break return '' . join ( ans )Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.