Permutation Sequence (Kth)

🎯

Permutation Sequence (Kth)

hardBACKTRACKINGAmazonGoogleFacebook

Imagine you have a list of tasks to perform in every possible order, but you want to quickly jump to the k-th order without enumerating all permutations.

💡 This problem asks for the k-th permutation sequence of numbers from 1 to n. Beginners often struggle because generating all permutations is expensive and unnecessary. Understanding how to directly compute the k-th permutation using factorial math is key.

📋

Problem Statement

Given n and k, return the k-th permutation sequence of the numbers [1, 2, ..., n] in lexicographical order. Input: two integers n and k. Output: a string representing the k-th permutation.

1 ≤ n ≤ 91 ≤ k ≤ n!

💡

Example

Input"n = 3, k = 3"

Output"213"

The permutations of [1,2,3] in order are: 123, 132, 213, 231, 312, 321. The 3rd is '213'.

• n = 1, k = 1 → output '1' (smallest input)
• k = 1 → output is the first permutation in ascending order
• k = n! → output is the last permutation in descending order
• n = 9, k = 362880 (9!) → largest input within constraints

⚠️

Common Mistakes

Forgetting to convert k to zero-based index

Incorrect index calculation leads to wrong permutation

✅ Always do k = k - 1 before calculations

Not removing used numbers from the list

Repeated numbers appear in the result

✅ Remove the selected number from the available list after choosing

Using factorial values incorrectly or not precomputing

Wrong index calculation or inefficient repeated factorial computation

✅ Precompute factorials once before main loop

Trying to generate all permutations for large n

Solution times out or crashes due to memory/time limits

✅ Use direct computation approach instead of brute force

Not handling edge cases like k=1 or k=n!

Incorrect output or runtime errors

✅ Test and handle boundary cases explicitly if needed

🧠

Brute Force (Generate All Permutations)

💡 This approach exists to build intuition by enumerating all permutations and picking the k-th. It is straightforward but inefficient, illustrating why direct computation is needed.

Intuition

Generate all permutations of [1..n] in lex order using backtracking, then return the k-th one.

Algorithm

1. Initialize a list to store all permutations.
2. Use backtracking to generate all permutations of [1..n].
3. Stop when the k-th permutation is generated.
4. Return the k-th permutation as a string.

💡 The challenge is understanding how backtracking generates permutations and why this approach is too slow for large n.

</>

Code

def getPermutation(n, k):
    res = []
    used = [False] * n
    path = []
    def backtrack():
        if len(path) == n:
            res.append(''.join(map(str, path)))
            return
        for i in range(n):
            if not used[i]:
                used[i] = True
                path.append(i + 1)
                backtrack()
                path.pop()
                used[i] = False
    backtrack()
    return res[k - 1]

# Driver code
if __name__ == '__main__':
    print(getPermutation(3, 3))  # Output: '213'

Line Notes

res = []Stores all permutations generated so far

used = [False] * nTracks which numbers are already in the current permutation path

def backtrack():Defines the recursive function to build permutations

if len(path) == n:Base case: a full permutation is formed

res.append(''.join(map(str, path)))Add the current permutation as a string to results

for i in range(n):Try each number from 1 to n if not used

used[i] = TrueMark number as used before recursion

path.append(i + 1)Add number to current permutation path

backtrack()Recurse to build deeper permutations

path.pop()Backtrack by removing last number

used[i] = FalseMark number as unused for other branches

return res[k - 1]Return the k-th permutation from the list

import java.util.*;
public class Solution {
    List<String> res = new ArrayList<>();
    boolean[] used;
    int n;
    public String getPermutation(int n, int k) {
        this.n = n;
        used = new boolean[n];
        backtrack(new StringBuilder());
        return res.get(k - 1);
    }
    private void backtrack(StringBuilder path) {
        if (path.length() == n) {
            res.add(path.toString());
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                used[i] = true;
                path.append(i + 1);
                backtrack(path);
                path.deleteCharAt(path.length() - 1);
                used[i] = false;
            }
        }
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.getPermutation(3, 3)); // Output: 213
    }
}

