Jobs

Interviews

Discussions

Find Permutation

Medium

Asked by:

19 views

Topics:

ArraysStringsGreedy AlgorithmsTwo Pointers

By now, you are given a positive integer n, which indicates that the permutation should contain integers from 1 to n.

Let me tell you a secret, now you will be given a string s of length n - 1, which contains character 'I' (increasing) or 'D' (decreasing), indicates that the relationship between two adjacent numbers in the permutation.

Given the string s, return any permutation of integers from 1 to n that satisfies the given string s.

Example 1:

Input: s = "IDID"
Output: [0,4,1,3,2]

Example 2:

Input: s = "III"
Output: [0,1,2,3]

Example 3:

Input: s = "DDI"
Output: [3,2,0,1]

Constraints:

1 <= s.length <= 10⁵
s[i] is either 'I' or 'D'.

Try coding it in LeetCode

Find Permutation

Medium

Asked by:

19 views

Topics:

ArraysStringsGreedy AlgorithmsTwo Pointers

By now, you are given a positive integer n, which indicates that the permutation should contain integers from 1 to n.

Given the string s, return any permutation of integers from 1 to n that satisfies the given string s.

Example 1:

Input: s = "IDID"
Output: [0,4,1,3,2]

Example 2:

Input: s = "III"
Output: [0,1,2,3]

Example 3:

Input: s = "DDI"
Output: [3,2,0,1]

Constraints:

1 <= s.length <= 10⁵
s[i] is either 'I' or 'D'.

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 is the range of values for 'n' and what is the expected type (integer)?
Can the input string 's' contain characters other than 'I' and 'D'?
If multiple permutations satisfy the condition, is any valid permutation acceptable, or is there a specific criteria for choosing one?
What should be returned if the input string 's' is empty?
Is 'n' always guaranteed to be one greater than the length of the string 's'?

Brute Force Solution

Approach

The brute force method for finding a permutation involves exploring every single possible arrangement. We generate all possible permutations and check each one to see if it satisfies the given condition. If it does, we've found our answer; if not, we move on to the next arrangement.

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

Start by listing out all the possible ways to arrange the available items.
Take the first arrangement and check if it meets the required conditions.
If the arrangement satisfies the condition, we can stop, we have found our solution.
If the arrangement doesn't satisfy the condition, discard it and move on to the next possible arrangement.
Repeat steps two through four until we find an arrangement that works or we have exhausted all possibilities.

Code Implementation

def find_permutation_brute_force(pattern): 
    sequence_length = len(pattern) 
    numbers = list(range(1, sequence_length + 1)) 
    import itertools 

    for permutation in itertools.permutations(numbers): 
        # Check each permutation against the pattern

        satisfies_pattern = True
        for index in range(sequence_length - 1): 
            if (pattern[index] == 'I' and permutation[index] > permutation[index + 1]) or \
               (pattern[index] == 'D' and permutation[index] < permutation[index + 1]):
                satisfies_pattern = False
                break

        # Return immediately upon finding the first valid permutation

        if satisfies_pattern: 
            return list(permutation)

    # Return an empty list if no permutation satisfies the pattern
    return []

Big(O) Analysis

Time Complexity

O(n! * n) – The brute force approach generates all possible permutations of the input. Generating all permutations of n items takes O(n!) time. For each of the n! permutations generated, we need to check if it satisfies the given condition. Assuming the condition check takes O(n) time (as we need to potentially iterate through each element of the permutation), the overall time complexity becomes O(n! * n).

Space Complexity

O(N) – The brute force algorithm generates all possible permutations. While the provided description does not explicitly state how permutations are generated, a common implementation involves recursion. Each recursive call creates a new stack frame. In the worst-case scenario, the depth of the recursion can go up to N, where N is the number of items to permute, leading to N stack frames. Each stack frame stores temporary variables and function call information, resulting in O(N) space usage. The algorithm also requires space to store the single permutation currently being explored which can be done in-place, which does not require extra memory to store, or copying into extra memory that would need to be taken into account.

Optimal Solution

Approach

The puzzle wants us to create a number sequence from a pattern of increasing and decreasing instructions. We can solve it efficiently by filling in the smallest or largest available number based on whether the pattern is increasing or decreasing at that point.

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

