Jobs

Interviews

Discussions

Permutation Sequence

Hard

Asked by:

More companies

75 views

Topics:

ArraysStringsRecursionGreedy Algorithms

The set [1, 2, 3, ..., n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, return the k^th permutation sequence.

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

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

Example 3:

Input: n = 3, k = 1
Output: "123"

Constraints:

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

Try coding it in LeetCode

Permutation Sequence

Hard

Asked by:

75 views

Topics:

ArraysStringsRecursionGreedy Algorithms

The set [1, 2, 3, ..., n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, return the k^th permutation sequence.

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

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

Example 3:

Input: n = 3, k = 1
Output: "123"

Constraints:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the valid ranges for 'n' and 'k'?
Is 'k' guaranteed to be within the valid range of permutations (1 to n!)?
Can 'n' be 0 or 1, and how should the function behave in those cases?
The problem statement uses 'kth permutation sequence'. Is 'k' 1-indexed or 0-indexed?
Are we expected to handle very large values of 'n' where n! might exceed standard integer limits during intermediate calculations?

Brute Force Solution

Approach

The brute force approach to finding a specific arrangement of numbers involves generating every single possible order of those numbers. Then, for each generated order, we check if it's the specific one we're looking for.

Here's how the algorithm would work step-by-step:

First, think about all the different ways you can arrange the given set of numbers.
For each arrangement you create, carefully compare it to the target arrangement you need to find.
If an arrangement matches the target exactly, you've found your answer.
If it doesn't match, discard that arrangement and move on to the next one.
Continue this process of generating and comparing until you find the matching arrangement.

Code Implementation

import itertoolsdef find_permutation_sequence_brute_force(numbers_to_permute, target_sequence):    # Generating all permutations is the first step in a brute-force search.    # This ensures we explore every possible arrangement.    all_possible_permutations = list(itertools.permutations(numbers_to_permute))    # We need to iterate through each generated permutation to check for a match.    for current_permutation in all_possible_permutations:        # Comparing the current permutation to the target is how we identify the desired sequence.        if list(current_permutation) == target_sequence:            # Returning the matching permutation immediately stops the search once found.            return list(current_permutation)    # If no permutation matches the target, it means the target is not achievable.    return None

Big(O) Analysis

Time Complexity

O(n * n!) – The approach generates all possible permutations of the n numbers, and there are n! (n factorial) such permutations. For each permutation generated, we compare it to the target sequence, which takes O(n) time. Therefore, the total time complexity is the number of permutations multiplied by the time to compare each permutation, resulting in O(n * n!).

Space Complexity

O(N!) – The brute force approach involves generating all possible permutations. Storing these permutations, even temporarily, would require space proportional to the number of permutations, which is N!. As N increases, the memory needed to hold these arrangements grows factorially. Thus, the auxiliary space complexity is O(N!).

Optimal Solution

Approach

Instead of generating all possible arrangements and then picking the correct one, this approach cleverly determines which character belongs in each position directly. It leverages the mathematical properties of permutations and factorials to make informed decisions.

Here's how the algorithm would work step-by-step:

First, determine how many possible arrangements can be made with the remaining characters.
Divide the target arrangement number by the count of arrangements for the subsequent characters to figure out which group the correct arrangement falls into.
The result of this division tells you which of the available characters should be placed in the current position of the final arrangement.
Once a character is chosen for the current position, remove it from the set of available characters.
Adjust the target arrangement number to reflect the sub-problem of finding the correct arrangement within the chosen group.
Repeat this process for each position in the final arrangement, narrowing down the choices until all characters are placed.
Continue until all positions are filled and you have constructed the exact target arrangement.

Code Implementation

import math

def get_permutation_sequence(number_of_elements, target_sequence_index):
    available_numbers = list(range(1, number_of_elements + 1))
    permutation_result = []
    # Adjust index to be 0-based for easier calculations.
    target_sequence_index -= 1

    for current_position in range(number_of_elements, 0, -1):
        # Calculate factorial for remaining elements to determine group size.
        factorial_of_remaining = math.factorial(current_position - 1)
        # Determine which available number to pick based on index and group size.
        picked_number_index = target_sequence_index // factorial_of_remaining
        # Append the chosen number to the result.
        permutation_result.append(available_numbers.pop(picked_number_index))
        # Update the index to find the correct permutation within the chosen group.
        target_sequence_index %= factorial_of_remaining

    return ''.join(map(str, permutation_result))

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n positions in the permutation sequence. Within each iteration, it calculates the factorial of the remaining characters, which takes constant time for small n (up to 12 for typical interview constraints) or can be precomputed. Then, it performs a division and a subtraction to determine the correct character index and update the target number. The dominant cost comes from managing the list of available characters. Specifically, finding and removing a character from a list of available candidates typically takes O(k) time, where k is the number of remaining characters. Since k decreases from n-1 down to 1, the total time for character selection and removal across all n positions becomes approximately the sum of 1 + 2 + ... + (n-1), which is O(n²).

Space Complexity

O(n) – The solution requires an auxiliary data structure to store the available characters, which initially contains n characters. As characters are selected and placed in the permutation, this list shrinks, but at any point, it holds at most n characters. Additionally, a factorial array of size n+1 might be precomputed or computed on the fly to assist in calculations. The primary driver of space complexity is the list of available characters, leading to an auxiliary space proportional to n.

Edge Cases

Case	How to Handle
n is 0 or negative	The problem statement implies n is a positive integer, but robust code might return an empty string or raise an error for invalid n.
k is 0 or negative	k is 1-indexed, so k <= 0 is an invalid input and should be handled with an error or an empty string.
k is larger than n!	If k exceeds the total number of permutations (n!), it's an invalid input and should result in an error or an empty string.
n = 1	For n=1, the only permutation is '1', so if k=1, return '1', otherwise it's an invalid k.
n is large, leading to large factorial values	Use a data type that can handle large factorials, like `long long` in C++ or Python's arbitrary-precision integers, to prevent overflow.
All numbers from 1 to n are used exactly once	The factorial-based approach naturally handles this by distributing elements based on factorials.
Input k is very close to 1 or n!	The algorithm should correctly identify the first and last permutations respectively.
Maximum recursion depth for a recursive permutation generation approach	A non-recursive, factorial-based approach is preferred for this problem to avoid stack overflow issues with large n.

n is 0 or negative

How to Handle:

The problem statement implies n is a positive integer, but robust code might return an empty string or raise an error for invalid n.

k is 0 or negative

How to Handle:

k is 1-indexed, so k <= 0 is an invalid input and should be handled with an error or an empty string.

k is larger than n!

How to Handle:

If k exceeds the total number of permutations (n!), it's an invalid input and should result in an error or an empty string.

n = 1

How to Handle:

For n=1, the only permutation is '1', so if k=1, return '1', otherwise it's an invalid k.

n is large, leading to large factorial values

How to Handle:

Use a data type that can handle large factorials, like `long long` in C++ or Python's arbitrary-precision integers, to prevent overflow.

All numbers from 1 to n are used exactly once

How to Handle:

The factorial-based approach naturally handles this by distributing elements based on factorials.

Input k is very close to 1 or n!

How to Handle:

The algorithm should correctly identify the first and last permutations respectively.

Maximum recursion depth for a recursive permutation generation approach

How to Handle:

A non-recursive, factorial-based approach is preferred for this problem to avoid stack overflow issues with large n.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the valid ranges for 'n' and 'k'?
Is 'k' guaranteed to be within the valid range of permutations (1 to n!)?
Can 'n' be 0 or 1, and how should the function behave in those cases?
The problem statement uses 'kth permutation sequence'. Is 'k' 1-indexed or 0-indexed?
Are we expected to handle very large values of 'n' where n! might exceed standard integer limits during intermediate calculations?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, think about all the different ways you can arrange the given set of numbers.
For each arrangement you create, carefully compare it to the target arrangement you need to find.
If an arrangement matches the target exactly, you've found your answer.
If it doesn't match, discard that arrangement and move on to the next one.
Continue this process of generating and comparing until you find the matching arrangement.

Code Implementation

import itertoolsdef find_permutation_sequence_brute_force(numbers_to_permute, target_sequence):    # Generating all permutations is the first step in a brute-force search.    # This ensures we explore every possible arrangement.    all_possible_permutations = list(itertools.permutations(numbers_to_permute))    # We need to iterate through each generated permutation to check for a match.    for current_permutation in all_possible_permutations:        # Comparing the current permutation to the target is how we identify the desired sequence.        if list(current_permutation) == target_sequence:            # Returning the matching permutation immediately stops the search once found.            return list(current_permutation)    # If no permutation matches the target, it means the target is not achievable.    return None

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, determine how many possible arrangements can be made with the remaining characters.
Divide the target arrangement number by the count of arrangements for the subsequent characters to figure out which group the correct arrangement falls into.
The result of this division tells you which of the available characters should be placed in the current position of the final arrangement.
Once a character is chosen for the current position, remove it from the set of available characters.
Adjust the target arrangement number to reflect the sub-problem of finding the correct arrangement within the chosen group.
Repeat this process for each position in the final arrangement, narrowing down the choices until all characters are placed.
Continue until all positions are filled and you have constructed the exact target arrangement.

Code Implementation

import math

def get_permutation_sequence(number_of_elements, target_sequence_index):
    available_numbers = list(range(1, number_of_elements + 1))
    permutation_result = []
    # Adjust index to be 0-based for easier calculations.
    target_sequence_index -= 1

    for current_position in range(number_of_elements, 0, -1):
        # Calculate factorial for remaining elements to determine group size.
        factorial_of_remaining = math.factorial(current_position - 1)
        # Determine which available number to pick based on index and group size.
        picked_number_index = target_sequence_index // factorial_of_remaining
        # Append the chosen number to the result.
        permutation_result.append(available_numbers.pop(picked_number_index))
        # Update the index to find the correct permutation within the chosen group.
        target_sequence_index %= factorial_of_remaining

    return ''.join(map(str, permutation_result))

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n is 0 or negative	The problem statement implies n is a positive integer, but robust code might return an empty string or raise an error for invalid n.
k is 0 or negative	k is 1-indexed, so k <= 0 is an invalid input and should be handled with an error or an empty string.
k is larger than n!	If k exceeds the total number of permutations (n!), it's an invalid input and should result in an error or an empty string.
n = 1	For n=1, the only permutation is '1', so if k=1, return '1', otherwise it's an invalid k.
n is large, leading to large factorial values	Use a data type that can handle large factorials, like `long long` in C++ or Python's arbitrary-precision integers, to prevent overflow.
All numbers from 1 to n are used exactly once	The factorial-based approach naturally handles this by distributing elements based on factorials.
Input k is very close to 1 or n!	The algorithm should correctly identify the first and last permutations respectively.
Maximum recursion depth for a recursive permutation generation approach	A non-recursive, factorial-based approach is preferred for this problem to avoid stack overflow issues with large n.

n is 0 or negative

How to Handle:

The problem statement implies n is a positive integer, but robust code might return an empty string or raise an error for invalid n.

k is 0 or negative

How to Handle:

k is 1-indexed, so k <= 0 is an invalid input and should be handled with an error or an empty string.

k is larger than n!

How to Handle:

If k exceeds the total number of permutations (n!), it's an invalid input and should result in an error or an empty string.

n = 1

How to Handle:

For n=1, the only permutation is '1', so if k=1, return '1', otherwise it's an invalid k.

n is large, leading to large factorial values

How to Handle:

Use a data type that can handle large factorials, like `long long` in C++ or Python's arbitrary-precision integers, to prevent overflow.

All numbers from 1 to n are used exactly once

How to Handle:

The factorial-based approach naturally handles this by distributing elements based on factorials.

Input k is very close to 1 or n!

How to Handle:

The algorithm should correctly identify the first and last permutations respectively.

Maximum recursion depth for a recursive permutation generation approach

How to Handle:

A non-recursive, factorial-based approach is preferred for this problem to avoid stack overflow issues with large n.