Jobs

Interviews

Discussions

Permutation Sequence

Hard

Adobe

1 view

Topics:

ArraysStrings

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.

For example:

n = 3, k = 3 should return "213"
n = 4, k = 9 should return "2314"
n = 3, k = 1 should return "123"

Constraints:

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

Permutation Sequence

Hard

Adobe

1 view

Topics:

ArraysStrings

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.

For example:

n = 3, k = 3 should return "213"
n = 4, k = 9 should return "2314"
n = 3, k = 1 should return "123"

Constraints:

1 <= n <= 9
1 <= k <= 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 is the range of 'n' (the size of the permutation) and 'k' (the index of the desired permutation)?
Is 'n' always a positive integer? What happens if 'n' is zero or negative?
Is 'k' always a positive integer? What happens if 'k' is zero, negative, or larger than the total number of permutations?
Are the numbers used for the permutation guaranteed to be distinct, or can there be duplicates?
Can you provide a few examples of input (n, k) and their corresponding expected output permutation string?

Brute Force Solution

Approach

The goal is to find the kth permutation of a set of numbers. The brute force strategy involves generating all possible orderings (permutations) of the numbers and then simply picking the kth one from the complete list.

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

First, list out all the possible ways to arrange the numbers.
Make sure every single possible arrangement is included. For example, if the numbers are 1, 2, and 3, make sure you have 123, 132, 213, 231, 312, and 321.
Once you have this complete list of arrangements, count from the first arrangement until you get to the kth arrangement in the list.
The kth arrangement in your list is the answer.

Code Implementation

def permutation_sequence_brute_force(number_set_size, kth_permutation):

    numbers = list(range(1, number_set_size + 1))
    all_permutations = []

    def generate_permutations(current_permutation, remaining_numbers):
        if not remaining_numbers:
            all_permutations.append(current_permutation[:])
            return

        for index in range(len(remaining_numbers)):
            number = remaining_numbers[index]
            current_permutation.append(number)
            generate_permutations(current_permutation, remaining_numbers[:index] + remaining_numbers[index+1:])
            current_permutation.pop()

    generate_permutations([], numbers)

    # Sort to ensure permutations are in lexicographical order
    all_permutations.sort()

    # Adjust for zero-based indexing to get correct permutation
    return ''.join(map(str, all_permutations[kth_permutation - 1]))

Big(O) Analysis

Time Complexity

O(n!) – The described brute force approach generates all possible permutations of n numbers. Generating all permutations requires exploring every possible arrangement. There are n! (n factorial) such arrangements. After generating these permutations, the algorithm selects the kth permutation, which takes O(1) time. Therefore, the dominant cost is generating all permutations, resulting in a time complexity of O(n!).

Space Complexity

O(N!) – The brute force approach generates all possible permutations, storing them in a list to find the kth one. For a set of N numbers, there are N! permutations. Therefore, the auxiliary space required to store all these permutations scales with N!.

Optimal Solution

Approach

The goal is to find the correct permutation without generating all permutations. The key idea is to understand how factorials relate to the position of a number within a permutation sequence, and then use that to pick each number in the correct order.

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

Figure out how many permutations exist for each position if you fix a specific number at that position. This number is the factorial of the number of remaining slots.
Use the given position number to determine which digit comes first in the sequence. Divide the position number by the factorial to get an index, then select the number at that index from a list of available numbers.
After selecting a number, update the position number using the remainder from the division in the previous step. This updated position is now relative to the remaining unused numbers.
Repeat steps 2 and 3, each time considering one less digit until all positions have been filled. At each step, select the appropriate number based on the current position and remaining choices.
Concatenate the selected numbers to form the desired permutation sequence.

Code Implementation

def get_permutation(number, position):
    numbers = list(range(1, number + 1))
    permutation = ''
    position -= 1

    factorial = 1
    for i in range(1, number):
        factorial *= i

    for i in range(number - 1, -1, -1):
        # Determine the index of the number to select
        index = position // factorial
        permutation += str(numbers[index])
        numbers.pop(index)

        # Update the position for the remaining numbers
        position %= factorial

        if i > 0:
            factorial //= i

    return permutation

Big(O) Analysis

Time Complexity

