Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

60. Permutation Sequence

Time: $O(n)$

Space: $O(n)$

			


class Solution {
 public:
  string getPermutation(int n, int k) {
    string ans;
    vector<int> nums(n);
    vector<int> factorial(n + 1, 1);  // factorial[i] := i!

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

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

    --k;  // 0-indexed

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

    return ans;
  }
};




			


class Solution {
  public String getPermutation(int n, int k) {
    StringBuilder sb = new StringBuilder();
    List<Integer> nums = new ArrayList<>();
    int[] factorial = new int[n + 1]; // factorial[i] := i!

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

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

    --k; // 0-indexed

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

    return sb.toString();
  }
}




			


class Solution:
  def getPermutation(self, n: int, k: int) -> str:
    ans = ''
    nums = [i + 1 for i in range(n)]
    factorial = [1] * (n + 1)  # factorial[i] := i!

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

    k -= 1  # 0-indexed

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

    return ans