Permutation Sequence (Kth)

📋

Problem

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.

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!

Edge cases: n = 1, k = 1 → output '1' (smallest input)k = 1 → output is the first permutation in ascending orderk = n! → output is the last permutation in descending order

</>

IDE

def getPermutation(n: int, k: int) -> str:public String getPermutation(int n, int k)string getPermutation(int n, int k)function getPermutation(n, k)

def getPermutation(n, k):
    # Write your solution here
    pass

class Solution {
    public String getPermutation(int n, int k) {
        // Write your solution here
        return "";
    }
}

#include <string>
using namespace std;

string getPermutation(int n, int k) {
    // Write your solution here
    return "";
}

function getPermutation(n, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Wrong permutation string off by one positionOff-by-one error in k indexing (using zero-based vs one-based inconsistently).✅ Subtract 1 from k before factorial computations: k -= 1

Wrong: First permutation for all k valuesIgnoring k and always returning ascending order permutation.✅ Implement logic to select digits based on factorial divisions of k.

Wrong: Last permutation for all k valuesIgnoring k and always returning descending order permutation.✅ Implement logic to select digits based on factorial divisions of k.

Wrong: TLE or timeoutUsing brute force generation of all permutations for large n and k.✅ Use factorial number system direct computation to achieve O(n^2) time.

✓

Test Cases

Focus on handling smallest and largest k values and single-element inputs correctly.

Watch out for off-by-one errors and avoid brute force for larger inputs.

Optimize your solution to use factorial number system for direct computation to pass performance tests.

t1_01basic

Input{"n":3,"k":3}

Expected"213"

⏱ Performance - must finish in 2000ms

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

💡 Think about generating permutations in lexicographical order.

💡 Consider backtracking or factorial number system to find the k-th permutation.

💡 Use factorials to directly compute the index of each digit in the permutation.

Why it failed: Incorrect output means the permutation order or indexing is wrong. Fix by correctly mapping k to permutation indices using factorial division.

✓ Correctly computes the k-th permutation using proper indexing.

t1_02basic

Input{"n":4,"k":9}

Expected"2314"

⏱ Performance - must finish in 2000ms

The 9th permutation of [1,2,3,4] in lex order is '2314'.

💡 Try to avoid generating all permutations; think about direct computation.

💡 Use factorial values to determine which digit to pick at each position.

💡 Subtract factorial multiples from k to find the next digit index.

Why it failed: Wrong output indicates incorrect factorial indexing or off-by-one errors in k adjustment. Fix by carefully decrementing k and selecting digits.

✓ Correctly uses factorial number system to find the 9th permutation.

t2_01edge

Input{"n":1,"k":1}

Expected"1"

⏱ Performance - must finish in 2000ms

With only one element, the only permutation is '1'.

💡 Check behavior when n is minimal (1).

💡 Ensure code handles single-element permutations without error.

💡 Return the single digit as string directly when n=1.

Why it failed: Fails on single element input due to missing base case or incorrect indexing. Fix by returning '1' directly when n=1.

✓ Handles single-element input correctly.

t2_02edge

Input{"n":3,"k":1}

Expected"123"

⏱ Performance - must finish in 2000ms

The first permutation in lex order for n=3 is '123'.

💡 Check if k=1 returns the first permutation in ascending order.

💡 Verify that k is treated as 1-based index correctly.

💡 Ensure no off-by-one errors when k=1.

Why it failed: Incorrect output for k=1 means off-by-one error in indexing k. Fix by treating k as 1-based and adjusting indices accordingly.

✓ Correctly returns the first permutation for k=1.

t2_03edge

Input{"n":3,"k":6}

Expected"321"

⏱ Performance - must finish in 2000ms

The last permutation for n=3 (k=3!) is '321'.

💡 Test the exact boundary where k equals n! (last permutation).

💡 Ensure code handles maximum k correctly without overflow.

💡 Return the descending order permutation when k=n!.

Why it failed: Fails on k=n! due to incorrect factorial calculation or indexing. Fix by correctly computing factorial and adjusting k-1 indexing.

✓ Correctly returns the last permutation for k=n!.

t3_01corner

Input{"n":4,"k":14}

Expected"3142"

⏱ Performance - must finish in 2000ms

The 14th permutation of [1,2,3,4] is '3142'.

💡 Beware of off-by-one errors in factorial indexing.

💡 Check if k is decremented before calculations to convert to zero-based.

💡 Adjust k by subtracting 1 before factorial division to fix indexing.

Why it failed: Off-by-one error in k indexing causes wrong permutation. Fix by using k-1 internally before factorial computations.

✓ Handles zero-based indexing correctly to produce accurate permutation.

t3_02corner

Input{"n":5,"k":16}

Expected"14352"

⏱ Performance - must finish in 2000ms

The 16th permutation of [1,2,3,4,5] is '15432'.

💡 Check if your solution mistakenly generates permutations instead of direct computation.

💡 Avoid brute force generation for large k; use factorial number system.

💡 Implement direct computation by selecting digits based on factorial divisions.

Why it failed: Using brute force or backtracking causes inefficiency or wrong output for larger k. Fix by implementing direct factorial-based computation.

✓ Efficiently computes permutation using factorial number system.

t3_03corner

Input{"n":3,"k":4}

Expected"231"

⏱ Performance - must finish in 2000ms

The 4th permutation of [1,2,3] is '231'.

💡 Beware of confusing 0/1-based indexing in k.

💡 Check if your code treats k as zero-based or one-based consistently.

💡 Subtract 1 from k before calculations to align with zero-based indexing.

Why it failed: Confusing zero-based and one-based indexing leads to wrong output. Fix by consistently using k-1 internally.

✓ Consistent indexing yields correct permutation.

t4_01performance

Input{"n":9,"k":362880}

Expectednull

⏱ Performance - must finish in 2000ms

Maximum input size n=9, k=9! = 362880. Optimal O(n^2) factorial number system approach must complete within 2s.

💡 Generating all permutations is infeasible for n=9.

💡 Use factorial number system for direct computation in O(n^2).

💡 Avoid backtracking or brute force to prevent TLE.

Why it failed: TLE due to factorial time brute force or backtracking. Fix by implementing direct factorial number system computation.

✓ Efficient O(n^2) solution passes performance test.

Practice

1. Consider this modified code snippet for generating parentheses. Which line contains a subtle bug that can cause invalid sequences to be generated?

medium

A. Line with 'if close_count <= open_count:' condition

B. Line with 's.pop()' after backtrack calls

C. Line with 'if open_count < n:' condition

D. Line with 'if len(s) == 2 * n:' base case

Solution

1. Step 1: Examine close_count condition

   The condition 'close_count <= open_count' allows adding ')' even when close_count equals open_count, which can produce invalid sequences.

2. Step 2: Correct condition

   The correct condition is 'close_count < open_count' to ensure ')' is added only when there are unmatched '('.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing to '<' fixes invalid sequence generation [OK]

Hint: Close count must be strictly less than open count [OK]

Common Mistakes:

• Using <= instead of < for close_count condition
• Forgetting to pop after recursion

2. Consider the following buggy implementation of next permutation. Which line contains the subtle bug that causes incorrect output when the input array is in descending order?

medium

A. Line 5: if i >= 0:

B. Line 13-16: reversing the suffix after pivot

C. Line 10: nums[i], nums[j] = nums[j], nums[i]

D. Line 2: while i >= 0 and nums[i] >= nums[i + 1]: i -= 1

Solution

1. Step 1: Identify the bug

   The comment indicates the reversal of the suffix is missing or incorrectly implemented, which is critical when the array is descending (no pivot found).

2. Step 2: Analyze the reversal code

   The reversal loop runs regardless of whether i is -1, which causes incorrect behavior when the entire array is descending; the suffix should be reversed to the lowest permutation.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing or incorrect suffix reversal causes wrong output on descending arrays [OK]

Hint: Suffix reversal must always happen after pivot swap or when no pivot found [OK]

Common Mistakes:

• Not reversing suffix after swap
• Swapping with wrong element
• Ignoring descending array edge case

3. What is the time complexity of the BFS approach for removing invalid parentheses from a string of length n, considering the worst case?

medium

A. O(n * 2^n) because there can be up to 2^n states and each validity check takes O(n)

B. O(n!) because permutations of removals are explored

C. O(2^n) because BFS explores all subsets of characters without repeated checks

D. O(n^2) because each level removes one character and checks validity in O(n)

Solution

1. Step 1: Count possible states

   Each character can be either removed or kept, so up to 2^n possible strings can be generated.

2. Step 2: Analyze per-state cost

   Each string requires an O(n) validity check, so total worst-case time is O(n * 2^n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   2^n states times O(n) validity checks [OK]

Hint: 2^n states times O(n) validity checks [OK]

Common Mistakes:

• Confusing O(n^2) with BFS complexity
• Ignoring validity check cost
• Assuming factorial complexity

4. Suppose the problem is modified so that digits can be repeated any number of times (reuse allowed), and you want to generate all letter combinations of length n from the given digits. Which modification to the algorithm correctly handles this reuse scenario?

hard

A. Modify backtracking to allow choosing the same digit multiple times by not incrementing the index after each choice until length n is reached

B. Sort digits and generate combinations by picking letters only once per digit

C. Use dynamic programming to store combinations of length k and build up to length n without reuse

D. Use the same iterative queue approach but do not advance the digit index; instead, for each combination, append letters from all digits repeatedly until length n is reached

Solution

1. Step 1: Understand reuse requirement

   Allowing reuse means digits can be chosen multiple times to build combinations of length n.

2. Step 2: Identify correct approach

   Backtracking can be modified to not increment the digit index after choosing a letter, allowing reuse until length n is reached.

3. Step 3: Why other options fail

   Iterative queue approach as-is assumes fixed digit positions; DP without reuse does not handle repeated digits; sorting and picking once per digit ignores reuse.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Backtracking with flexible index handles reuse elegantly [OK]

Hint: Backtracking index controls reuse by not advancing [OK]

Common Mistakes:

• Trying to reuse digits in iterative approach without index control
• Ignoring reuse in DP or sorting

5. Suppose the problem is modified so that parentheses can be reused multiple times (e.g., you can insert removed parentheses back anywhere). Which of the following algorithmic changes correctly adapts the BFS approach to handle this variant?

hard

A. Switch to backtracking with memoization to explore insertions and removals explicitly, pruning invalid states

B. Use BFS as is, since it already explores all possible removals and insertions implicitly

C. Use a greedy approach to insert parentheses at earliest invalid positions without BFS or backtracking

D. Modify BFS to allow adding parentheses back by generating new states with insertions at every position

Solution

1. Step 1: Understand reuse of parentheses

   Allowing reuse means we can insert parentheses anywhere, greatly increasing state space and complexity.

2. Step 2: Analyze BFS suitability

   Standard BFS only removes characters; it does not handle insertions, so it cannot explore all states correctly.

3. Step 3: Identify correct approach

   Backtracking with memoization can explicitly explore insertions and removals, pruning invalid states to handle reuse properly.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Backtracking with memoization handles insertions and pruning [OK]

Hint: Reuse requires explicit insertion exploration, not just removal BFS [OK]

Common Mistakes:

• Assuming BFS handles insertions
• Using greedy for complex insertions
• Modifying BFS without pruning leads to explosion