Jobs

Interviews

Discussions

Permutations III

Medium

Asked by:

13 views

Topics:

RecursionArrays

Given an array of distinct integers nums, return all the possible permutations in lexicographical order.

You can return the answer in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

Constraints:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.

Try coding it in LeetCode

Permutations III

Medium

Asked by:

13 views

Topics:

RecursionArrays

Given an array of distinct integers nums, return all the possible permutations in lexicographical order.

You can return the answer in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

Constraints:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.

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 integer values within the `nums` array? Can I assume they will fit within a standard integer data type?
What should I do if the input array `nums` is empty or null?
Could you clarify the meaning of "lexicographical order" in the context of this problem? Should I assume ascending or descending order by default if a next greater permutation is not available?
Are the integers within the input array guaranteed to be distinct, as stated in the problem description?
The problem states to modify the array in-place. Does this mean I cannot use any extra space beyond a constant amount, or am I allowed a limited amount of auxiliary space?

Brute Force Solution

Approach

The brute force approach to finding all permutations is like trying out every possible arrangement. We explore each arrangement fully before moving on to the next, ensuring no possibility is missed. This exhaustive method guarantees we find the correct solution, but may take a long time.

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

Imagine you have a set of building blocks, each with a different number on it.
Start by picking one block to be the first in your arrangement.
Then, from the remaining blocks, pick another to be the second.
Continue picking blocks, one at a time, until you've used all the blocks and created a complete arrangement.
Write down that arrangement.
Now, go back and try a different first block.
Repeat the process of picking the remaining blocks in all possible orders to create new arrangements.
Do this until you've tried every block as the first one, and all combinations for each starting block.
You will then have a complete list of every possible arrangement of the blocks.

Code Implementation

def find_permutations_brute_force(input_list):
    permutations_list = []

    if not input_list:
        return [[]]

    first_element = input_list[0]
    remaining_elements = input_list[1:]

    # Recursively find permutations of remaining elements.
    sub_permutations = find_permutations_brute_force(remaining_elements)

    # Insert the first element at every possible position.
    for sub_permutation in sub_permutations:
        for index in range(len(sub_permutation) + 1):
            new_permutation = sub_permutation[:index] + [first_element] + sub_permutation[index:]
            permutations_list.append(new_permutation)

    return permutations_list

Big(O) Analysis

Time Complexity

O(n!) – The algorithm explores all possible permutations of the input array. For an array of size n, there are n! (n factorial) possible permutations. The algorithm generates each of these permutations, and the time taken to generate each permutation is proportional to n (due to operations like copying the current permutation). Therefore, the overall time complexity is driven by the number of permutations, which is n! The creation of each permutation takes O(n) but doesn't affect the final Big O, so the dominating cost is the generation of the permutations themselves, resulting in O(n!).

Space Complexity

O(N) – The algorithm uses recursion to explore each possible arrangement. The maximum depth of the recursion is N, where N is the number of blocks, representing the size of the input. At each level of the recursion, we are essentially keeping track of which blocks have been used and the current partial arrangement. Therefore, the call stack can grow to a depth of N in the worst case, and the space used to maintain the stack frames contributes to O(N) space complexity. In addition, we can consider the step where the arrangements are written down can take O(N) space per arrangement.

Optimal Solution

Approach

To find all possible arrangements, the key is to build them step by step by making small choices. At each step, we'll pick an element and then find all the ways to arrange the rest, repeating this until we have every possible arrangement. We also ensure that we don't repeat any arrangements.

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

Start with an empty collection to store all the unique arrangements we find.
Begin by picking the first element from the initial set of elements.
After picking the first element, find all the arrangements of the remaining elements. This is done by calling the same procedure on the remaining elements.
For each arrangement of the remaining elements, add the originally picked element to the beginning of each of those arrangements.
Once we've built a complete arrangement, add it to our collection of unique arrangements.
Repeat this process for every element in the initial set. That is, each element gets a turn to be the 'first' element.
When repeating, avoid duplicate elements to prevent duplicate arrangements. For instance, if your elements are [1, 2, 2], make sure the '2's are treated as the same when chosen as the first element to build the arrangement.
After going through this process for all elements, the collection will contain every possible unique arrangement.

Code Implementation

