NUHMAN.com

Introduction

LeetCode 60: Permutation Sequence is an interesting problem that challenges your understanding of combinatorics and factorial number systems. Given a number n and a position k, you're asked to find the k-th lexicographically smallest permutation of numbers from 1 to n.

This problem tests your ability to efficiently generate the k-th permutation without generating all permutations, especially when the size of n can go up to 9.

Problem Statement

Given two integers n and k, return the k-th permutation sequence of the numbers from 1 to n.

Example 1:

go

Input: n = 3, k = 3
Output: "213"
Explanation: The permutations of [1,2,3] in lexicographical order are:
  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"
The 3rd permutation is "213".

Example 2:

go

Input: n = 4, k = 9
Output: "2314"

Constraints

• 1 <= n <= 9
• 1 <= k <= n! (Factorial of n)

Approach: Factorial Number System

The idea behind solving this problem is based on the factorial number system, where you break the problem down into smaller subproblems using factorials. By using this approach, you can directly find the k-th permutation without generating all permutations.

Key Steps:

1. Start with the numbers [1, 2, ..., n].
2. Find the block size at each step: (n-1)!, and use it to determine which element should be at the current position.
3. Adjust k and repeat the process until the entire permutation is constructed.

Go Implementation

go

import "strconv"

func getPermutation(n int, k int) string {
    // Create a list of numbers to get permutations from
    nums := []int{}
    for i := 1; i <= n; i++ {
        nums = append(nums, i)
    }

    // Adjust k to be zero-indexed
    k--

    // Calculate factorial values for all numbers from 1 to n
    fact := make([]int, n)
    fact[0] = 1
    for i := 1; i < n; i++ {
        fact[i] = fact[i-1] * (i + 1)
    }

    result := ""

    // Generate the k-th permutation
    for i := 0; i < n; i++ {
        idx := k / fact[n-i-1]  // Determine the index of the current element
        result += strconv.Itoa(nums[idx]) // Add the element to result
        nums = append(nums[:idx], nums[idx+1:]...) // Remove the used element
        k -= idx * fact[n-i-1] // Update k
    }

    return result
}

Example Walkthrough

Given n = 3 and k = 3, we want to find the 3rd permutation of numbers [1, 2, 3]:

1. Initial numbers: [1, 2, 3]
2. Factorials: (n-1)! = 2! = 2, 2! = 2
3. Calculate the first element:

• k = 3, so 3 / 2 = 1, so the first element is 2. The remaining numbers are [1, 3], and update k = 3 - 1 * 2 = 1.

1. Next, calculate for the remaining numbers [1, 3]:

• k = 1, so 1 / 1 = 0, so the next element is 1. The remaining number is [3], and update k = 1 - 0 * 1 = 1.

1. The last element is 3.

Final result: "213"

Time and Space Complexity

MetricComplexityTime ComplexityO(n²)Space ComplexityO(n)

• The algorithm processes n elements, each taking at most O(n) time due to the removal of elements from the list, leading to an overall time complexity of O(n²).
• The space complexity is O(n) due to storing the numbers in a list.

Edge Cases

• k = 1: The first permutation is simply the sorted sequence [1, 2, ..., n].
• k = n!: The last permutation is the sequence [n, n-1, ..., 1].
• Small values of n: Handles edge cases where n is very small, such as n = 1.

Key Takeaways

• The factorial number system helps directly calculate the k-th permutation without generating all permutations.
• Efficient indexing and element removal using factorial values is the core technique.
• This problem is a great practice for understanding combinatorial problems and factorials.