LeetCode 60: Permutation Sequence Solution
Master LeetCode problem 60 (Permutation Sequence), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
Problem Explanation
Explanation
To find the kth permutation sequence of numbers from 1 to n, we can follow these steps:
- Generate all permutations of numbers from 1 to n.
- Sort the permutations in lexicographical order.
- Return the kth permutation.
The time complexity of this approach is O(n!) as we are generating all permutations, and the space complexity is also O(n!) to store all permutations.
Solution Code
class Solution {
public String getPermutation(int n, int k) {
List<Integer> numbers = new ArrayList<>();
int[] factorial = new int[n + 1];
factorial[0] = 1;
for (int i = 1; i <= n; i++) {
numbers.add(i);
factorial[i] = factorial[i - 1] * i;
}
k--;
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= n; i++) {
int index = k / factorial[n - i];
sb.append(numbers.get(index));
numbers.remove(index);
k -= index * factorial[n - i];
}
return sb.toString();
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 60 (Permutation Sequence)?
This page provides optimized solutions for LeetCode problem 60 (Permutation Sequence) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 60 (Permutation Sequence)?
The time complexity for LeetCode 60 (Permutation Sequence) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 60 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 60 in Java, C++, or Python.