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 the following Python code implementing the bitmask backtracking solution for N-Queens II. What is the final return value of totalNQueens(4)?

easy

A. 2

B. 0

C. 1

D. 4

Solution

1. Step 1: Trace initial call for n=4

   Start with row=0, no columns or diagonals occupied, all 4 columns available.

2. Step 2: Count valid placements recursively

   Backtracking explores all valid queen placements; for n=4, there are exactly 2 distinct solutions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Known result for 4-queens is 2 solutions [OK]

Hint: 4-queens has 2 solutions; bitmask backtracking counts all [OK]

Common Mistakes:

• Off-by-one counting
• Confusing number of solutions with board size

2. You are given an array of integers and need to find the lexicographically next greater permutation of its elements. Which approach guarantees finding this next permutation in optimal time without generating all permutations?

easy

A. Scan from the end to find a pivot where the sequence stops increasing, swap with the smallest greater element on the right, then reverse the suffix.

B. Apply a greedy approach by swapping the first two elements that are out of order from the start.

C. Use dynamic programming to store all permutations and find the next one by memoization.

D. Generate all permutations, sort them, and pick the next one after the current permutation.

Solution

1. Step 1: Understand the problem requirement

   The problem asks for the lexicographically next greater permutation, which requires finding the next sequence just larger than the current one.

2. Step 2: Identify the optimal approach

   The approach scanning from the end to find a pivot where the sequence stops increasing, swapping with the smallest greater element on the right, then reversing the suffix guarantees the next permutation in O(n) time without generating all permutations.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Brute force is correct but inefficient; DP and greedy do not guarantee correct next permutation [OK]

Hint: Next permutation uses pivot-swap-reverse pattern [OK]

Common Mistakes:

• Thinking brute force is optimal
• Using greedy from start fails on suffix order

3. What is the time complexity of the optimal in-place next permutation algorithm for an input array of length n?

medium

A. O(n) because it scans the array a constant number of times

B. O(n log n) because it sorts the suffix after the pivot

C. O(n!) due to generating all permutations

D. O(n^2) because it swaps elements multiple times in nested loops

Solution

1. Step 1: Identify the main operations

   The algorithm scans from the end to find the pivot (O(n)), then scans again to find the swap element (O(n)), and finally reverses the suffix (O(n)).

2. Step 2: Sum up the operations

   All steps are linear scans or swaps, so total time complexity is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   No sorting or factorial generation involved, linear scans only [OK]

Hint: Next permutation scans array linearly multiple times [OK]

Common Mistakes:

• Confusing suffix reversal with sorting
• Assuming factorial due to permutations

4. Suppose the Expression Add Operators problem is modified so that digits can be reused any number of times to form expressions (i.e., unlimited reuse of digits in order). Which of the following algorithmic changes correctly adapts the backtracking solution to handle this variant without infinite loops or incorrect results?

hard

A. Remove the index increment in recursive calls to allow reuse, but add a visited set to avoid infinite loops

B. Keep the index increment as is, but allow substring splits to wrap around to the start of the string

C. Modify backtracking to not increment index after choosing a digit, but limit recursion depth to n to prevent infinite loops

D. Allow index to reset to zero after reaching the end, but prune expressions longer than a fixed length to avoid infinite recursion

Solution

1. Step 1: Understand digit reuse impact

   Allowing reuse means the index does not always increment; digits can be chosen repeatedly, risking infinite recursion.

2. Step 2: Prevent infinite loops

   Not incrementing index requires limiting recursion depth (e.g., max length n) to avoid infinite loops while exploring repeated digits.

3. Step 3: Evaluate options

   Modify backtracking to not increment index after choosing a digit, but limit recursion depth to n to prevent infinite loops correctly limits recursion depth while allowing reuse; others either cause infinite loops or incorrect pruning.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Limiting recursion depth prevents infinite loops with reuse [OK]

Hint: Limit recursion depth when digits can be reused [OK]

Common Mistakes:

• Forgetting to limit recursion depth causes infinite loops

5. Suppose you want to generate all valid parentheses sequences of length 2n, but now you can reuse parentheses pairs multiple times (i.e., sequences can contain repeated pairs). Which modification to the backtracking algorithm correctly handles this variant?

hard

A. Use memoization to store and reuse previously generated valid sequences to handle repeated pairs

B. Keep the original constraints but allow adding '(' or ')' even if counts exceed n, then filter duplicates after generation

C. Modify the algorithm to generate sequences of length 2n without constraints, then check validity and uniqueness

D. Remove the limit on open_count and close_count, allowing unlimited '(' and ')' additions

Solution

1. Step 1: Understand reuse requirement

   Reusing pairs means sequences can contain repeated valid substrings; naive pruning breaks this.

2. Step 2: Analyze modifications

   Removing limits or generating all sequences leads to invalid or duplicate sequences. Memoization allows reusing computed valid sequences efficiently.

3. Step 3: Choose correct approach

   Memoization stores and reuses valid subsequences, enabling correct generation with reuse.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Memoization handles reuse without generating invalid sequences [OK]

Hint: Memoization enables reuse without invalid sequences [OK]

Common Mistakes:

• Removing constraints causes invalid sequences
• Filtering duplicates after generation is inefficient