Permutation Sequence solution and explanation
Google
9 more videos on this problem
L18. K-th Permutation Sequence | Leetcodetake U forward · 24:41 · 297K views
Permutation Sequence | Leetcode #60Techdose · 18:17 · 62K views
Permutation Sequence | LeetCode 60 | C++, PythonKnowledge Center · 26:16 · 6K views
permutation sequence | permutation sequence leetcode | leetcode 60 | mediumNaresh Gupta · 14:47 · 2K views
60. Permutation Sequence | Leetcode HARD | Try First, then watch | Easiest solutionJeeetcode · 13:58 · 1K views
Permutation Sequence Python Solution - LeetCode #60Professor Oakes · 6:00 · 1K views
Leetcode Permutation Sequence Java SolutionHackerHeap · 10:31 · 1K views
LeetCode 60. Permutation SequenceHappy Coding · 16:46 · 1K views
Permutation Sequence | Java | LeetCode - Medium - 60 | The Code MateThe Code Mate · 23:02 · 1K views
60. Permutation Sequence || leetcode || medium question || c++ solution and explanationcode Explainer · 3:54 · 960 views
The problem
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!
Approach overview
Problem Overview: Given n and k, return the k-th permutation of the numbers 1..n in lexicographic order. The challenge is to compute the exact permutation without generating all n! possibilities.
Approach 1: Recursive Backtracking (Traditional Approach) (Time: O(n! * n), Space: O(n))
This method generates permutations using classic recursion and backtracking. Start with an empty path and repeatedly pick an unused number from 1..n. Each recursive call adds a number to the permutation until the length reaches n. Every complete permutation is produced in lexicographic order if numbers are explored sequentially. Keep a counter and stop once the k-th permutation is reached. This approach is conceptually simple but extremely inefficient because it explores up to n! permutations even though only one result is required.
Approach 2: Factorial Number System and Decrement Method (Time: O(n^2), Space: O(n))
The optimized solution relies on a math observation about permutation groups. For n digits, each leading digit repeats for (n-1)! permutations. Compute factorial values and determine which block the k-th permutation belongs to. Maintain a list of available numbers. The index of the next digit is (k-1) / (n-1)!. Remove that number from the list, append it to the result, update k with the remainder, and repeat for the remaining digits. This effectively converts k into a factorial number system representation. Because removing elements from a list costs O(n), the overall complexity becomes O(n^2). The technique is a common combinatorics trick and often appears alongside backtracking problems as an optimized alternative.
Recommended for interviews: Interviewers expect the factorial-number-system approach. The brute-force backtracking method shows you understand permutation generation, but the mathematical indexing approach demonstrates stronger algorithmic insight and reduces the search from factorial time to quadratic time.
Approach 1: Factorial Number System and Decrement Method
This approach leverages the factorial number system, where the number of permutations starting with a particular digit can be determined by the factorial of (n-1). We adjust k for zero-based indexing and deduct permutations as we determine each digit sequentially.
def getPermutation(n: int, k: int) -> str:
import math
numbers = list(range(1, n+1))
k -= 1
result = []
for i in range(n, 0, -1):
idx = k // math.factorial(i-1)
result.append(numbers.pop(idx))
k %= math.factorial(i-1)
return ''.join(map(str, result))
n = 3
k = 3
print(getPermutation(n, k))import java.util.ArrayList;
public class Main {
public static String getPermutation(int n, int k) {
int[] factorial = new int[n];
ArrayList<Integer> numbers = new ArrayList<>();
factorial[0] = 1;
for (int i = 1; i < n; i++)
factorial[i] = factorial[i - 1] * i;
for (int i = 1; i <= n; i++)
numbers.add(i);
StringBuilder result = new StringBuilder();
k--;
for (int i = n; i >= 1; i--) {
int index = k / factorial[i - 1];
result.append(numbers.get(index));
numbers.remove(index);
k %= factorial[i - 1];
}
return result.toString();
}
public static void main(String[] args) {
int n = 3, k = 3;
System.out.println(getPermutation(n, k));
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
string getPermutation(int n, int k) {
vector<int> factorial(n, 1);
vector<int> numbers;
for (int i = 1; i < n; i++)
factorial[i] = factorial[i - 1] * i;
for (int i = 1; i <= n; i++)
numbers.push_back(i);
string result;
k--;
for (int i = n; i >= 1; i--) {
int index = k / factorial[i - 1];
result += to_string(numbers[index]);
numbers.erase(numbers.begin() + index);
k %= factorial[i - 1];
}
return result;
}
int main() {
int n = 3, k = 3;
cout << getPermutation(n, k) << endl;
return 0;
}function getPermutation(n, k) {
let numbers = Array.from({length: n}, (_, i) => i + 1);
let factorial = [1];
for (let i = 1; i < n; i++)
factorial[i] = factorial[i - 1] * i;
k--;
let result = '';
for (let i = n; i > 0; i--) {
let index = Math.floor(k / factorial[i - 1]);
result += numbers[index];
numbers.splice(index, 1);
k %= factorial[i - 1];
}
return result;
}
const n = 3, k = 3;
console.log(getPermutation(n, k));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void getPermutation(int n, int k, char *result) {
int *factorial = malloc((n + 1) * sizeof(int));
int *numbers = malloc(n * sizeof(int));
factorial[0] = 1;
for (int i = 1; i <= n; i++)
factorial[i] = i * factorial[i - 1];
for (int i = 0; i < n; i++)
numbers[i] = i + 1;
k--;
for (int i = 0; i < n; i++) {
int index = k / factorial[n - 1 - i];
result[i] = '0' + numbers[index];
for (int j = index; j < n - 1; j++)
numbers[j] = numbers[j + 1];
k %= factorial[n - 1 - i];
}
result[n] = '\0';
free(factorial);
free(numbers);
}
int main() {
int n = 3, k = 3;
char result[10];
getPermutation(n, k, result);
printf("%s\n", result);
return 0;
}using System;
using System.Collections.Generic;
class Program {
public static string GetPermutation(int n, int k) {
List<int> numbers = new List<int>();
int[] factorial = new int[n];
factorial[0] = 1;
for (int i = 1; i < n; i++)
factorial[i] = factorial[i - 1] * i;
for (int i = 1; i <= n; i++)
numbers.Add(i);
k--;
string result = "";
for (int i = n; i > 0; i--) {
int index = k / factorial[i - 1];
result += numbers[index].ToString();
numbers.RemoveAt(index);
k %= factorial[i - 1];
}
return result;
}
static void Main() {
int n = 3, k = 3;
Console.WriteLine(GetPermutation(n, k));
}
}This Python implementation utilizes math.factorial to handle factorial calculations. It efficiently builds the permutation using list manipulation to determine which element should appear in each position.
Time Complexity: O(n^2) because of list pop operation.
Space Complexity: O(n) due to the list of numbers.
Approach 2: Recursive Backtracking (Traditional Approach)
This approach generates permutations using a traditional backtracking method, with the goal of finding the k-th permutation without necessarily generating all permutations explicitly.
import itertools
def getPermutation(n, k):
numbers = list(range(1, n + 1))
perms_gen = itertools.permutations(numbers)
result = next(itertools.islice(perms_gen, k - 1, None))
return ''.join(map(str, result))
n = 3
k = 3
print(getPermutation(n, k))import java.util.Arrays;
public class Main {
public static String getPermutation(int n, int k) {
int count = 0;
char[] numbers = new char[n];
for (int i = 0; i < n; i++)
numbers[i] = (char)('1' + i);
Arrays.sort(numbers);
StringBuilder result = new StringBuilder();
do {
count++;
if (count == k) {
result = new StringBuilder(new String(numbers));
break;
}
} while (nextPermutation(numbers));
return result.toString();
}
private static boolean nextPermutation(char[] array) {
int i = array.length - 2;
while (i >= 0 && array[i] >= array[i + 1]) i--;
if (i == -1) return false;
int j = array.length - 1;
while (array[j] <= array[i]) j--;
swap(array, i, j);
reverse(array, i + 1, array.length - 1);
return true;
}
private static void swap(char[] array, int i, int j) {
char temp = array[i];
array[i] = array[j];
array[j] = temp;
}
private static void reverse(char[] array, int i, int j) {
while (i < j) swap(array, i++, j--);
}
public static void main(String[] args) {
int n = 3, k = 3;
System.out.println(getPermutation(n, k));
}
}#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
string getPermutation(int n, int k) {
string numbers;
for (int i = 1; i <= n; i++)
numbers += to_string(i);
string result;
do {
k--;
if (k == 0) {
result = numbers;
break;
}
} while (next_permutation(numbers.begin(), numbers.end()));
return result;
}
int main() {
int n = 3, k = 3;
cout << getPermutation(n, k) << endl;
return 0;
}function getPermutation(n, k) {
let nums = Array.from({ length: n }, (_, i) => i + 1);
let permCount = 0;
let found = '';
function permute(arr, m = []) {
if (arr.length == 0) {
permCount++;
if (permCount == k) {
found = m.join('');
}
}
if (found) return;
for (let i = 0; i < arr.length; i++) {
let curr = arr.slice();
let next = curr.splice(i, 1);
permute(curr.slice(), m.concat(next));
if (found) return;
}
}
permute(nums);
return found;
}
let n = 3, k = 3;
console.log(getPermutation(n, k));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void swap(char *a, char *b) {
char temp = *a;
*a = *b;
*b = temp;
}
int count = 0;
char *perm = NULL;
void permute(char *str, int start, int end, int k) {
if (start == end) {
count++;
if (count == k) {
strcpy(perm, str);
}
} else {
for (int i = start; i <= end; i++) {
swap((str + start), (str + i));
permute(str, start + 1, end, k);
swap((str + start), (str + i));
}
}
}
char *getPermutation(int n, int k) {
char *numbers = malloc((n + 1) * sizeof(char));
for (int i = 0; i < n; i++)
numbers[i] = '1' + i;
numbers[n] = '\0';
perm = malloc((n + 1) * sizeof(char));
permute(numbers, 0, n - 1, k);
free(numbers);
return perm;
}
int main() {
int n = 3, k = 3;
char *result = getPermutation(n, k);
printf("%s\n", result);
free(result);
return 0;
}using System;
using System.Collections.Generic;
class Program {
static string GetPermutation(int n, int k) {
var numbers = new List<int>();
for (int i = 1; i <= n; i++) numbers.Add(i);
int count = 0;
string permutation = string.Empty;
RecursePermute(numbers, k, ref count, ref permutation);
return permutation;
}
static void RecursePermute(List<int> numbers, int k, ref int count, ref string permutation) {
if (numbers.Count == 0 && ++count == k) return;
for (int i = 0; i < numbers.Count; i++) {
int current = numbers[i];
numbers.RemoveAt(i);
permutation += current.ToString();
RecursePermute(numbers, k, ref count, ref permutation);
if (count == k) return;
permutation = permutation.Substring(0, permutation.Length - 1);
numbers.Insert(i, current);
}
}
static void Main() {
int n = 3, k = 3;
Console.WriteLine(GetPermutation(n, k));
}
}This Python solution makes use of itertools.permutations to dynamically produce permutations, leveraging itertools.islice to directly arrive at the k-th permutation.
Time Complexity: O(n!) from iteration over the permutations.
Space Complexity: O(n), storing the sequence in memory.
Approach 3: Enumeration
We know that the set [1,2,..n] has a total of n! permutations. If we determine the first digit, the number of permutations that the remaining digits can form is (n-1)!.
Therefore, we enumerate each digit i. If k is greater than the number of permutations after the current position is determined, then we can directly subtract this number; otherwise, it means that we have found the number at the current position.
For each digit i, where 0 leq i < n, the number of permutations that the remaining digits can form is (n-i-1)!, which we denote as fact. The numbers used in the process are recorded in vis.
The time complexity is O(n^2), and the space complexity is O(n).
function getPermutation(n: number, k: number): string {
let ans = '';
const vis = Array.from({ length: n + 1 }, () => false);
for (let i = 0; i < n; i++) {
let fact = 1;
for (let j = 1; j < n - i; j++) {
fact *= j;
}
for (let j = 1; j <= n; j++) {
if (!vis[j]) {
if (k > fact) {
k -= fact;
} else {
ans += j;
vis[j] = true;
break;
}
}
}
}
return ans;
}func getPermutation(n int, k int) string {
ans := make([]byte, n)
vis := make([]bool, n+1)
for i := 0; i < n; i++ {
fact := 1
for j := 1; j < n-i; j++ {
fact *= j
}
for j := 1; j <= n; j++ {
if !vis[j] {
if k > fact {
k -= fact
} else {
ans[i] = byte('0' + j)
vis[j] = true
break
}
}
}
}
return string(ans)
}impl Solution {
pub fn get_permutation(n: i32, k: i32) -> String {
let mut k = k;
let mut ans = String::new();
let mut fact = vec![1; n as usize];
for i in 1..n as usize {
fact[i] = fact[i - 1] * (i as i32);
}
let mut vis = vec![false; n as usize + 1];
for i in 0..n as usize {
let cnt = fact[(n as usize) - i - 1];
for j in 1..=n {
if vis[j as usize] {
continue;
}
if k > cnt {
k -= cnt;
} else {
ans.push_str(&j.to_string());
vis[j as usize] = true;
break;
}
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Factorial Number System and Decrement Method | Time Complexity: O(n^2) because of list pop operation. Space Complexity: O(n) due to the list of numbers. |
| Recursive Backtracking (Traditional Approach) | Time Complexity: O(n!) from iteration over the permutations. Space Complexity: O(n), storing the sequence in memory. |
| Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Backtracking (Traditional) | O(n! * n) | O(n) | Useful for understanding permutation generation or when all permutations are required. |
| Factorial Number System and Decrement Method | O(n^2) | O(n) | Best choice when only the k-th permutation is needed without generating all permutations. |
Frequently asked questions
Is Permutation Sequence easy or hard?
Permutation Sequence is classified as a Hard problem because it requires recognizing the factorial-number-system pattern. The implementation itself is manageable, but the key insight about permutation grouping makes it challenging.
Permutation Sequence Python/Java solution
Most Python and Java solutions implement the factorial number system method. They precompute factorials, store numbers 1..n in a list, convert k-1 into factorial-base digits, and iteratively pick and remove elements to build the permutation.
How to solve Permutation Sequence in O(n)?
Pure O(n) time is difficult with a simple list because removing elements costs O(n). The common implementation achieves O(n^2). With advanced data structures like a balanced tree or Fenwick tree for k-th order statistics, the complexity can approach O(n log n).
What is the best approach for Permutation Sequence?
The factorial number system approach is the most efficient. Instead of generating all n! permutations, it determines each digit of the k-th permutation using factorial group sizes. This reduces the complexity to O(n^2) time and O(n) space.
Is Permutation Sequence asked at Google/Amazon/Meta?
Permutation and combinatorics problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that involve permutation indexing, ranking, or factorial number systems are common in algorithm rounds.
What data structure is used in Permutation Sequence?
The optimized solution uses an array or list to store remaining digits and a factorial array for quick block-size calculations. Each step selects the correct index and removes that element from the list.
What is the time complexity of Permutation Sequence?
The optimal factorial-based method runs in O(n^2) time because each step removes one element from a list of remaining numbers. The brute-force recursive backtracking approach generates all permutations and costs O(n! * n).