menu

[LeetCode] 060. Permutation Sequence

Problem (Medium)

060. Permutation Sequence

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 kth permutation sequence.

Note:

  • Given n will be between 1 and 9 inclusive.
  • Given k will be between 1 and n! inclusive.

Example 1:

  • Input: n = 3, k = 3
  • Output: “213”

Example 2:

  • Input: n = 4, k = 9
  • Output: “2314”

Approach 1: (My Solution, Time Limit Exceeded!)

Idea

  • List all possible permutations by backtracking method;
  • grab the k-th item in the list.

Solution

class Solution1:
    def getPermutation(self, n, k): 
        """ 
        :type n: int
        :type k: int
        :rtype: str
        """
        res = []
        self.backtrack(res, n, [])
        return ''.join([str(i) for i in res[k-1]])

    def backtrack(self, res, n, item):
        if len(item) == n:
            res.append(item)
            return
        for i in range(n):
            if i+1 in item:
                continue
            self.backtrack(res, n, item+[i+1])

Complexity

  • Time: $O()$?
  • Space: $O(n!)$

Approach 2: Solution in $O(n)$ *

Idea

“Explain-like-I’m-five” Java Solution in O(n)

Solution

import math
class Solution2:
    # @param {integer} n
    # @param {integer} k
    # @return {string}
    def getPermutation(self, n, k):
        numbers = range(1, n+1)
        permutation = ''
        k -= 1
        while n > 0:
            n -= 1
            # get the index of current digit
            index, k = divmod(k, math.factorial(n))
            permutation += str(numbers[index])
            # remove handled number
            numbers.remove(numbers[index])

        return permutation

Complexity

  • Time: $O(n)$?
  • Space: $O(n)$?



KF

Comments