Permutation Sequence solution in Python

Quick Links

Problem Description

Ah, the classic “Permutation Sequence” problem! Imagine you have a group of friends, and you want to arrange them in every possible order for a group photo. But wait! You only care about the k-th arrangement. Why? Because you’re too lazy to scroll through all the permutations. You just want to know which one is the k-th!

In LeetCode terms, the problem is defined as follows: Given two integers n and k, return the k-th permutation sequence of the numbers from 1 to n. So, if you have 3 friends (1, 2, and 3), the permutations are:

If k = 4, you’d get “231”. Easy peasy, right?

Code Solution


class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        ans = ''
        nums = [i + 1 for i in range(n)]
        fact = [1] * (n + 1)  # fact[i] := i!

        for i in range(2, n + 1):
            fact[i] = fact[i - 1] * i

        k -= 1  # 0-indexed

        for i in reversed(range(n)):
            j = k // fact[i]
            k %= fact[i]
            ans += str(nums[j])
            nums.pop(j)

        return ans

Approach Explanation

The approach taken in the code is quite clever! It uses the concept of factorials to determine the position of each number in the permutation sequence. Here’s a brief breakdown:

Factorial Precomputation: First, we compute the factorials of numbers from 1 to n. This helps us determine how many permutations can be formed with the remaining numbers.
Index Calculation: We adjust k to be zero-indexed (because we humans start counting from 1, but computers start from 0). Then, for each position in the result, we determine which number should be placed there by dividing k by the factorial of the remaining numbers.
Updating k: After placing a number, we update k to find the next number’s position.
Pop the Number: Finally, we remove the used number from the list to avoid repetition.

Time and Space Complexity

Time Complexity: O(n²) – The loop runs n times, and each pop operation takes O(n) in the worst case.

Space Complexity: O(n) – We use an array to store the numbers and another for factorials.

Real-World Example

Imagine you’re organizing a talent show with n participants. You want to know the order in which they will perform based on a specific position k. Instead of listing all possible orders (which could take forever), you can use the permutation sequence approach to find out the k-th order directly.