Coding

Permutation Sequence

Asked at

InfoEdge India Ltd

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given two integers n and k, return the k-th permutation sequence of the numbers [1, 2, 3, ..., n].

The permutations are arranged in lexicographic order (i.e., dictionary order).

You must solve the problem without generating all permutations explicitly.

Input: n = 3, k = 3 **Output: **"213" Explanation: The permutations in order are:

1. 123
1. 132
1. 213 ← K = 3
1. 231
1. 312
1. 321

**Input: **n = 3, k = 5 Output: "312" **Explanation: **K = 5 corresponds to the fifth permutation in lexicographic order.

Input: n = 4, k = 9

1 <= n <= 9
1 <= k <= n! (i.e., k is always a valid permutation index)

cpp

class Solution {
public:
    string getPermutation(int n, int k) {
        // Your code goes here
    }
};

java

class Solution {
    public String getPermutation(int n, int k) {
        // Your code goes here
    }
}

python

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        # Your code goes here

javascript

class Solution {
    getPermutation(n, k) {
        // Your code goes here
    }
}

csharp

class Solution {
    public string GetPermutation(int n, int k) {
        // Your code goes here
    }
}

func getPermutation(n int, k int) string {
    // Your code goes here
}

Stuck? Show a way to structure it+

01Convert one-based k to zero-based k minus one.
02Keep sorted unused digits and precompute factorials.
03At each remaining length m, choose index k divided by factorial(m minus one).
04Remove that digit and replace k with the remainder.
05Append until no digits remain.

Reference answer

There are factorial(n minus one) lexicographic permutations beginning with each possible first digit. Convert k from one-based to zero-based so integer division identifies the correct block. Keep a list containing 1 through n. With m digits left, compute block = factorial(m minus one), select index = k divided by block, append that unused digit, remove it from the list, and replace k with k modulo block. Repeat until the list is empty. For n = 3 and k = 3, zero-based k is 2; blocks of size 2 select 2 first, then the remaining index selects 1, producing 213. Do not generate all n factorial permutations: that defeats the requirement. Precomputing factorials costs O(n) time and space. Removing from an array costs O(n) per step, so this direct implementation is O(n squared) time and O(n) space, which is ideal for n at most 9.

Then expect these follow-ups

How would you find the rank of a given permutation?
Tests: follow-up reasoning
How does this change when digits can repeat?
Tests: constraint adaptation

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question