O(n) – The solution iterates n times to determine each digit of the permutation. In each iteration, calculating the factorial takes constant time (or can be precomputed in O(n)), selecting the element from the list takes O(1) (if using a suitable data structure like a linked list for removals, which isn't explicitly stated but is a reasonable optimization), and the remaining operations are constant time. Therefore, the dominant operation is iterating n times to build the permutation, resulting in O(n) time complexity.

Space Complexity

O(N) – The algorithm uses a list of available numbers, which initially contains N integers. This list is modified in place, but it still contributes O(N) auxiliary space. Although the algorithm uses a few constant space variables, the dominant space usage comes from this list. Therefore, the overall space complexity is O(N).

Edge Cases

Case	How to Handle
n is 0 or negative	Return an empty string or throw an exception, as the problem is not defined for non-positive n.
k is 0 or negative	Throw an exception, as k must be a positive integer representing the kth permutation.
k is greater than n! (factorial of n)	Throw an exception or return an empty string, as k exceeds the total number of possible permutations.
n is 1	Return "1" since there is only one permutation.
n is large (e.g., n > 12)	Consider the potential for integer overflow when calculating factorials and use appropriate data types to mitigate it.
k is 1 (first permutation)	Return the sorted sequence of numbers from 1 to n in ascending order.
k is n! (last permutation)	Return the sequence of numbers from 1 to n in descending order.
Integer overflow calculating factorials	Use a data type with a larger range, such as long, or implement a factorial function that detects and handles overflow.

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 is the range of 'n' (the size of the permutation) and 'k' (the index of the desired permutation)?
Is 'n' always a positive integer? What happens if 'n' is zero or negative?
Is 'k' always a positive integer? What happens if 'k' is zero, negative, or larger than the total number of permutations?
Are the numbers used for the permutation guaranteed to be distinct, or can there be duplicates?
Can you provide a few examples of input (n, k) and their corresponding expected output permutation string?

Brute Force Solution

Approach

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

First, list out all the possible ways to arrange the numbers.
Make sure every single possible arrangement is included. For example, if the numbers are 1, 2, and 3, make sure you have 123, 132, 213, 231, 312, and 321.
Once you have this complete list of arrangements, count from the first arrangement until you get to the kth arrangement in the list.
The kth arrangement in your list is the answer.

Code Implementation

def permutation_sequence_brute_force(number_set_size, kth_permutation):

    numbers = list(range(1, number_set_size + 1))
    all_permutations = []

    def generate_permutations(current_permutation, remaining_numbers):
        if not remaining_numbers:
            all_permutations.append(current_permutation[:])
            return

        for index in range(len(remaining_numbers)):
            number = remaining_numbers[index]
            current_permutation.append(number)
            generate_permutations(current_permutation, remaining_numbers[:index] + remaining_numbers[index+1:])
            current_permutation.pop()

    generate_permutations([], numbers)

    # Sort to ensure permutations are in lexicographical order
    all_permutations.sort()

    # Adjust for zero-based indexing to get correct permutation
    return ''.join(map(str, all_permutations[kth_permutation - 1]))

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Figure out how many permutations exist for each position if you fix a specific number at that position. This number is the factorial of the number of remaining slots.
Use the given position number to determine which digit comes first in the sequence. Divide the position number by the factorial to get an index, then select the number at that index from a list of available numbers.
After selecting a number, update the position number using the remainder from the division in the previous step. This updated position is now relative to the remaining unused numbers.
Repeat steps 2 and 3, each time considering one less digit until all positions have been filled. At each step, select the appropriate number based on the current position and remaining choices.
Concatenate the selected numbers to form the desired permutation sequence.

Code Implementation

def get_permutation(number, position):
    numbers = list(range(1, number + 1))
    permutation = ''
    position -= 1

    factorial = 1
    for i in range(1, number):
        factorial *= i

    for i in range(number - 1, -1, -1):
        # Determine the index of the number to select
        index = position // factorial
        permutation += str(numbers[index])
        numbers.pop(index)

        # Update the position for the remaining numbers
        position %= factorial

        if i > 0:
            factorial //= i

    return permutation

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n is 0 or negative	Return an empty string or throw an exception, as the problem is not defined for non-positive n.
k is 0 or negative	Throw an exception, as k must be a positive integer representing the kth permutation.
k is greater than n! (factorial of n)	Throw an exception or return an empty string, as k exceeds the total number of possible permutations.
n is 1	Return "1" since there is only one permutation.
n is large (e.g., n > 12)	Consider the potential for integer overflow when calculating factorials and use appropriate data types to mitigate it.
k is 1 (first permutation)	Return the sorted sequence of numbers from 1 to n in ascending order.
k is n! (last permutation)	Return the sequence of numbers from 1 to n in descending order.
Integer overflow calculating factorials	Use a data type with a larger range, such as long, or implement a factorial function that detects and handles overflow.