Permutation Sequence (Kth)

▶

Steps

setup

Initialize factorial array

Create a factorial array of size n with all elements initialized to 1. This array will store factorial values from 0! to (n-1)!.

💡 Precomputing factorials allows quick calculation of how many permutations start with each number at each position.

Line:

factorial = [1] * n

💡 Factorials represent the number of permutations possible for the remaining positions.

setup

Compute factorial values

Compute factorial values for indices 1 and 2 by multiplying the previous factorial by the current index.

💡 This step fills the factorial array with correct values to use for index calculations later.

Line:

for i in range(1, n):
    factorial[i] = factorial[i - 1] * i

💡 factorial[1] = 1, factorial[2] = 2, representing 1! and 2! respectively.

setup

Initialize numbers list

Create a list of numbers from 1 to n to represent the available digits for the permutation.

💡 This list will shrink as numbers are chosen for the permutation.

Line:

numbers = list(range(1, n + 1))

💡 The numbers list starts as [1, 2, 3], representing all digits to choose from.

setup

Adjust k to zero-based index

Subtract 1 from k to convert it from 1-based to zero-based indexing for easier calculations.

💡 Zero-based indexing aligns with array indices and factorial calculations.

Line:

k -= 1  # zero-based index

💡 k changes from 3 to 2, meaning we want the 2nd index permutation in zero-based terms.

traverse

Calculate index for first position

Calculate idx by dividing k by factorial[2] (2!). idx = 2 // 2 = 1. This selects the second number in the list for the first position.

💡 This determines which number to pick first based on how many permutations each number leads.

Line:

idx = k // factorial[i]

💡 Choosing index 1 means the first digit is '2' (numbers[1]).

traverse

Update k after first selection

Update k to k modulo factorial[2], k = 2 % 2 = 0. This resets k for the next position's calculation.

💡 Updating k narrows down the position within the smaller permutation block.

Line:

k %= factorial[i]

💡 k=0 means the next selection is the first in the remaining permutations.

insert

Append first chosen number and remove it

Append '2' (numbers[1]) to the result and remove it from the numbers list, leaving [1, 3].

💡 Removing the chosen number prevents reuse and shrinks the problem size.

Line:

result.append(str(numbers[idx]))
numbers.pop(idx)

💡 The first digit of the permutation is fixed as '2'.

traverse

Calculate index for second position

Calculate idx = k // factorial[1] = 0 // 1 = 0. Select the first number in the updated list [1,3].

💡 This picks the next digit based on the updated k and factorial values.

Line:

idx = k // factorial[i]

💡 Choosing index 0 means the second digit is '1'.

traverse

Update k after second selection

Update k = k % factorial[1] = 0 % 1 = 0, preparing for the last digit selection.

💡 k remains zero, indicating the first permutation in the last block.

Line:

k %= factorial[i]

💡 k=0 means the next digit is the first in the remaining list.

insert

Append second chosen number and remove it

Append '1' (numbers[0]) to the result and remove it from the list, leaving [3].

💡 The permutation is building with the second digit fixed.

Line:

result.append(str(numbers[idx]))
numbers.pop(idx)

💡 The permutation so far is '21'.

traverse

Calculate index for last position

Calculate idx = k // factorial[0] = 0 // 1 = 0. Select the only remaining number '3'.

💡 The last digit is chosen from the remaining single number.

Line:

idx = k // factorial[i]

💡 The last digit completes the permutation.

insert

Append last chosen number and remove it

Append '3' to the result and remove it from the numbers list, which becomes empty.

💡 The permutation is now complete with all digits chosen.

Line:

result.append(str(numbers[idx]))
numbers.pop(idx)

💡 The final permutation string is '213'.

reconstruct

Return final permutation string

Join the result list into a string and return it as the kth permutation.

💡 This step outputs the final answer after all selections.

Line:

return ''.join(result)

💡 The algorithm efficiently computed the 3rd permutation without enumerating all permutations.

def getPermutation(n, k):
    factorial = [1] * n  # STEP 1
    for i in range(1, n):  # STEP 2
        factorial[i] = factorial[i - 1] * i
    numbers = list(range(1, n + 1))  # STEP 3
    k -= 1  # zero-based index adjustment STEP 4
    result = []
    for i in range(n - 1, -1, -1):  # STEP 5-12
        idx = k // factorial[i]  # STEP 5,8,11
        k %= factorial[i]  # STEP 6,9,12
        result.append(str(numbers[idx]))  # STEP 7,10,12
        numbers.pop(idx)
    return ''.join(result)  # STEP 13

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

📊

Permutation Sequence (Kth) - Watch the Algorithm Execute, Step by Step

Watching this step-by-step reveals how the factorial number system helps directly compute the kth permutation without generating all permutations.

setup

1

0

1

1

1

2

Result: ""

fill_row

1

0

1

1

i

2

2

Result: ""

setup

1

0

2

1

3

2

Result: ""

setup

1

0

2

1

k

3

2

Result: ""

compare

1

0

idx

2

1

i

3

2