Line Notes

List<String> res = new ArrayList<>()Stores all permutations generated

boolean[] usedTracks which numbers are used in current path

backtrack(new StringBuilder())Starts recursion with empty path

if (path.length() == n)Base case: full permutation formed

res.add(path.toString())Add current permutation to results

for (int i = 0; i < n; i++)Try each number from 1 to n

used[i] = trueMark number as used before recursion

path.append(i + 1)Add number to current path

backtrack(path)Recurse deeper

path.deleteCharAt(path.length() - 1)Backtrack by removing last number

used[i] = falseMark number as unused for other branches

return res.get(k - 1)Return the k-th permutation

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    vector<string> res;
    vector<bool> used;
    int n;
    void backtrack(string &path) {
        if ((int)path.size() == n) {
            res.push_back(path);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                used[i] = true;
                path.push_back('1' + i);
                backtrack(path);
                path.pop_back();
                used[i] = false;
            }
        }
    }
    string getPermutation(int n, int k) {
        this->n = n;
        used.assign(n, false);
        string path = "";
        backtrack(path);
        return res[k - 1];
    }
};

int main() {
    Solution sol;
    cout << sol.getPermutation(3, 3) << endl; // Output: 213
    return 0;
}

Line Notes

vector<string> resStores all generated permutations

vector<bool> usedTracks usage of numbers in current permutation

void backtrack(string &path)Recursive function to build permutations

if ((int)path.size() == n)Base case: full permutation formed

res.push_back(path)Add current permutation to results

for (int i = 0; i < n; i++)Try each number from 1 to n

used[i] = trueMark number as used before recursion

path.push_back('1' + i)Add number to current path

backtrack(path)Recurse deeper

path.pop_back()Backtrack by removing last number

used[i] = falseMark number as unused for other branches

return res[k - 1]Return the k-th permutation

function getPermutation(n, k) {
    const res = [];
    const used = new Array(n).fill(false);
    const path = [];
    function backtrack() {
        if (path.length === n) {
            res.push(path.join(''));
            return;
        }
        for (let i = 0; i < n; i++) {
            if (!used[i]) {
                used[i] = true;
                path.push(i + 1);
                backtrack();
                path.pop();
                used[i] = false;
            }
        }
    }
    backtrack();
    return res[k - 1];
}

// Test
console.log(getPermutation(3, 3)); // Output: 213

Line Notes

const res = []Stores all permutations generated

const used = new Array(n).fill(false)Tracks which numbers are used in current path

function backtrack()Recursive function to build permutations

if (path.length === n)Base case: full permutation formed

res.push(path.join(''))Add current permutation as string to results

for (let i = 0; i < n; i++)Try each number from 1 to n

used[i] = trueMark number as used before recursion

path.push(i + 1)Add number to current path

backtrack()Recurse deeper

path.pop()Backtrack by removing last number

used[i] = falseMark number as unused for other branches

return res[k - 1]Return the k-th permutation

⏱

Complexity

TimeO(n! * n)

SpaceO(n! * n)

Generating all permutations takes n! time and each permutation is length n, so total O(n! * n).

💡 For n=9, n! is 362,880, which is huge and impractical to generate fully.

Interview Verdict: TLE

This approach times out for larger n because it generates all permutations instead of directly computing the k-th.

🧠

Backtracking with Early Stop

💡 This approach improves brute force by stopping recursion once the k-th permutation is found, saving some time but still not efficient enough for large n.

Intuition

Generate permutations in lex order, but stop recursion as soon as the k-th permutation is reached.

Algorithm

1. Initialize a global counter to track how many permutations have been generated.
2. Use backtracking to generate permutations in lex order.
3. When the counter reaches k, record the current permutation and stop recursion.
4. Return the recorded permutation.

💡 The key difficulty is managing the global count and stopping recursion early to save time.

</>

Code

