60. Permutation Sequence

Problem Statement in English

You’re given two integers n and k. You need to return the k-th permutation sequence of the numbers from 1 to n.

Approach

We approach this just line generating all the permutations of the numbers from 1 to n and returning the k-th one.

Check out the 46. Permutations post for more details on generating all permutations.

And we’re done!

Solution in Python

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        count = 0
        seen = set()
        buffer = []

        def permute():
            nonlocal count

            if len(buffer) == n:
                count += 1
                if count == k:
                    return True
                return False

            for i in range(1, n + 1):
                if i in seen:
                    continue

                buffer.append(i)
                seen.add(i)

                if permute():
                    return True

                seen.remove(i)
                buffer.pop()

        permute()
        return "".join(map(str, buffer))

Complexity

• Time: $O(n \times n!)$
  Since the outermost loop runs $n$ times, and the loop inside that runs $n - 1$ times, and the one inside that $n - 2$ times, and for each of these loops there are $n$ checks of the seen set.

• Space: $O(n)$
  Since we are using a seen set which can contain $n$ elements at most.

And we are done.