Start with a range of possible numbers, from 1 to the size required by the number of instructions plus one.
Look at the first instruction in the pattern. If it's an increasing instruction, select the smallest available number from the range and add it to the sequence.
If the instruction is decreasing, instead select the largest available number from the range and add it to the sequence.
Remove the chosen number from the range of possibilities.
Move on to the next instruction in the pattern and repeat the process of selecting the smallest or largest remaining number based on the new instruction.
Continue until you've used all the instructions and added the final number to the sequence, forming the correct permutation.

Code Implementation

def find_permutation(instruction_string):
    string_length = len(instruction_string)
    available_numbers = list(range(1, string_length + 2))
    result_permutation = []

    for instruction in instruction_string:
        # Choose smallest or largest based on I or D.
        if instruction == 'I':
            result_permutation.append(available_numbers[0])
            available_numbers.pop(0)

        else:
            # Decreasing, so choose the largest.
            result_permutation.append(available_numbers[-1])
            available_numbers.pop()

    # Add the last remaining number.
    result_permutation.append(available_numbers[0])
    return result_permutation

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string (pattern) of length n-1, where n is the length of the final permutation. In each iteration, it selects either the smallest or largest remaining number, effectively removing one number from the range of possible values. Selecting the smallest or largest available number from a sorted list (or maintaining indices for this purpose) can be done in constant time, or at worst, logarithmic time with more complex data structures like a heap. Since these operations within the loop are typically O(1) or O(log n), and the loop runs n-1 times, the dominant factor is the iteration itself. Thus, the overall time complexity is O(n), assuming efficient selection of min/max, or if using indices, O(1) for each lookup.

Space Complexity

O(N) – The algorithm uses a range of possible numbers. In the worst case, this range needs to store all numbers from 1 to N+1 where N is the length of the input string pattern. Thus, we are essentially creating an auxiliary list of size N+1, which simplifies to O(N) space complexity. Also, the output sequence which contains the final permutation contributes O(N) space as well. So the total auxiliary space is dominated by O(N).

Edge Cases

Case	How to Handle
Empty string s or invalid format string 'I' or 'D'	Return an empty list or null/None, or throw exception, as no permutation is possible.
String s contains characters other than 'I' or 'D'	Throw an exception as the input format is invalid.
Length of string s is larger than the maximum possible permutation size based on integer range.	Throw an exception or return null if the length exceeds a reasonable limit to prevent integer overflow during number generation.
String s only contains 'I' characters.	Create an ascending sequence from 1 to n+1, where n is the length of s.
String s only contains 'D' characters.	Create a descending sequence from n+1 to 1, where n is the length of s.
Input string 's' has the same number of 'I' and 'D' at the start	The chosen algorithm should still generate a valid sequence because it tracks and adjusts min/max values.
String s is very long causing integer overflow if not carefully handled during computation.	Use appropriate data types (e.g., long) or algorithm optimization to prevent potential integer overflows.
The length of the input string s is 0	Return an array containing only the number 1 as it satisfies the constraints.

Empty string s or invalid format string 'I' or 'D'

How to Handle:

Return an empty list or null/None, or throw exception, as no permutation is possible.

String s contains characters other than 'I' or 'D'

How to Handle:

Throw an exception as the input format is invalid.

Length of string s is larger than the maximum possible permutation size based on integer range.

How to Handle:

Throw an exception or return null if the length exceeds a reasonable limit to prevent integer overflow during number generation.

String s only contains 'I' characters.

How to Handle:

Create an ascending sequence from 1 to n+1, where n is the length of s.

String s only contains 'D' characters.

How to Handle:

Create a descending sequence from n+1 to 1, where n is the length of s.

Input string 's' has the same number of 'I' and 'D' at the start

How to Handle:

The chosen algorithm should still generate a valid sequence because it tracks and adjusts min/max values.

String s is very long causing integer overflow if not carefully handled during computation.

How to Handle:

Use appropriate data types (e.g., long) or algorithm optimization to prevent potential integer overflows.

The length of the input string s is 0

How to Handle:

Return an array containing only the number 1 as it satisfies the constraints.

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 values for 'n' and what is the expected type (integer)?
Can the input string 's' contain characters other than 'I' and 'D'?
If multiple permutations satisfy the condition, is any valid permutation acceptable, or is there a specific criteria for choosing one?
What should be returned if the input string 's' is empty?
Is 'n' always guaranteed to be one greater than the length of the string 's'?