def find_all_permutations(items):
    result_permutations = []
    number_of_items = len(items)
    used_items = [False] * number_of_items
    current_permutation = []

    def backtrack():
        # If we've used all items, add the permutation to the result.
        if len(current_permutation) == number_of_items:
            result_permutations.append(current_permutation[:] )
            return

        for item_index in range(number_of_items):
            # Only process if the item hasn't been used yet.
            if not used_items[item_index]:
                current_permutation.append(items[item_index])
                used_items[item_index] = True

                # Recursively build the rest of the permutation.
                backtrack()

                # Backtrack: remove the last item and mark it as unused.
                current_permutation.pop()
                used_items[item_index] = False

    # Initiate the backtracking process.
    backtrack()

    return result_permutations

Big(O) Analysis

Time Complexity

O(n!) – The algorithm generates all possible permutations of the input array of size n. The number of permutations of n distinct elements is n! (n factorial). The algorithm explores each of these n! permutations. For each permutation, it takes O(n) time to construct it (e.g., adding elements to a list). Therefore, the total time complexity is O(n * n!). However, the problem specifies that it avoids duplicate elements, reducing the number of generated permutations in the case when the input has duplicate elements. But even in the presence of duplicates the worst-case scenario where all elements are distinct still requires the generation of n! permutations. Since the generation of n! permutations dominates the time complexity, the overall time complexity remains O(n!).

Space Complexity

O(N^2) – The algorithm uses recursion, and the depth of the recursion can go up to N, where N is the number of elements in the initial set. Each level of recursion stores a copy of the current arrangement being built, which has a maximum size of N. Additionally, the collection to store unique arrangements can contain up to N! arrangements, but since we're considering auxiliary space, it's more accurate to consider the space used to build each arrangement which is O(N) in the worst case and since each level has a copy, it's N deep, the auxiliary space becomes O(N * N) = O(N^2). Therefore, the auxiliary space complexity is O(N^2).

Edge Cases

Case	How to Handle
Empty or null input array	Return the empty array immediately as there is no permutation to find.
Input array with a single element	The next greater permutation is the array itself, so return the array unchanged.
Input array sorted in descending order (largest to smallest)	Reverse the array to get the smallest possible permutation (ascending order).
Input array already in ascending order (smallest to largest)	Find the rightmost element that is smaller than its right neighbor, which in this case will be the second to last element and swap it with the last.
Input array with duplicate numbers	The algorithm should still work correctly as it relies on finding the next greater element and swapping.
Input array with all identical numbers	Reverse the array since no larger permutation is possible.
Large input array (performance consideration)	The algorithm has O(n) time complexity, which scales reasonably well for larger inputs.
Integer overflow during swap (unlikely but possible with very large numbers)	While unlikely with standard integer sizes and constraints, ensure integer size limits are understood, or consider using larger data types if required.

Empty or null input array

How to Handle:

Return the empty array immediately as there is no permutation to find.

Input array with a single element

How to Handle:

The next greater permutation is the array itself, so return the array unchanged.

Input array sorted in descending order (largest to smallest)

How to Handle:

Reverse the array to get the smallest possible permutation (ascending order).

Input array already in ascending order (smallest to largest)

How to Handle:

Find the rightmost element that is smaller than its right neighbor, which in this case will be the second to last element and swap it with the last.

Input array with duplicate numbers

How to Handle:

The algorithm should still work correctly as it relies on finding the next greater element and swapping.

Input array with all identical numbers

How to Handle:

Reverse the array since no larger permutation is possible.

Large input array (performance consideration)

How to Handle:

The algorithm has O(n) time complexity, which scales reasonably well for larger inputs.

Integer overflow during swap (unlikely but possible with very large numbers)

How to Handle:

While unlikely with standard integer sizes and constraints, ensure integer size limits are understood, or consider using larger data types if required.

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 integer values within the `nums` array? Can I assume they will fit within a standard integer data type?
What should I do if the input array `nums` is empty or null?
Could you clarify the meaning of "lexicographical order" in the context of this problem? Should I assume ascending or descending order by default if a next greater permutation is not available?
Are the integers within the input array guaranteed to be distinct, as stated in the problem description?
The problem states to modify the array in-place. Does this mean I cannot use any extra space beyond a constant amount, or am I allowed a limited amount of auxiliary space?

Brute Force Solution

Approach

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

