Generated by Codex with GPT-5

Quick facts

What the problem is really asking

The numbers 1 through n can form n! different permutations in lexicographic order.

The problem asks for the kth permutation in that ordering without generating all the earlier ones first.

That is the only real challenge. If the task were simply to list all permutations, a standard backtracking solution would work. But here that would waste a huge amount of work because the answer can be constructed directly.

The key insight: permutations come in factorial-sized blocks

Fix the first digit of the permutation.

If n = 4, then every choice of the first digit leaves 3 remaining digits, which can be arranged in 3! = 6 ways. That means:

  • permutations starting with 1 occupy the first 6 positions
  • permutations starting with 2 occupy the next 6
  • permutations starting with 3 occupy the next 6
  • permutations starting with 4 occupy the last 6

So the first digit is determined by asking:

Which block of size (n - 1)! contains the rank k?

After choosing that first digit, the exact same logic applies to the remaining digits. This is why the optimal solution feels like repeatedly zooming into smaller factorial blocks.

How to derive the direct solution

The clean derivation is:

  1. Convert k from one-based indexing to zero-based indexing, because division works more naturally that way.
  2. Keep a sorted list of currently unused digits.
  3. For each position from left to right:
  4. Compute how many permutations each possible next digit would cover: (remaining_count - 1)!.
  5. Use integer division to choose the correct digit block.
  6. Remove that digit, reduce the rank with modulo, and continue.

This works because lexicographic order groups permutations by prefix. Once the correct prefix block is chosen, every earlier block can be skipped entirely.

Why this is the best approach

The optimal interview answer uses factorial numbering, sometimes called the factorial number system.

It avoids generating permutations and instead computes the answer digit by digit. With a normal Python list of remaining digits, the time complexity is O(n^2) because removing the ith unused digit costs linear time. The auxiliary space is O(n) for the remaining digits and factorial table.

For the actual LeetCode constraints, that is more than good enough and is the intended solution. The important win is conceptual: the algorithm jumps directly to the correct permutation instead of exploring the whole search tree.

Python solution

The implementation below keeps the ranking logic separate from the LeetCode wrapper. It validates the inputs, precomputes factorials once, and then repeatedly chooses the correct unused digit for each position.

from typing import List


class PermutationSequenceBuilder:
    """Build the k-th lexicographic permutation of the numbers 1..n."""

    @staticmethod
    def build_factorials(limit: int) -> List[int]:
        """Return factorial values from 0! through limit! inclusive."""
        factorials = [1] * (limit + 1)
        for value in range(1, limit + 1):
            factorials[value] = factorials[value - 1] * value
        return factorials

    @staticmethod
    def validate_inputs(n: int, k: int, factorials: List[int]) -> None:
        """Ensure the requested rank is inside the valid permutation range."""
        if n <= 0:
            raise ValueError("n must be positive.")

        total_permutations = factorials[n]
        if k < 1 or k > total_permutations:
            raise ValueError(
                f"k must be between 1 and {total_permutations} for n={n}."
            )

    def get_kth_permutation(self, n: int, k: int) -> str:
        """Return the k-th permutation using one-based indexing for k."""
        factorials = self.build_factorials(n)
        self.validate_inputs(n, k, factorials)

        available_digits = [str(value) for value in range(1, n + 1)]
        zero_indexed_rank = k - 1
        permutation_parts: List[str] = []

        for remaining_count in range(n, 0, -1):
            block_size = factorials[remaining_count - 1]

            # Choose which unused digit owns the current lexicographic block.
            digit_index = zero_indexed_rank // block_size
            zero_indexed_rank %= block_size

            chosen_digit = available_digits.pop(digit_index)
            permutation_parts.append(chosen_digit)

        return "".join(permutation_parts)


class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        """LeetCode entry point."""
        builder = PermutationSequenceBuilder()
        return builder.get_kth_permutation(n, k)

Interview follow-ups

What if the interviewer asks for a recursive solution?

The same factorial-block idea can be written recursively instead of iteratively. At each recursive step, choose the correct digit by dividing the current rank by (remaining_count - 1)!, remove that digit from the available set, and recurse on the rest. This works for exactly the same reason as the iterative version: lexicographic order is organized by prefix blocks. The tradeoff is mainly style. The recursive version can feel elegant, but the iterative version is usually easier to debug and avoids recursion overhead.

What if n becomes much larger and O(n^2) removal is no longer acceptable?

Then the bottleneck is not the factorial math. It is the data structure used to find and remove the digit_indexth unused element. A plain Python list makes that operation linear, which is fine for small n but not for large-scale variants. To improve it, use an order-statistics structure such as a Fenwick tree, segment tree, or balanced binary search tree that can find the kth remaining item and delete it in O(log n) time. The overall algorithmic idea stays the same, but the total runtime improves to O(n log n) at the cost of a more complex implementation.

How would you adapt this if the available symbols were arbitrary characters instead of 1..n?

The direct-ranking approach still works. The only requirement is that the symbols start in sorted order so that the lexicographic blocks line up with the requested ordering. Instead of initializing ["1", "2", ..., "n"], the algorithm would initialize a sorted list like ["A", "C", "F", "Z"] or any other ordered items, then use the same factorial block selection on that list. The complexity does not change. The only real difference is how the symbols are represented and sorted.

Why is generating all permutations the wrong answer here?

Because it solves a much bigger problem than the prompt asked for. Backtracking generates every permutation up to the target rank, which takes O(n! * n) time if the produced strings are counted. The factorial-numbering solution skips entire subtrees at once by reasoning about how many permutations share a prefix. That is exactly the sort of optimization interviewers want to hear: not just how to produce correct output, but how to avoid unnecessary work by using the structure of lexicographic ordering.

Practical takeaway

This problem becomes simple once it is viewed as a ranking problem instead of a permutation-generation problem.

The pattern to remember is:

  • each choice for the next digit owns a block of (remaining_count - 1)! permutations
  • division picks the right block
  • modulo gives the rank inside that block

That turns what looks like a backtracking problem into a direct constructive algorithm.