LeetCode Hard –  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:

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Example 1:Input: n = 3, k = 3 Output: “213”

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

Example 3:Input: n = 3, k = 1 Output: “123”

Constraints:

• 1 <= n <= 9
• 1 <= k <= n!

Java Solution

You can solve this problem by using a mathematical approach. The idea is to find the kth permutation by iteratively determining each digit at a time. Here’s a Java implementation for this problem:

import java.util.ArrayList;
import java.util.List;

public class KthPermutation {
    public static String getPermutation(int n, int k) {
        List<Integer> numbers = new ArrayList<>();
        int[] factorial = new int[n + 1];
        StringBuilder result = new StringBuilder();

        // Calculate factorial values
        factorial[0] = 1;
        for (int i = 1; i <= n; i++) {
            factorial[i] = i * factorial[i - 1];
            numbers.add(i);
        }

        k--; // Adjust k to 0-based index

        for (int i = 1; i <= n; i++) {
            int index = k / factorial[n - i];
            result.append(numbers.get(index));
            numbers.remove(index);
            k %= factorial[n - i];
        }

        return result.toString();
    }

    public static void main(String[] args) {
        System.out.println(getPermutation(3, 3));  // Output: "213"
        System.out.println(getPermutation(4, 9));  // Output: "2314"
        System.out.println(getPermutation(3, 1));  // Output: "123"
    }
}

In this Java solution, the getPermutation method uses a mathematical approach to find the kth permutation. It calculates the factorial values, then iteratively determines each digit of the permutation by dividing k by the factorial of the remaining digits. The numbers list is used to store available digits, and the result is built accordingly.

Python Solution

def getPermutation(n, k):
    numbers = list(range(1, n + 1))
    factorial = [1] * (n + 1)
    result = []

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

    k -= 1  # Adjust k to 0-based index

    for i in range(1, n + 1):
        index = k // factorial[n - i]
        result.append(numbers[index])
        numbers.pop(index)
        k %= factorial[n - i]

    return ''.join(map(str, result))

# Test cases
print(getPermutation(3, 3))  # Output: "213"
print(getPermutation(4, 9))  # Output: "2314"
print(getPermutation(3, 1))  # Output: "123"

This Python code follows the same logic as the Java solution. It calculates factorial values, iteratively determines each digit of the permutation, and builds the result accordingly. Make sure to run the provided test cases to verify the correctness of the implementation.