Imagine you have a set of building blocks, each with a different number on it.
Start by picking one block to be the first in your arrangement.
Then, from the remaining blocks, pick another to be the second.
Continue picking blocks, one at a time, until you've used all the blocks and created a complete arrangement.
Write down that arrangement.
Now, go back and try a different first block.
Repeat the process of picking the remaining blocks in all possible orders to create new arrangements.
Do this until you've tried every block as the first one, and all combinations for each starting block.
You will then have a complete list of every possible arrangement of the blocks.

Code Implementation

def find_permutations_brute_force(input_list):
    permutations_list = []

    if not input_list:
        return [[]]

    first_element = input_list[0]
    remaining_elements = input_list[1:]

    # Recursively find permutations of remaining elements.
    sub_permutations = find_permutations_brute_force(remaining_elements)

    # Insert the first element at every possible position.
    for sub_permutation in sub_permutations:
        for index in range(len(sub_permutation) + 1):
            new_permutation = sub_permutation[:index] + [first_element] + sub_permutation[index:]
            permutations_list.append(new_permutation)

    return permutations_list

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start with an empty collection to store all the unique arrangements we find.
Begin by picking the first element from the initial set of elements.
After picking the first element, find all the arrangements of the remaining elements. This is done by calling the same procedure on the remaining elements.
For each arrangement of the remaining elements, add the originally picked element to the beginning of each of those arrangements.
Once we've built a complete arrangement, add it to our collection of unique arrangements.
Repeat this process for every element in the initial set. That is, each element gets a turn to be the 'first' element.
When repeating, avoid duplicate elements to prevent duplicate arrangements. For instance, if your elements are [1, 2, 2], make sure the '2's are treated as the same when chosen as the first element to build the arrangement.
After going through this process for all elements, the collection will contain every possible unique arrangement.

Code Implementation

def find_all_permutations(items):
    result_permutations = []
    number_of_items = len(items)
    used_items = [False] * number_of_items
    current_permutation = []

    def backtrack():
        # If we've used all items, add the permutation to the result.
        if len(current_permutation) == number_of_items:
            result_permutations.append(current_permutation[:] )
            return

        for item_index in range(number_of_items):
            # Only process if the item hasn't been used yet.
            if not used_items[item_index]:
                current_permutation.append(items[item_index])
                used_items[item_index] = True

                # Recursively build the rest of the permutation.
                backtrack()

                # Backtrack: remove the last item and mark it as unused.
                current_permutation.pop()
                used_items[item_index] = False

    # Initiate the backtracking process.
    backtrack()

    return result_permutations

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return the empty array immediately as there is no permutation to find.
Input array with a single element	The next greater permutation is the array itself, so return the array unchanged.
Input array sorted in descending order (largest to smallest)	Reverse the array to get the smallest possible permutation (ascending order).
Input array already in ascending order (smallest to largest)	Find the rightmost element that is smaller than its right neighbor, which in this case will be the second to last element and swap it with the last.
Input array with duplicate numbers	The algorithm should still work correctly as it relies on finding the next greater element and swapping.
Input array with all identical numbers	Reverse the array since no larger permutation is possible.
Large input array (performance consideration)	The algorithm has O(n) time complexity, which scales reasonably well for larger inputs.
Integer overflow during swap (unlikely but possible with very large numbers)	While unlikely with standard integer sizes and constraints, ensure integer size limits are understood, or consider using larger data types if required.

Empty or null input array

How to Handle:

Return the empty array immediately as there is no permutation to find.

Input array with a single element

How to Handle:

The next greater permutation is the array itself, so return the array unchanged.

Input array sorted in descending order (largest to smallest)

How to Handle:

Reverse the array to get the smallest possible permutation (ascending order).

Input array already in ascending order (smallest to largest)

How to Handle:

Find the rightmost element that is smaller than its right neighbor, which in this case will be the second to last element and swap it with the last.

Input array with duplicate numbers

How to Handle:

The algorithm should still work correctly as it relies on finding the next greater element and swapping.

Input array with all identical numbers

How to Handle:

Reverse the array since no larger permutation is possible.

Large input array (performance consideration)

How to Handle:

The algorithm has O(n) time complexity, which scales reasonably well for larger inputs.

Integer overflow during swap (unlikely but possible with very large numbers)

How to Handle:

While unlikely with standard integer sizes and constraints, ensure integer size limits are understood, or consider using larger data types if required.