Result: ""

move_left

k

1

0

idx

2

1

i

3

2

Result: ""

delete

k

1

0

3

1

Result: "2"

compare

idx

1

0

i

3

1

Result: "2"

move_left

idx

1

0

i

3

1

Result: "2"

delete

k

3

0

Result: "21"

compare

idx

3

0

Result: "21"

delete

Result: "213"

record

Result: "213"

Key Takeaways

✓ The factorial number system partitions permutations into blocks, allowing direct calculation of the kth permutation without generating all permutations.

This insight is hard to see from code alone because the math behind factorial indexing is abstract without visualization.

✓ At each step, the algorithm selects a digit by dividing k by the factorial of remaining positions, then updates k to the remainder, progressively narrowing down the permutation.

Seeing k and idx update step-by-step clarifies how the algorithm zooms into the correct permutation.

✓ Removing chosen numbers from the list ensures no repeats and reduces the problem size, which is visually clear when watching the array shrink.

This concrete example shows how the numbers list changes, which is less obvious when reading code.

Practice

1. You need to count the number of permutations of numbers from 1 to n such that for each position i, either the number at position i is divisible by i or i is divisible by the number. Which algorithmic approach best guarantees an efficient solution?

easy

A. Sorting numbers and checking divisibility in a single pass

B. Greedy algorithm that places numbers based on divisibility from left to right

C. Dynamic programming with memoization over subsets

D. Backtracking with pruning to explore valid permutations only

Solution

1. Step 1: Understand problem constraints

   The problem requires counting permutations with divisibility conditions at each position, which is a combinatorial search problem.

2. Step 2: Identify suitable algorithm

   Backtracking with pruning efficiently explores only valid permutations, avoiding full enumeration, unlike greedy or sorting approaches which fail to guarantee correctness.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Backtracking prunes invalid branches early, ensuring correctness and efficiency [OK]

Hint: Backtracking prunes invalid permutations early [OK]

Common Mistakes:

• Assuming greedy can solve divisibility constraints
• Thinking sorting suffices for permutation constraints

2. 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

3. You need to partition a string into substrings such that every substring is a palindrome. Which algorithmic approach guarantees finding all possible palindrome partitions efficiently by pruning invalid partitions early?

easy

A. Backtracking that explores all substring partitions and checks palindrome validity dynamically

B. Dynamic programming that counts the number of palindromic substrings without generating partitions

C. Greedy approach that picks the longest palindrome substring at each step

D. Breadth-first search that generates partitions level by level without palindrome checks

Solution

1. Step 1: Understand problem requirements

   The problem requires generating all palindrome partitions, not just counting or finding one.

2. Step 2: Identify suitable algorithm

   Backtracking explores all partitions and prunes invalid ones by checking palindrome substrings dynamically, ensuring completeness and correctness.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking with palindrome checks finds all partitions [OK]

Hint: Backtracking explores all partitions with palindrome pruning [OK]

Common Mistakes:

• Assuming greedy longest palindrome picks all partitions
• Confusing counting palindromes with generating partitions
• Ignoring palindrome checks in BFS

4. You are given a string containing only digits. Your task is to split it into exactly four parts such that each part represents a valid IP address segment (0 to 255, no leading zeros except for '0'). Which algorithmic approach guarantees finding all valid IP addresses efficiently?

easy

A. Sorting the digits and then partitioning into four segments

B. Greedy approach that picks the shortest valid segment at each step

C. Dynamic programming to count the number of valid segmentations

D. Backtracking with pruning to explore all valid segmentations

Solution

1. Step 1: Understand the problem constraints

   The problem requires enumerating all valid IP addresses, which involves exploring multiple segmentations of the string.

2. Step 2: Evaluate algorithm suitability

   Greedy approaches fail because they may miss valid segmentations; DP counting does not generate all solutions; sorting digits destroys original order. Backtracking with pruning systematically explores all valid partitions.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Backtracking explores all partitions with pruning to avoid invalid segments [OK]

Hint: Backtracking explores all segmentations with pruning [OK]

Common Mistakes:

• Assuming greedy can find all valid IPs
• Using DP counting without generating solutions

5. What is the time complexity of generating all permutations of an array of length n using Heap's algorithm, and why might a common misconception about this complexity be incorrect?

medium

A. O(n! * n^2) because each permutation requires n swaps and there are n! permutations

B. O(n! * log n) because Heap's algorithm uses a heap data structure internally

C. O(n! * n) because each of the n! permutations requires copying the array of length n

D. O(n! + n) because generating permutations is factorial plus linear overhead

Solution

1. Step 1: Identify number of permutations

   There are n! permutations for an array of length n.

2. Step 2: Analyze cost per permutation

   Heap's algorithm generates each permutation with O(1) swaps, but copying the current permutation to the result list takes O(n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Time complexity is O(n! * n) due to copying each permutation [OK]

Hint: Copying each permutation costs O(n), not the swaps themselves [OK]

Common Mistakes:

• Assuming swaps cost O(n) each or confusing heap data structure usage