K-th permutation Sequence

Dec 18, 2024 • 3 mins read

Problem Overview

The Permutation Sequence problem is a challenge that belongs to the category of combinatorial problems on LeetCode. The problem requires finding the k-th permutation sequence of numbers using 1 through n, arranged in lexicographical order. This requires understanding permutations, sequences, and effectively employing recursion along with mathematical insights to solve the problem efficiently.

Understanding the Problem

Given two integers, n and k, where n represents the number of elements in the sequence ranging from 1 to n, and k is the position in the lexicographical order of permutations, the task is to output the k-th permutation sequence.

Example

Example 1:

Input: n = 3, k = 3
Output: "213"
Explanation: The permutations sequence from 1 to 3 are:
1. 123
2. 132
3. 213
4. 231
5. 312
6. 321

In this case, the 3rd permutation is "213".

Constraints:

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

Key DSA Concepts and Theory

Permutations

Permutations are different arrangements of a set of elements. The number of permutations of n elements is n! (n factorial). For instance, numbers 1, 2, and 3 have 3! = 6 permutations.

Lexicographical Order

Lexicographical order is akin to dictionary order. For example, in numbers from 1 to 3, "123" comes before "132", just like words starting with 'a' come before those starting with 'b'.

Factorial Number System

A less common concept, factorial number system, can help solve permutation index problems efficiently. It uses the positional values as factorials. For a sequence [1, 2, 3], the factorial number system represents:

1 * (n-1)! + 1 * (n-2)! + ...

Understanding its significance is vital in calculating permutations efficiently without generating them all.

Solution Approach

To solve this problem without generating all permutations, we can consider the factorial representation to decide which numbers should appear at each position of our permutation to directly determine the k-th permutation. Here’s how you can achieve this:

Precompute Factorials: Calculate the factorial for all numbers from 1 to n-1 as they will determine how many permutations begin with a particular number at each position.
Zero-based index: Convert the k-th position to a zero-based index selection to simplify calculations internally.
Initialize a number list: Keep a list of numbers from which we pick to form the permutation.
Iterate to build the permutation: Use the idea of the permutations' distribution into blocks controlled by factorial divisions to select the right number at each position.

Below is the code implementation in both C++ and Java.

C++ Implementation

#include <vector>
#include <string>

class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> factorial(n, 1);
        vector<int> numbers;
        for (int i = 1; i < n; ++i) {
            factorial[i] = factorial[i - 1] * i;
        }
        for (int i = 1; i <= n; ++i) {
            numbers.push_back(i);
        }
        
        --k; // convert k to zero-based
        string result;
        
        for (int i = n; i > 0; --i) {
            int idx = k / factorial[i - 1];
            result.push_back(numbers[idx] + '0');
            numbers.erase(numbers.begin() + idx);
            k -= idx * factorial[i - 1];
        }
        
        return result;
    }
};

Java Implementation

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

class Solution {
    public String getPermutation(int n, int k) {
        List<Integer> numbers = new ArrayList<>();
        int[] factorial = new int[n];
        factorial[0] = 1;
        
        for (int i = 1; i < n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }
        
        for (int i = 1; i <= n; i++) {
            numbers.add(i);
        }
        
        k--; // convert k to zero-based
        StringBuilder result = new StringBuilder();
        
        for (int i = n; i > 0; i--) {
            int idx = k / factorial[i - 1];
            result.append(numbers.get(idx));
            numbers.remove(idx);
            k -= idx * factorial[i - 1];
        }
        
        return result.toString();
    }
}

Time and Space Complexity Analysis

Time Complexity: O(n^2)
- Although we iteratively compute the permutations in O(n) with O(n) retrieval of elements using erase operation in a list or array, the whole process is reasonably efficient for n up to 9 due to factorial product bounds on feasible computational steps involved at each stage.
Space Complexity: O(n)
- This involves storing factorial tables and managing a list of numbers for permutations, thus utilizing linear space.

Common Mistakes to Avoid

Failing to convert k to zero-based indexing may lead to off-by-one errors.
Using a solution that attempts to generate all permutations directly might lead to timeouts, especially for larger n.

Additional Resources and References

Here are some resources to understand and visualize permutations and factorial concepts:

Understanding permutations and using factorial number system insight can give a significant edge in solving similar combinatorial problems efficiently.