#60

Hard

LeetCode Problem Workspace

Permutation Sequence

Find the kth permutation sequence of a set of numbers using math and recursion to efficiently compute the result.

Problem Statement

Given an integer n, the set [1, 2, 3, ..., n] contains a total of n! unique permutations. These permutations can be ordered lexicographically, and each position in the sequence can be computed using a factorial system.

You are given n and an integer k, and you need to find the kth permutation sequence of the set [1, 2, ..., n]. You must return the permutation in the form of a string of numbers.

Examples

Example 1

Input: n = 3, k = 3

Output: "213"

Example details omitted.

Example 2

Input: n = 4, k = 9

Output: "2314"

Example details omitted.

Example 3

Input: n = 3, k = 1

Output: "123"

Example details omitted.

Constraints

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

Solution Approach

Understand Factorial System

The key to solving the problem is recognizing that the kth permutation can be derived using a factorial system. Each block of permutations corresponds to a fixed number of possibilities. For instance, with n=3, the first 2 permutations will start with the first number, and the next 2 start with the second number, etc.

Recursive Position Calculation

Using recursion, you can iteratively determine the next number in the sequence by calculating the index within a reduced set of available numbers. Factorial division helps determine the appropriate number for each position.

Efficient Permutation Generation

Instead of generating all permutations and selecting the kth one, the recursive factorial approach directly calculates the kth permutation, reducing both time and space complexity.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity depend on the final approach used. With an efficient factorial approach, the time complexity is O(n), and space complexity is O(n) due to the recursive calls and number list tracking.

What Interviewers Usually Probe

Look for understanding of recursion and factorials.
Check for the ability to optimize with factorials instead of brute force generation.
Assess problem-solving by recursive breakdown of the sequence.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding how factorials divide the problem into smaller sections, leading to incorrect permutation generation.
Failing to adjust the set of available numbers as elements are selected, causing incorrect positions.
Overcomplicating the solution by generating all permutations before selecting the kth one.

Follow-up variants

Find the nth permutation in lexicographic order of a different range of numbers.
Use an iterative approach instead of recursion to find the kth permutation.
Return the kth permutation for very large values of n by optimizing factorial computations.

FAQ

How does recursion help solve the Permutation Sequence problem?

Recursion simplifies the process of selecting each digit in the permutation by narrowing the choices at each step, using factorial-based division to determine the right number.

What is the time complexity of solving Permutation Sequence?

The time complexity is O(n), as the factorial approach allows for direct calculation of the permutation without generating all permutations.

Can we solve the Permutation Sequence problem iteratively?

Yes, it is possible to solve it iteratively by using factorial division in a loop to select numbers for each position in the sequence.

What is the key concept behind solving Permutation Sequence?

The key concept is using the factorial system to reduce the problem, and applying recursion or iteration to determine the kth permutation in the sequence.

How does GhostInterview assist with the Permutation Sequence problem?

GhostInterview helps you understand the recursive factorial approach and avoid common mistakes, making the process of solving the Permutation Sequence efficient and effective.

terminal

Solution

Solution 1: Enumeration

We know that the set $[1,2,..n]$ has a total of $n!$ permutations. If we determine the first digit, the number of permutations that the remaining digits can form is $(n-1)!$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        ans = []
        vis = [False] * (n + 1)
        for i in range(n):
            fact = 1
            for j in range(1, n - i):
                fact *= j
            for j in range(1, n + 1):
                if not vis[j]:
                    if k > fact:
                        k -= fact
                    else:
                        ans.append(str(j))
                        vis[j] = True
                        break
        return ''.join(ans)

Continue Practicing

#50 powx n #2 add two numbers #224 basic calculator