LietCode
Permutation Sequence (Hard)

Permutation Sequence (Hard)

Abhi's photo
Abhi
·

3 min read

Explain the Problem

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 k-th permutation sequence.

Example:

Input: n = 3, k = 3

Output: "213"

Problem Explanation

Given a set of numbers [1, 2, 3, ..., n] and an integer k, we need to find the k-th permutation sequence of the set in lexicographical order. For example, if n = 3 and k = 4, the permutations in order are:

  1. "123"

  2. "132"

  3. "213"

  4. "231"

  5. "312"

  6. "321"

The 4th permutation sequence is "231".

Short, Easy-to-Remember Solution/Approach

To find the k-th permutation:

  1. Use a factorial number system to determine the positions.

  2. Keep a list of available numbers and pick numbers based on the factorial representation.

  3. Adjust k for zero-based indexing.

Solution in JavaScript with Code Commenting

function getPermutation(n, k) {
    let factorial = [1];
    let numbers = [];
    let result = "";

    // Generate factorial array and number list
    for (let i = 1; i <= n; i++) {
        factorial[i] = factorial[i - 1] * i;
        numbers.push(i);
    }

    k--; // Convert k to zero-based index

    for (let i = n; i > 0; i--) {
        let index = Math.floor(k / factorial[i - 1]);
        result += numbers[index];
        numbers.splice(index, 1); // Remove used number
        k %= factorial[i - 1];
    }

    return result;
}

// Example usage:
console.log(getPermutation(3, 4)); // Output: "231"

Explanation in Easy-to-Understand Way with Real-Life Example

Imagine you have three different colored balls: red (1), blue (2), and green (3). You want to find the 4th way to arrange these balls in a line.

  1. Factorials: Factorials help us understand the number of permutations possible with a given set. For n = 3, 3! = 6 (six permutations in total).

  2. Step-by-Step: To find the 4th permutation:

    • We determine which number should be first by seeing how many permutations start with each number.

    • Use k to pick the correct starting number.

    • Repeat the process for the remaining numbers.

Code Explanation in Pointers

  1. Initialization:

    • factorial: Array to store factorials up to n!.

    • numbers: List of numbers [1, 2, ..., n].

    • result: String to build the k-th permutation.

  2. Convert k: Adjust k to zero-based indexing for easier calculation.

  3. Determine Position:

    • Loop through positions from n to 1.

    • Calculate the index of the number to pick using Math.floor(k / factorial[i - 1]).

    • Append the number to result.

    • Remove the used number from numbers.

    • Update k using modulo operation.

  4. Return Result: The final result is the k-th permutation.

Complexities

  • Time Complexity: (O(n^2)) due to the array splice operation inside the loop.

  • Space Complexity: (O(n)) for storing the factorials and numbers arrays.

This approach efficiently finds the k-th permutation by leveraging the factorial number system, reducing the need to generate all permutations explicitly.

backtracking