def getPermutation(n, k):
    used = [False] * n
    path = []
    count = [0]
    result = ['']
    def backtrack():
        if len(path) == n:
            count[0] += 1
            if count[0] == k:
                result[0] = ''.join(map(str, path))
            return
        if result[0]:
            return
        for i in range(n):
            if not used[i]:
                used[i] = True
                path.append(i + 1)
                backtrack()
                path.pop()
                used[i] = False
    backtrack()
    return result[0]

# Driver code
if __name__ == '__main__':
    print(getPermutation(3, 3))  # Output: '213'

Line Notes

count = [0]Tracks how many permutations have been generated so far

result = ['']Stores the k-th permutation once found

if len(path) == n:Base case: full permutation formed

count[0] += 1Increment count when a permutation is completed

if count[0] == k:Check if current permutation is the k-th

result[0] = ''.join(map(str, path))Save the k-th permutation

if result[0]:Stop recursion early if k-th permutation found

for i in range(n):Try each number from 1 to n

used[i] = TrueMark number as used

path.append(i + 1)Add number to current path

backtrack()Recurse deeper

path.pop()Backtrack by removing last number

used[i] = FalseMark number as unused

import java.util.*;
public class Solution {
    List<String> res = new ArrayList<>();
    boolean[] used;
    int n, count = 0;
    String result = "";
    public String getPermutation(int n, int k) {
        this.n = n;
        used = new boolean[n];
        backtrack(new StringBuilder(), k);
        return result;
    }
    private void backtrack(StringBuilder path, int k) {
        if (path.length() == n) {
            count++;
            if (count == k) {
                result = path.toString();
            }
            return;
        }
        if (!result.isEmpty()) return;
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                used[i] = true;
                path.append(i + 1);
                backtrack(path, k);
                path.deleteCharAt(path.length() - 1);
                used[i] = false;
            }
        }
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.getPermutation(3, 3)); // Output: 213
    }
}

Line Notes

int count = 0Tracks how many permutations generated

String result = ""Stores the k-th permutation once found

if (path.length() == n)Base case: full permutation formed

count++Increment count when a permutation is completed

if (count == k)Check if current permutation is the k-th

result = path.toString()Save the k-th permutation

if (!result.isEmpty()) returnStop recursion early if k-th permutation found

for (int i = 0; i < n; i++)Try each number from 1 to n

used[i] = trueMark number as used

path.append(i + 1)Add number to current path

backtrack(path, k)Recurse deeper

path.deleteCharAt(path.length() - 1)Backtrack by removing last number

used[i] = falseMark number as unused

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    vector<bool> used;
    int n, count = 0;
    string result = "";
    void backtrack(string &path, int k) {
        if ((int)path.size() == n) {
            count++;
            if (count == k) {
                result = path;
            }
            return;
        }
        if (!result.empty()) return;
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                used[i] = true;
                path.push_back('1' + i);
                backtrack(path, k);
                path.pop_back();
                used[i] = false;
            }
        }
    }
    string getPermutation(int n, int k) {
        this->n = n;
        used.assign(n, false);
        string path = "";
        backtrack(path, k);
        return result;
    }
};

int main() {
    Solution sol;
    cout << sol.getPermutation(3, 3) << endl; // Output: 213
    return 0;
}

Line Notes

int count = 0Tracks how many permutations generated

string result = ""Stores the k-th permutation once found

if ((int)path.size() == n)Base case: full permutation formed

count++Increment count when a permutation is completed

if (count == k)Check if current permutation is the k-th

result = pathSave the k-th permutation

if (!result.empty()) returnStop recursion early if k-th permutation found

for (int i = 0; i < n; i++)Try each number from 1 to n

used[i] = trueMark number as used

path.push_back('1' + i)Add number to current path

backtrack(path, k)Recurse deeper

path.pop_back()Backtrack by removing last number

used[i] = falseMark number as unused

function getPermutation(n, k) {
    const used = new Array(n).fill(false);
    const path = [];
    let count = 0;
    let result = '';
    function backtrack() {
        if (path.length === n) {
            count++;
            if (count === k) {
                result = path.join('');
            }
            return;
        }
        if (result) return;
        for (let i = 0; i < n; i++) {
            if (!used[i]) {
                used[i] = true;
                path.push(i + 1);
                backtrack();
                path.pop();
                used[i] = false;
            }
        }
    }
    backtrack();
    return result;
}

