Jobs

Interviews

Discussions

Permutations

Medium

GoDaddy

2 views

Topics:

ArraysRecursion

Given an array nums of distinct integers, return all the possible permutations. 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.

Permutations

Medium

GoDaddy

2 views

Topics:

ArraysRecursion

Given an array nums of distinct integers, return all the possible permutations. 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.

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 maximum possible size of the input array nums?
Does the input array nums contain only positive integers, or can it include negative numbers or zero?
Are all the integers in the input array nums guaranteed to be distinct, as stated in the problem description?
Is the order of the permutations in the output significant, or can they be in any order?
Could the input array be empty or null?

Brute Force Solution

Approach

The brute force strategy for finding all possible orderings of items involves trying every single possible arrangement. We generate each permutation and add the valid ones to our result. This guarantees we find all possible answers, although it might take a while if we have a lot of items.

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

Start by picking the first item in our list.
Now, for each remaining item, consider putting it second.
For each of these combinations, take another remaining item and put it third.
Continue this process until you've used all the items.
Each time you've used all items, you have one complete arrangement.
Repeat the entire process, starting from the beginning, but picking the items in a different order.
Keep doing this until you've tried every possible order for picking the items.

Code Implementation

def find_all_permutations(input_list):
    all_possible_permutations = []

    def generate_permutations(current_permutation, remaining_elements):
        # If there are no remaining elements, the permutation is complete.
        if not remaining_elements:
            all_possible_permutations.append(current_permutation[:])
            return

        for index in range(len(remaining_elements)):
            # Choose an element to add to the current permutation.

            element_to_add = remaining_elements[index]

            current_permutation.append(element_to_add)

            # Create a new list of remaining elements without the chosen one.
            new_remaining_elements = remaining_elements[:index] + remaining_elements[index+1:]

            # Recursively generate permutations.
            generate_permutations(current_permutation, new_remaining_elements)

            # Backtrack by removing the last added element to explore other possibilities.
            current_permutation.pop()

    generate_permutations([], input_list)
    return all_possible_permutations

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n!) – The described brute force permutation algorithm explores every possible arrangement of the n input elements. For the first position, there are n choices, for the second, n-1 choices remain, then n-2, and so on until only one choice remains. This results in n * (n-1) * (n-2) * ... * 1, which is equal to n! (n factorial). Therefore, the algorithm must perform on the order of n! operations to generate all permutations.

Space Complexity

O(N) – The described algorithm uses recursion. In the worst-case scenario, where N is the number of items, the recursion depth can reach N. Each recursive call adds a new frame to the call stack, requiring space to store the function's local variables and return address. Therefore, the auxiliary space required is proportional to the depth of the recursion, resulting in O(N) space complexity due to the call stack.

Optimal Solution

Approach

To create all possible arrangements of items, we'll use a method that systematically explores each arrangement. The core idea is to build up each arrangement step-by-step by making choices about which item to include next, and then undo those choices to explore other possibilities. This avoids generating duplicate arrangements and ensures we consider every possibility exactly once.

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

Start with an empty arrangement.
Choose an item that hasn't already been used in the current arrangement.
Add the chosen item to the current arrangement.
If the arrangement is now complete, save it as one of the final results.
Otherwise, repeat the process of choosing and adding items to expand the arrangement.
Once all possible extensions of the current arrangement have been explored, remove the last added item. This allows us to backtrack and explore other choices at that step.
Repeat the entire process until all possible arrangements have been generated.

Code Implementation

def find_all_permutations(input_list):
    all_possible_permutations = []
    current_permutation = []
    used_elements = [False] * len(input_list)

    def generate_permutations():
        # When permutation is complete, add to results
        if len(current_permutation) == len(input_list):
            all_possible_permutations.append(current_permutation[:] )
            return

        for index in range(len(input_list)):
            # Only consider unused elements to avoid duplicates in permutation
            if not used_elements[index]:
                current_permutation.append(input_list[index])
                used_elements[index] = True

                generate_permutations()

                # Backtrack: remove the last element to explore other branches
                used_elements[index] = False
                current_permutation.pop()

    generate_permutations()
    return all_possible_permutations

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n!) – The algorithm constructs permutations of an input array of size n. At each step, it explores n choices for the first position, then n-1 choices for the second, n-2 for the third, and so on until only one choice remains. This leads to n * (n-1) * (n-2) * ... * 1 = n! total permutations being generated. Building each permutation takes O(n) time to copy the elements into a result list. Therefore, the overall time complexity is dominated by the generation of n! permutations, resulting in O(n!).

