L18. K-th Permutation Sequence | Leetcode

Summary (K-th Permutation Sequence – Leetcode)

Problem Definition

Given integers n and k, consider all permutations of the numbers 1..n. There are n! total permutations. When arranged in lexicographical order, the task is to return the k-th permutation (as stated 1-indexed, but typically handled as 0-indexed in the solution).

Key Example Reasoning

• For n = 3, there are 3! = 6 permutations.
• If k = 3, the solution returns the 3rd lexicographical permutation; if k = 5, it returns the 5th, etc.
• For the walkthrough example n = 4, the total permutations are 24 (i.e., 4!).

---

Naive / Brute Force Approach (Interview Starter)

1. Generate all permutations using recursion.
2. Store them, then sort lexicographically.
3. Return the permutation at index k - 1 (because code uses 0-based indexing).

Complexity Claims

• Generating permutations: O(n!)
• Storing/copying each permutation adds about another factor of O(n) → O(n · n!)
• Sorting all permutations: roughly O(n! · log(n!))
• Described as very slow (“hell of a time”), motivating an optimized method.

---

Optimal Mathematical / Block Decomposition Approach

The core insight: permutations can be divided into blocks of equal size.

• Fix the first digit.
• The remaining (n-1) digits can be permuted in (n-1)! ways.
• Therefore, the first digit is determined by which block contains the k-th permutation.

Step-by-Step Logic

1. Convert to 0-based indexing: k = k - 1
2. Let blockSize = (remainingLen - 1)!
3. Compute the block’s index within the remaining numbers:
   • idx = k / blockSize
4. Pick nums[idx] and append it to the answer
5. Remove that number from the list
6. Update: k = k % blockSize
7. Repeat until the list is empty

Walkthrough Example (as described)

For n = 4, k = 17:

• Convert to 0-based: k = 16
• Initial block size: 3! = 6
  • Since 16 falls into the block starting with 3, the first digit is 3
• Next:
  • reduce via k % 6
  • block size becomes 2!
• Continue similarly until the remaining list is exhausted.

Final produced example permutation: “3412”.

---

Implementation Details Highlighted

C++ Implementation (as described)

• Compute factorial = (n-1)!
• Store remaining numbers 1..n in an array/vector
• Convert k to 0-based by doing k = k - 1
• While numbers remain:
  • idx = k / factorial
  • append nums[idx] to the result string
  • erase that element from the vector
  • k = k % factorial
  • update factorial to the next smaller factorial (conceptually shifting to the next block size)

Time/Space Complexity (as claimed)

• Vector middle erase is O(n)
• Over n selections → total O(n²)
• Space: O(n) (vector + output)

---

Java Implementation (as described)

Mirrors the same block-selection method:

• Precompute factorial = (n-1)!
• Maintain a list containing 1..n
• Use k - 1 for 0-based indexing
• In a loop:
  • pick index = k / factorial
  • append element to the answer string
  • remove it from the list
  • update k = k % factorial
  • reduce factorial as the list size shrinks
• Return the built string when the list is empty

---

Main Speakers / Sources

• Primary source: The video narrator/host (starting with “hey everyone welcome back…”) who solves and codes Leetcode’s “K-th Permutation Sequence”.