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. Given the following code for next permutation, what is the content of the array nums after calling next_permutation([1, 3, 2])?

easy

A. [1, 2, 3]

B. [2, 3, 1]

C. [2, 1, 3]

D. [1, 3, 2]

Solution

1. Step 1: Trace the pivot search

   Start with i = 1 (index of 3). Since nums[1]=3 >= nums[2]=2, decrement i to 0. nums[0]=1 < nums[1]=3, so pivot i=0.

2. Step 2: Find j to swap with pivot

   Start j=2 (value 2). nums[2]=2 > nums[0]=1, so j=2. Swap nums[0] and nums[2]: array becomes [2,3,1]. Then reverse suffix from i+1=1 to end: reverse [3,1] -> [1,3]. Final array: [2,1,3].

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Array changes from [1,3,2] to [2,1,3] after next permutation [OK]

Hint: Pivot found at first decreasing from right, swap and reverse suffix [OK]

Common Mistakes:

• Swapping with wrong element
• Not reversing suffix after swap

2. Consider the following Python code implementing Heap's algorithm for permutations:

from typing import List

def permute(nums: List[int]) -> List[List[int]]:
    res = [nums[:]]
    c = [0] * len(nums)
    i = 0
    while i < len(nums):
        if c[i] < i:
            if i % 2 == 0:
                nums[0], nums[i] = nums[i], nums[0]
            else:
                nums[c[i]], nums[i] = nums[i], nums[c[i]]
            res.append(nums[:])
            c[i] += 1
            i = 0
        else:
            c[i] = 0
            i += 1
    return res

print(permute([1,2,3]))

What is the value of the variable res after the algorithm completes?

easy

A. [[1, 2, 3], [1, 3, 2], [3, 1, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1]]

B. [[1, 2, 3], [2, 1, 3], [3, 1, 2], [3, 2, 1], [2, 3, 1], [1, 3, 2]]

C. [[1, 2, 3], [2, 1, 3], [3, 1, 2], [1, 3, 2], [2, 3, 1], [3, 2, 1]]

D. [[1, 2, 3], [2, 1, 3], [3, 1, 2], [1, 3, 2], [3, 2, 1], [2, 3, 1]]

Solution

1. Step 1: Trace initial state and first swaps

   Start with [1,2,3], res = [[1,2,3]]. For i=1 (odd), swap nums[c[1]] and nums[1], c[1]=0, swap nums[0] and nums[1] -> [2,1,3], append to res.

2. Step 2: Continue iterations and record permutations

   Following Heap's algorithm, the permutations generated in order are: [1,2,3], [2,1,3], [3,1,2], [1,3,2], [3,2,1], [2,3,1].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Matches Heap's algorithm output order for n=3 [OK]

Hint: Heap's algorithm generates permutations in a specific swap order [OK]

Common Mistakes:

• Confusing swap indices or order of permutations generated

3. Identify the bug in the following code snippet for counting beautiful arrangements:

medium

A. Line with 'bit = 1 << num' bit shift

B. Line with 'if (used & bit) == 0' check

C. Line with 'if pos > n:' condition

D. Line with recursive call 'backtrack(pos + 1, used | bit)'

Solution

1. Step 1: Analyze bit shift operation

   Bitmask uses 0-based indexing, so bit for number num should be 1 << (num - 1), not 1 << num.

2. Step 2: Consequence of incorrect bit shift

   Incorrect bit shifts cause wrong bits to be set/checked, leading to missing or duplicate counts.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct bit shift is critical for accurate used-state tracking [OK]

Hint: Bit shifts must be zero-based for bitmask [OK]

Common Mistakes:

• Off-by-one bit shifts
• Forgetting to unmark used numbers

4. What is the time complexity of the optimal backtracking solution for the Word Search problem, where N is the number of cells in the board and L is the length of the word?

medium

A. O(N * 4^L) because each cell explores 4 directions for each character

B. O(N * 3^L) because after the first character, each step explores up to 3 directions

C. O(N * L) because each cell is visited once per character

D. O(N^2) because the board is searched multiple times for each character

Solution

1. Step 1: Identify branching factor per recursion

   From each cell, first character has 4 directions, subsequent steps have at most 3 (excluding the cell we came from).

2. Step 2: Calculate total complexity

   For each of N cells, explore up to 3^L paths, so total time is O(N * 3^L).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   3^L accounts for pruning revisits, not 4^L [OK]

Hint: Remember first step has 4 directions, next steps 3 due to no revisiting [OK]

Common Mistakes:

• Assuming 4^L for all steps
• Confusing L with N in complexity

5. Suppose the problem changes so that each element in the input array can be used multiple times in each permutation (i.e., unlimited reuse). Which modification to the backtracking algorithm correctly generates all unique permutations with duplicates allowed and reuse permitted?

hard

A. Use backtracking without swapping, but at each recursion level, iterate over all elements and skip duplicates using a 'used' boolean array to avoid repeated elements at the same recursion depth.

B. Remove the 'seen' set and allow swapping elements freely without skipping duplicates.

C. Sort the array and use the same swapping and 'seen' set logic as before, but do not increment the recursion start index to allow reuse.

D. Generate all permutations without sorting or skipping duplicates, then filter duplicates at the end using a hash set.

Solution

1. Step 1: Understand reuse requirement

   Unlimited reuse means elements can be chosen multiple times at each recursion level, so swapping and incrementing start index is not suitable.

2. Step 2: Identify correct approach

   Backtracking without swapping, iterating over all elements at each recursion level, and using a 'used' boolean array to skip duplicates at the same depth ensures unique permutations with reuse.

3. Step 3: Evaluate other options

   Removing 'seen' causes duplicates; swapping without incrementing start index breaks logic; filtering duplicates after generation is inefficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Backtracking with reuse requires iteration over all elements each recursion, not swapping with start index increment [OK]

Hint: Reuse requires iteration over all elements each recursion, not swapping with start index increment [OK]

Common Mistakes:

• Trying to reuse elements by swapping without adjusting recursion index or skipping duplicates properly