Permutation Sequence [LC#60]

The set [1, 2, 3, ..., n] contains a total of n! unique permutations. Given n and k, return the kth permutation sequence.

Intuition

Code

def kth_permutation(n: int, k: int) -> str:
    factorials = [1]
    digits = ["1"]
    for i in range(1, n):
        factorials.append(factorials[-1] * i)
        digits.append(str(i + 1))

    output = []
    k -= 1
    for i in range(n - 1, -1, -1):
        # index = k // factorials[i]
        # k = k - idx * factorials[i]
        index, k = divmod(k, factorials[i])
        output.append(digits[index])
        del digits[index]
    return "".join(output)

Time complexity