// Test
console.log(getPermutation(3, 3)); // Output: 213

Line Notes

let count = 0Tracks how many permutations generated

let result = ''Stores the k-th permutation once found

if (path.length === n)Base case: full permutation formed

count++Increment count when a permutation is completed

if (count === k)Check if current permutation is the k-th

result = path.join('')Save the k-th permutation

if (result) returnStop recursion early if k-th permutation found

for (let i = 0; i < n; i++)Try each number from 1 to n

used[i] = trueMark number as used

path.push(i + 1)Add number to current path

backtrack()Recurse deeper

path.pop()Backtrack by removing last number

used[i] = falseMark number as unused

⏱

Complexity

TimeO(k * n)

SpaceO(n)

In worst case, we generate up to k permutations, each of length n, so O(k * n).

💡 If k is large (close to n!), this is still very slow and impractical.

Interview Verdict: TLE for large k

Early stopping helps but still too slow for large inputs; motivates direct computation.

🧠

Optimal Direct Computation Using Factorial Number System

💡 This approach uses math to directly compute the k-th permutation without generating all permutations, making it efficient and scalable.

Intuition

Each position in the permutation can be determined by dividing k by factorials of remaining digits, selecting the appropriate number from the unused list.

Algorithm

1. Precompute factorials from 0! to (n-1)!.
2. Create a list of numbers from 1 to n.
3. Adjust k to zero-based index (k = k - 1).
4. For each position, determine the index by dividing k by factorial of remaining positions.
5. Append the number at that index to the result and remove it from the list.
6. Update k to k modulo factorial of remaining positions.
7. Return the concatenated result string.

💡 The key insight is mapping k to indices using factorial blocks, which avoids generating permutations.

</>

Code

def getPermutation(n, k):
    factorial = [1] * n
    for i in range(1, n):
        factorial[i] = factorial[i - 1] * i
    numbers = list(range(1, n + 1))
    k -= 1  # zero-based index
    result = []
    for i in range(n - 1, -1, -1):
        idx = k // factorial[i]
        k %= factorial[i]
        result.append(str(numbers[idx]))
        numbers.pop(idx)
    return ''.join(result)

# Driver code
if __name__ == '__main__':
    print(getPermutation(3, 3))  # Output: '213'

Line Notes

factorial = [1] * nInitialize factorial array to store factorials up to (n-1)!

for i in range(1, n)Compute factorial values iteratively

numbers = list(range(1, n + 1))List of available numbers to pick from

k -= 1Convert k to zero-based index for calculation

for i in range(n - 1, -1, -1)Iterate from highest factorial to lowest

idx = k // factorial[i]Determine index of number to pick based on k

k %= factorial[i]Update k to remainder for next iteration

result.append(str(numbers[idx]))Add selected number to result

numbers.pop(idx)Remove used number from list

import java.util.*;
public class Solution {
    public String getPermutation(int n, int k) {
        int[] factorial = new int[n];
        factorial[0] = 1;
        for (int i = 1; i < n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }
        List<Integer> numbers = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            numbers.add(i);
        }
        k--;
        StringBuilder result = new StringBuilder();
        for (int i = n - 1; i >= 0; i--) {
            int idx = k / factorial[i];
            k %= factorial[i];
            result.append(numbers.get(idx));
            numbers.remove(idx);
        }
        return result.toString();
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.getPermutation(3, 3)); // Output: 213
    }
}

Line Notes

int[] factorial = new int[n]Array to store factorials up to (n-1)!

for (int i = 1; i < n; i++)Compute factorial values iteratively

List<Integer> numbers = new ArrayList<>()List of available numbers to pick from

k--Convert k to zero-based index

for (int i = n - 1; i >= 0; i--)Iterate from highest factorial to lowest

int idx = k / factorial[i]Determine index of number to pick

k %= factorial[i]Update k for next iteration

result.append(numbers.get(idx))Add selected number to result

