Code Implementation

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        import math
        numbers = [str(i) for i in range(1, n+1)]
        k -= 1  # Convert to 0-based index
        result = []
        for i in range(n, 0, -1):
            f = math.factorial(i-1)
            idx = k // f
            result.append(numbers.pop(idx))
            k %= f
        return ''.join(result)
      

class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> numbers;
        for (int i = 1; i <= n; ++i) numbers.push_back(i);
        string result = "";
        int fact = 1;
        for (int i = 2; i < n; ++i) fact *= i;
        --k; // 0-based index
        for (int i = n - 1; i >= 0; --i) {
            int idx = k / fact;
            result += to_string(numbers[idx]);
            numbers.erase(numbers.begin() + idx);
            if (i != 0) k %= fact, fact /= (i == 0 ? 1 : i);
        }
        return result;
    }
};
      

class Solution {
    public String getPermutation(int n, int k) {
        List<Integer> numbers = new ArrayList<>();
        for (int i = 1; i <= n; i++) numbers.add(i);
        int fact = 1;
        for (int i = 2; i < n; i++) fact *= i;
        StringBuilder result = new StringBuilder();
        k--; // 0-based index
        for (int i = n - 1; i >= 0; i--) {
            int idx = k / fact;
            result.append(numbers.get(idx));
            numbers.remove(idx);
            if (i != 0) {
                k %= fact;
                fact /= i;
            }
        }
        return result.toString();
    }
}
      

var getPermutation = function(n, k) {
    let numbers = [];
    for (let i = 1; i <= n; i++) numbers.push(i);
    let fact = 1;
    for (let i = 2; i < n; i++) fact *= i;
    k--; // 0-based index
    let result = '';
    for (let i = n - 1; i >= 0; i--) {
        let idx = Math.floor(k / fact);
        result += numbers[idx];
        numbers.splice(idx, 1);
        if (i != 0) {
            k %= fact;
            fact = Math.floor(fact / i);
        }
    }
    return result;
};
      

Problem Description

Given two integers n and k, your task is to return the kth permutation sequence of the numbers from 1 to n in lexicographic order. Each number from 1 to n must appear exactly once in the sequence, and you must not reuse any element. Only one valid answer exists for each input.

• Input: Two integers, n (1 ≤ n ≤ 9) and k (1 ≤ k ≤ n!).
• Output: A string representing the kth permutation sequence.
• Constraints: Each digit is used exactly once; elements are not reused; only one valid sequence per input.

Thought Process

At first glance, this problem seems to require generating all possible permutations of the numbers 1 to n and then selecting the kth one. However, this brute-force approach is highly inefficient, especially as n grows, because the number of permutations (n!) increases rapidly.

Instead, we should look for a pattern or mathematical way to directly compute the kth permutation without generating all possible sequences. By understanding how permutations are ordered lexicographically, we can determine which digit should be placed at each position by using factorials to "skip" groups of permutations.

The key is to realize that the first digit changes every (n-1)! permutations, the second digit changes every (n-2)!, and so on. This allows us to determine each digit by dividing k by the appropriate factorial and updating our choices accordingly.

Solution Approach

• Step 1: Prepare the List of Numbers
  Create a list of numbers from 1 to n. This list will help us track which digits are still available for our permutation.
• Step 2: Adjust k for Zero-Based Indexing
  Since computer indices start from zero but k is one-based, subtract 1 from k to align with zero-based logic.
• Step 3: Build the Permutation
  For each position from left to right:
  • Compute the factorial of the number of remaining digits minus one. This tells us how many permutations start with each possible digit at this position.
  • Determine the index of the digit to use at the current position by dividing k by this factorial.
  • Pick the digit at that index from our list, add it to the result, and remove it from the list.
  • Update k to be the remainder after dividing by the factorial, so we focus on the next block of permutations.
• Step 4: Repeat
  Repeat the above process until all digits are used and the permutation is complete.

This approach ensures that we "jump" directly to the correct permutation, avoiding the need to generate all possible sequences.

Example Walkthrough

Let's use n = 4 and k = 9 as an example.

• Available numbers: [1, 2, 3, 4]
• k = 9 - 1 = 8 (zero-based)

1. First position:
   • Factorial of (4-1) = 6
   • Index = 8 // 6 = 1
   • Pick numbers[1] = 2 → result: "2"
   • Remove 2; numbers = [1, 3, 4]
   • k = 8 % 6 = 2
2. Second position:
   • Factorial of (3-1) = 2
   • Index = 2 // 2 = 1
   • Pick numbers[1] = 3 → result: "23"
   • Remove 3; numbers = [1, 4]
   • k = 2 % 2 = 0
3. Third position:
   • Factorial of (2-1) = 1
   • Index = 0 // 1 = 0
   • Pick numbers[0] = 1 → result: "231"
   • Remove 1; numbers = [4]
   • k = 0 % 1 = 0
4. Fourth position:
   • Only one number left: 4 → result: "2314"

So, the 9th permutation for n=4 is "2314".

Time and Space Complexity

• Brute-Force Approach:
  • Time Complexity: O(n!) – Because it generates all permutations.
  • Space Complexity: O(n!) – Stores all permutations.
• Optimized Approach (Current Solution):
  • Time Complexity: O(n²) – For each of n positions, we may need to remove an element from a list (O(n) per removal).
  • Space Complexity: O(n) – For the list of available numbers and the result.

The optimized approach is much more efficient, especially for larger values of n.

Summary

The problem asks for the kth permutation of the sequence 1 to n. Rather than generating all permutations, we use factorial math to directly determine each digit's position by "skipping" over blocks of permutations. This approach is efficient and elegant, reducing time and space complexity significantly. The main insight is recognizing how permutations are structured and using this to our advantage to build the required sequence step by step.