Skip to content

60. Permutation Sequence 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  string getPermutation(int n, int k) {
    string ans;
    vector<int> nums(n);
    vector<int> fact(n + 1, 1);  // fact[i] := i!

    iota(nums.begin(), nums.end(), 1);

    for (int i = 2; i <= n; ++i)
      fact[i] = fact[i - 1] * i;

    --k;  // 0-indexed

    for (int i = n - 1; i >= 0; --i) {
      const int j = k / fact[i];
      k %= fact[i];
      ans += to_string(nums[j]);
      nums.erase(nums.begin() + j);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
  public String getPermutation(int n, int k) {
    StringBuilder sb = new StringBuilder();
    List<Integer> nums = new ArrayList<>();
    int[] fact = new int[n + 1]; // fact[i] := i!

    for (int i = 1; i <= n; ++i)
      nums.add(i);

    Arrays.fill(fact, 1);
    for (int i = 2; i <= n; ++i)
      fact[i] = fact[i - 1] * i;

    --k; // 0-indexed

    for (int i = n - 1; i >= 0; --i) {
      final int j = k / fact[i];
      k %= fact[i];
      sb.append(nums.get(j));
      nums.remove(j);
    }

    return sb.toString();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def getPermutation(self, n: int, k: int) -> str:
    ans = ''
    nums = [i + 1 for i in range(n)]
    fact = [1] * (n + 1)  # fact[i] := i!

    for i in range(2, n + 1):
      fact[i] = fact[i - 1] * i

    k -= 1  # 0-indexed

    for i in reversed(range(n)):
      j = k // fact[i]
      k %= fact[i]
      ans += str(nums[j])
      nums.pop(j)

    return ans