Space Complexity

O(N) – The algorithm uses recursion to build permutations. The depth of the recursion can reach N, where N is the number of items, as each recursive call adds an item to the current arrangement. Each level of recursion requires space to store the function's state (local variables, return address), so the maximum space used by the call stack is proportional to N. Additionally, space is used to store the current arrangement being built, which can also grow up to size N. Therefore, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty list to indicate no permutations are possible for an invalid input.
Input array with only one element	Return a list containing a list with the single element as the only permutation.
Input array with two elements	Ensure both possible permutations are generated correctly by swapping the elements.
Large input array causing stack overflow in recursive implementations	Consider using iterative solutions or language-specific optimizations for tail recursion to avoid stack overflow issues.
Input array containing negative numbers	The algorithm should function correctly with negative numbers without any special modifications.
Input array containing zero	The algorithm should function correctly with zero without any special modifications.
Input array with elements that are near the maximum integer value	Ensure that any arithmetic operations within the algorithm do not lead to integer overflows, which could cause incorrect results.
Input array that is already sorted	The algorithm should still generate all permutations correctly, regardless of the initial order of elements.

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 maximum possible size of the input array nums?
Does the input array nums contain only positive integers, or can it include negative numbers or zero?
Are all the integers in the input array nums guaranteed to be distinct, as stated in the problem description?
Is the order of the permutations in the output significant, or can they be in any order?
Could the input array be empty or null?

Brute Force Solution

Approach

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

Start by picking the first item in our list.
Now, for each remaining item, consider putting it second.
For each of these combinations, take another remaining item and put it third.
Continue this process until you've used all the items.
Each time you've used all items, you have one complete arrangement.
Repeat the entire process, starting from the beginning, but picking the items in a different order.
Keep doing this until you've tried every possible order for picking the items.

Code Implementation

def find_all_permutations(input_list):
    all_possible_permutations = []

    def generate_permutations(current_permutation, remaining_elements):
        # If there are no remaining elements, the permutation is complete.
        if not remaining_elements:
            all_possible_permutations.append(current_permutation[:])
            return

        for index in range(len(remaining_elements)):
            # Choose an element to add to the current permutation.

            element_to_add = remaining_elements[index]

            current_permutation.append(element_to_add)

            # Create a new list of remaining elements without the chosen one.
            new_remaining_elements = remaining_elements[:index] + remaining_elements[index+1:]

            # Recursively generate permutations.
            generate_permutations(current_permutation, new_remaining_elements)

            # Backtrack by removing the last added element to explore other possibilities.
            current_permutation.pop()

    generate_permutations([], input_list)
    return all_possible_permutations

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start with an empty arrangement.
Choose an item that hasn't already been used in the current arrangement.
Add the chosen item to the current arrangement.
If the arrangement is now complete, save it as one of the final results.
Otherwise, repeat the process of choosing and adding items to expand the arrangement.
Once all possible extensions of the current arrangement have been explored, remove the last added item. This allows us to backtrack and explore other choices at that step.
Repeat the entire process until all possible arrangements have been generated.

Code Implementation

def find_all_permutations(input_list):
    all_possible_permutations = []
    current_permutation = []
    used_elements = [False] * len(input_list)

    def generate_permutations():
        # When permutation is complete, add to results
        if len(current_permutation) == len(input_list):
            all_possible_permutations.append(current_permutation[:] )
            return

        for index in range(len(input_list)):
            # Only consider unused elements to avoid duplicates in permutation
            if not used_elements[index]:
                current_permutation.append(input_list[index])
                used_elements[index] = True

                generate_permutations()

                # Backtrack: remove the last element to explore other branches
                used_elements[index] = False
                current_permutation.pop()

    generate_permutations()
    return all_possible_permutations

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty list to indicate no permutations are possible for an invalid input.
Input array with only one element	Return a list containing a list with the single element as the only permutation.
Input array with two elements	Ensure both possible permutations are generated correctly by swapping the elements.
Large input array causing stack overflow in recursive implementations	Consider using iterative solutions or language-specific optimizations for tail recursion to avoid stack overflow issues.
Input array containing negative numbers	The algorithm should function correctly with negative numbers without any special modifications.
Input array containing zero	The algorithm should function correctly with zero without any special modifications.
Input array with elements that are near the maximum integer value	Ensure that any arithmetic operations within the algorithm do not lead to integer overflows, which could cause incorrect results.
Input array that is already sorted	The algorithm should still generate all permutations correctly, regardless of the initial order of elements.