https://leetcode.com/problems/permutation-sequence

The simplest way to solve this problem is use backtracking, where you just generate all sequences, with complexity O(k) = O(n!). We can do better. Let us consider an example: n=6, k=314. How we can find the first digit? There are 5! = 120 permutations, which start with 1, there are also 120 permutations, which start with 2, and so on. 314 > 2*120 and 314 < 3*120, so it means, that the fist digit we need to take is 3. So we build first digit of our number, remove it from list of all digits digits and continue:

  1. k = 314-2*5! = 74, n - 1 = 5, d = 3, build number so far 3, digits = [1,2,4,5,6]
  2. k = 74-3*4! = 2, n - 1 = 4, d = 0, build number so far 35, digits = [1,2,4,6]
  3. k = 2-0*3! = 2, n - 1 = 3, d = 0, build number so far 351, digits = [2,4,6]
  4. k = 2-1*2! = 0, n - 1 = 2, d = 2, build number so far 3512, digits = [4,6]
  5. k = 0-1*1! = 0, n - 1 = 1, d = 2, build number so far 35126, digits = [4]
  6. Finally, we have only one digit left, output is 351264.

Complexity. I keep list of n digits, and then delete them one by one. Complexity of one deletion is O(n), so overall complexity is O(n^2). Note, that it can be improved to O(n log n) if we use SortedList, but it just not worth it, n is too small.

class Solution:
    def getPermutation(self, n, k):
        numbers = list(range(1,n+1))
        answer = ""
        
        for n_it in range(n,0,-1):
            d = (k-1)//factorial(n_it-1)
            k -= d*factorial(n_it-1)
            answer += str(numbers[d])
            numbers.remove(numbers[d])
                   
        return answer

Oneliner

Here it is, with O(n^2) complexity!

return reduce(lambda s,n:(s[0]+s[2][(d:=s[1]//(f:=factorial(n)))],s[1]%f,s[2][:d]+s[2][d+1:]),range(n-1,-1,-1),('',k-1,'123456789'))[0]

If you like the solution, you can upvote it on leetcode discussion section: Problem 0060