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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Permutation Sequence and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →