Skip to main content

60. Permutation Sequence

hard

Given n and k, return the k-th lexicographically ordered permutation of [1..n]. Tests whether you can resist enumerating all n! permutations — the math-savvy solution skips straight to the answer in O(n^2).

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

The set [1, 2, 3, ..., n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, we get the following sequence for n = 3: "123", "132", "213", "231", "312", "321". Given n and k, return the k-th permutation sequence.

Constraints

  • 1 <= n <= 9
  • 1 <= k <= n!

Examples

Example 1

Input
n = 3, k = 3
Output
"213"

Example 2

Input
n = 4, k = 9
Output
"2314"

Example 3

Input
n = 3, k = 1
Output
"123"

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Don't generate all permutations — too slow. There's structure.

Hint 2

Permutations starting with each digit are grouped in blocks of size (n-1)!.

Hint 3

Decrement k by 1 to make it 0-indexed. The first digit's index in the remaining numbers is k / (n-1)!; new k is k % (n-1)!.

Hint 4

Repeat with n - 1 numbers. Keep a list of available digits and remove each picked one.

Solution approach

Reveal approach

Pre-compute factorials [0!, 1!, ..., n!]. Maintain a list of available digits [1, 2, ..., n]. Decrement k by 1 to 0-index. For i from 1 to n: groupSize = (n - i)!; index = k / groupSize; append digits[index] to the result; remove digits[index]; k %= groupSize. The list-removal cost is O(n) per step, so total is O(n^2). This is a recursive-decomposition pattern even though we usually write it iteratively — at each step you decide which group of (n - i)! permutations contains the k-th, then recurse on the smaller problem with the remaining digits.

Complexity

Time
O(n^2)
Space
O(n)

Related patterns

  • math
  • recursion
  • factorial-decomposition

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft

More Recursion practice problems

See all Recursion problems →