numbers.remove(idx)Remove used number from list

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> factorial(n, 1);
        for (int i = 1; i < n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }
        vector<int> numbers;
        for (int i = 1; i <= n; i++) {
            numbers.push_back(i);
        }
        k--;
        string result;
        for (int i = n - 1; i >= 0; i--) {
            int idx = k / factorial[i];
            k %= factorial[i];
            result += to_string(numbers[idx]);
            numbers.erase(numbers.begin() + idx);
        }
        return result;
    }
};

int main() {
    Solution sol;
    cout << sol.getPermutation(3, 3) << endl; // Output: 213
    return 0;
}

Line Notes

vector<int> factorial(n, 1)Stores factorials up to (n-1)!

for (int i = 1; i < n; i++)Compute factorial values iteratively

vector<int> numbersList of available numbers to pick from

k--Convert k to zero-based index

for (int i = n - 1; i >= 0; i--)Iterate from highest factorial to lowest

int idx = k / factorial[i]Determine index of number to pick

k %= factorial[i]Update k for next iteration

result += to_string(numbers[idx])Add selected number to result

numbers.erase(numbers.begin() + idx)Remove used number from list

function getPermutation(n, k) {
    const factorial = new Array(n).fill(1);
    for (let i = 1; i < n; i++) {
        factorial[i] = factorial[i - 1] * i;
    }
    const numbers = [];
    for (let i = 1; i <= n; i++) {
        numbers.push(i);
    }
    k--;
    let result = '';
    for (let i = n - 1; i >= 0; i--) {
        const idx = Math.floor(k / factorial[i]);
        k %= factorial[i];
        result += numbers[idx];
        numbers.splice(idx, 1);
    }
    return result;
}

// Test
console.log(getPermutation(3, 3)); // Output: 213

Line Notes

const factorial = new Array(n).fill(1)Array to store factorials up to (n-1)!

for (let i = 1; i < n; i++)Compute factorial values iteratively

const numbers = []List of available numbers to pick from

k--Convert k to zero-based index

for (let i = n - 1; i >= 0; i--)Iterate from highest factorial to lowest

const idx = Math.floor(k / factorial[i])Determine index of number to pick

k %= factorial[i]Update k for next iteration

result += numbers[idx]Add selected number to result

numbers.splice(idx, 1)Remove used number from list

⏱

Complexity

TimeO(n^2)

SpaceO(n)

Computing factorials is O(n), and removing elements from the list is O(n) per removal, total O(n^2).

💡 For n=9, this is very efficient compared to brute force, running in milliseconds.

Interview Verdict: Accepted

This is the optimal approach for this problem and is expected in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, code the optimal direct computation approach after briefly mentioning brute force.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n! * n)	O(n! * n)	Yes (deep recursion)	Yes	Mention only - never code
2. Backtracking with Early Stop	O(k * n)	O(n)	Yes	Yes	Mention as improvement, but not optimal
3. Optimal Direct Computation	O(n^2)	O(n)	No	N/A	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and learn how to explain your thought process clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Explain the brute force approach to show understanding.Step 3: Discuss its inefficiency and propose early stopping.Step 4: Introduce the factorial number system for direct computation.Step 5: Code the optimal solution and test with examples.

Time Allocation

Clarify: 2min → Approach discussion: 5min → Code: 10min → Testing & optimization: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of permutations, ability to optimize brute force, and knowledge of factorial math for direct computation.

Common Follow-ups

• What if numbers are not 1 to n but an arbitrary list? → Sort and apply same logic.
• How to handle duplicates in the input? → Use backtracking with pruning or count permutations carefully.

💡 These follow-ups test your ability to generalize and handle variations of the problem.

🔍

Pattern Recognition

When to Use

1) Asked for k-th permutation or sequence; 2) Input size too large for brute force; 3) Lexicographical order mentioned; 4) Factorials or counting permutations involved.

Signature Phrases

k-th permutationlexicographical ordersequence number

NOT This Pattern When

Generating all permutations without order or combinations problems

Similar Problems

Next Permutation - find next lexicographical permutationPermutation II - handle duplicates in permutations