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

## C++

``````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;
}
};
``````

## JAVA

``````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)

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();
}
}
``````

## Python

``````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
``````