Brute Force Solution

Approach

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

Start by listing out all the possible ways to arrange the available items.
Take the first arrangement and check if it meets the required conditions.
If the arrangement satisfies the condition, we can stop, we have found our solution.
If the arrangement doesn't satisfy the condition, discard it and move on to the next possible arrangement.
Repeat steps two through four until we find an arrangement that works or we have exhausted all possibilities.

Code Implementation

def find_permutation_brute_force(pattern): 
    sequence_length = len(pattern) 
    numbers = list(range(1, sequence_length + 1)) 
    import itertools 

    for permutation in itertools.permutations(numbers): 
        # Check each permutation against the pattern

        satisfies_pattern = True
        for index in range(sequence_length - 1): 
            if (pattern[index] == 'I' and permutation[index] > permutation[index + 1]) or \
               (pattern[index] == 'D' and permutation[index] < permutation[index + 1]):
                satisfies_pattern = False
                break

        # Return immediately upon finding the first valid permutation

        if satisfies_pattern: 
            return list(permutation)

    # Return an empty list if no permutation satisfies the pattern
    return []

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start with a range of possible numbers, from 1 to the size required by the number of instructions plus one.
Look at the first instruction in the pattern. If it's an increasing instruction, select the smallest available number from the range and add it to the sequence.
If the instruction is decreasing, instead select the largest available number from the range and add it to the sequence.
Remove the chosen number from the range of possibilities.
Move on to the next instruction in the pattern and repeat the process of selecting the smallest or largest remaining number based on the new instruction.
Continue until you've used all the instructions and added the final number to the sequence, forming the correct permutation.

Code Implementation

def find_permutation(instruction_string):
    string_length = len(instruction_string)
    available_numbers = list(range(1, string_length + 2))
    result_permutation = []

    for instruction in instruction_string:
        # Choose smallest or largest based on I or D.
        if instruction == 'I':
            result_permutation.append(available_numbers[0])
            available_numbers.pop(0)

        else:
            # Decreasing, so choose the largest.
            result_permutation.append(available_numbers[-1])
            available_numbers.pop()

    # Add the last remaining number.
    result_permutation.append(available_numbers[0])
    return result_permutation

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string s or invalid format string 'I' or 'D'	Return an empty list or null/None, or throw exception, as no permutation is possible.
String s contains characters other than 'I' or 'D'	Throw an exception as the input format is invalid.
Length of string s is larger than the maximum possible permutation size based on integer range.	Throw an exception or return null if the length exceeds a reasonable limit to prevent integer overflow during number generation.
String s only contains 'I' characters.	Create an ascending sequence from 1 to n+1, where n is the length of s.
String s only contains 'D' characters.	Create a descending sequence from n+1 to 1, where n is the length of s.
Input string 's' has the same number of 'I' and 'D' at the start	The chosen algorithm should still generate a valid sequence because it tracks and adjusts min/max values.
String s is very long causing integer overflow if not carefully handled during computation.	Use appropriate data types (e.g., long) or algorithm optimization to prevent potential integer overflows.
The length of the input string s is 0	Return an array containing only the number 1 as it satisfies the constraints.

Empty string s or invalid format string 'I' or 'D'

How to Handle:

Return an empty list or null/None, or throw exception, as no permutation is possible.

String s contains characters other than 'I' or 'D'

How to Handle:

Throw an exception as the input format is invalid.

Length of string s is larger than the maximum possible permutation size based on integer range.

How to Handle:

Throw an exception or return null if the length exceeds a reasonable limit to prevent integer overflow during number generation.

String s only contains 'I' characters.

How to Handle:

Create an ascending sequence from 1 to n+1, where n is the length of s.

String s only contains 'D' characters.

How to Handle:

Create a descending sequence from n+1 to 1, where n is the length of s.

Input string 's' has the same number of 'I' and 'D' at the start

How to Handle:

The chosen algorithm should still generate a valid sequence because it tracks and adjusts min/max values.

String s is very long causing integer overflow if not carefully handled during computation.

How to Handle:

Use appropriate data types (e.g., long) or algorithm optimization to prevent potential integer overflows.

The length of the input string s is 0

How to Handle:

Return an array containing only the number 1 as it satisfies the constraints.