Jobs

Interviews

Discussions

Permutations II

Medium

Asked by:

More companies

76 views

Topics:

ArraysRecursion

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Example 1:

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

Example 2:

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

Constraints:

1 <= nums.length <= 8
-10 <= nums[i] <= 10

Try coding it in LeetCode

Permutations II

Medium

Asked by:

More companies

76 views

Topics:

ArraysRecursion

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Example 1:

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

Example 2:

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

Constraints:

1 <= nums.length <= 8
-10 <= nums[i] <= 10

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 maximum size of the input array `nums`?
Can the input array `nums` contain negative numbers, zero, or floating-point numbers?
If the input array `nums` is empty, should I return an empty list or `null`?
Is the order of permutations in the output list significant? If so, what order should I use?
Are all the numbers in `nums` integers, or are other data types possible?

Brute Force Solution

Approach

The brute force strategy for generating unique permutations involves exploring every possible arrangement of the given numbers. Since we need unique permutations, we also check for and avoid duplicates in our generated results. We systematically create and filter all possible arrangements to find the unique ones.

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

Imagine you have a pile of numbered tiles.
Start by picking a tile and setting it down as the beginning of a possible arrangement.
Then, pick another tile from the remaining ones and place it next to the first one, creating a longer arrangement.
Keep adding tiles from the remaining ones until you've used all the tiles in the arrangement.
Write down the entire arrangement you created.
Repeat this process, but each time, start with a different tile as the first one.
Continue exploring every possible way to pick and place the tiles until you've tried all the starting tiles and every possible combination of them.
Once you have a list of all the arrangements, go through the list and remove any arrangements that are exactly the same as each other, keeping only the unique arrangements.

Code Implementation

def find_unique_permutations_brute_force(numbers):
    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_to_add = remaining_numbers[index]
            
            # Add the current number to the permutation and recurse.
            current_permutation.append(number_to_add)
            generate_permutations(current_permutation, remaining_numbers[:index] + remaining_numbers[index+1:])
            
            # Backtrack to try other possibilities.
            current_permutation.pop()
            
    generate_permutations([], numbers)
    
    unique_permutations_set = []

    #Remove duplicate permutations from the complete list
    for permutation in all_permutations:
        if permutation not in unique_permutations_set:

            unique_permutations_set.append(permutation)

    return unique_permutations_set

Big(O) Analysis

Time Complexity

O(n! * n) – The algorithm generates all possible permutations of the input array. There are n! (n factorial) possible permutations for an array of size n. For each permutation, the algorithm needs to check if it already exists in the result set to avoid duplicates. This check involves comparing the current permutation (of length n) with existing permutations. Thus, the overall time complexity becomes O(n! * n), where n! accounts for generating all permutations and n accounts for checking if a permutation is a duplicate.

Space Complexity

O(N) – The space complexity is determined by the depth of the recursion stack and the temporary list used to build permutations. The maximum depth of the recursion is N (the number of tiles), as in each recursive call, we are picking one of the remaining tiles. In the worst case, we are also storing a temporary list of size N. Therefore, the space used is proportional to N, leading to O(N) space complexity.

Optimal Solution

Approach

The challenge is to find all unique arrangements of a list of things, where some things might be the same. The key idea is to build each arrangement one thing at a time, but to avoid creating duplicate arrangements by carefully considering which thing to add next. We'll use a system to keep track of how many of each thing we have left to use, and only add something if it's the first time we're considering adding that specific thing at that specific point in the arrangement.

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

First, count how many times each thing appears in the original list.
Start building an arrangement. At each step, consider all the things we haven't used up yet.
Before adding a thing to the arrangement, check if we've already tried adding something identical at this same spot. If so, skip it to avoid duplicates.
If it's a new thing or we haven't tried it in this spot yet, add it to the arrangement, reduce its count, and keep building the arrangement.
Once the arrangement is complete (we've used up all the things), add it to our list of final arrangements.
After adding something to the arrangement, we need to 'undo' that addition so we can try other possibilities. Increase the thing's count again, and remove it from the arrangement.
By being careful about which things we try in each spot, we avoid creating the same arrangement multiple times, making the whole process much faster.

Code Implementation

def find_unique_permutations(numbers):
    number_counts = {}
    for number in numbers:
        number_counts[number] = number_counts.get(number, 0) + 1

    unique_permutations = []
    current_permutation = []

    def backtrack():
        if len(current_permutation) == len(numbers):
            unique_permutations.append(current_permutation[:] * 1)
            return

        used_numbers = set()
        for number in number_counts:

            # Only process if count exists and it's the first time at this level
            if number_counts[number] > 0 and number not in used_numbers:

                # Mark the current number as used in the current iteration
                used_numbers.add(number)

                current_permutation.append(number)

                # Decrement count and recurse
                number_counts[number] -= 1

                backtrack()

                # Backtrack: restore state by incrementing the count
                number_counts[number] += 1
                current_permutation.pop()

    backtrack()
    return unique_permutations

Big(O) Analysis

Time Complexity

O(n!) – The algorithm explores all possible permutations of the input array. In the worst case, where all elements are distinct, there are n! possible permutations. Constructing each permutation involves potentially iterating through the input to select elements and track used counts. Therefore, the dominant factor is the generation of all n! permutations, making the time complexity O(n!).

Space Complexity

O(N) – The primary space complexity stems from the recursion depth and the frequency map. The depth of the recursion can go up to N, where N is the number of elements in the input list, representing the length of each permutation being built on the call stack. Additionally, a hash map (or similar structure) is used to store the frequency counts of the numbers, requiring space proportional to N in the worst-case where all numbers are distinct. Therefore, the overall auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty list if the input array is null or empty to avoid null pointer exceptions or unnecessary computations.
Input array with one element	Return a list containing a list with the single element to satisfy the permutation definition.
Input array with two identical elements	The algorithm should produce only one permutation: [element, element].
Input array with all identical elements (e.g., [1, 1, 1, 1])	The algorithm should produce only one permutation consisting of the identical elements repeated.
Large input array size	Consider the time and space complexity; backtracking solutions can be inefficient for very large inputs, potentially leading to timeouts or memory issues so use appropriate optimization like pruning during the DFS.
Input array with many duplicate numbers	Sorting the array before backtracking and skipping identical adjacent elements during recursion helps to avoid generating duplicate permutations, optimizing the solution.
Input array containing negative numbers, zeros, and positive numbers	The algorithm should handle all integer values correctly without special treatment based on sign or value of zero, as they do not affect the permutation logic itself.
Integer overflow if calculating factorials for very large n	Since we're returning permutations rather than counting them, and the input array size is likely constrained to avoid excessive runtime, integer overflow in calculating the number of permutations is less of a concern, and the direct permutation generation should proceed without explicit overflow checks; though large arrays may still take a while to process.

Null or empty input array

How to Handle:

Return an empty list if the input array is null or empty to avoid null pointer exceptions or unnecessary computations.

Input array with one element

How to Handle:

Return a list containing a list with the single element to satisfy the permutation definition.

Input array with two identical elements

How to Handle:

The algorithm should produce only one permutation: [element, element].

Input array with all identical elements (e.g., [1, 1, 1, 1])

How to Handle:

The algorithm should produce only one permutation consisting of the identical elements repeated.

Large input array size

How to Handle:

Consider the time and space complexity; backtracking solutions can be inefficient for very large inputs, potentially leading to timeouts or memory issues so use appropriate optimization like pruning during the DFS.

Input array with many duplicate numbers

How to Handle:

Sorting the array before backtracking and skipping identical adjacent elements during recursion helps to avoid generating duplicate permutations, optimizing the solution.

Input array containing negative numbers, zeros, and positive numbers

How to Handle:

The algorithm should handle all integer values correctly without special treatment based on sign or value of zero, as they do not affect the permutation logic itself.

Integer overflow if calculating factorials for very large n

How to Handle:

Since we're returning permutations rather than counting them, and the input array size is likely constrained to avoid excessive runtime, integer overflow in calculating the number of permutations is less of a concern, and the direct permutation generation should proceed without explicit overflow checks; though large arrays may still take a while to process.

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 size of the input array `nums`?
Can the input array `nums` contain negative numbers, zero, or floating-point numbers?
If the input array `nums` is empty, should I return an empty list or `null`?
Is the order of permutations in the output list significant? If so, what order should I use?
Are all the numbers in `nums` integers, or are other data types possible?

Brute Force Solution

Approach

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

Imagine you have a pile of numbered tiles.
Start by picking a tile and setting it down as the beginning of a possible arrangement.
Then, pick another tile from the remaining ones and place it next to the first one, creating a longer arrangement.
Keep adding tiles from the remaining ones until you've used all the tiles in the arrangement.
Write down the entire arrangement you created.
Repeat this process, but each time, start with a different tile as the first one.
Continue exploring every possible way to pick and place the tiles until you've tried all the starting tiles and every possible combination of them.
Once you have a list of all the arrangements, go through the list and remove any arrangements that are exactly the same as each other, keeping only the unique arrangements.

Code Implementation

def find_unique_permutations_brute_force(numbers):
    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_to_add = remaining_numbers[index]
            
            # Add the current number to the permutation and recurse.
            current_permutation.append(number_to_add)
            generate_permutations(current_permutation, remaining_numbers[:index] + remaining_numbers[index+1:])
            
            # Backtrack to try other possibilities.
            current_permutation.pop()
            
    generate_permutations([], numbers)
    
    unique_permutations_set = []

    #Remove duplicate permutations from the complete list
    for permutation in all_permutations:
        if permutation not in unique_permutations_set:

            unique_permutations_set.append(permutation)

    return unique_permutations_set

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, count how many times each thing appears in the original list.
Start building an arrangement. At each step, consider all the things we haven't used up yet.
Before adding a thing to the arrangement, check if we've already tried adding something identical at this same spot. If so, skip it to avoid duplicates.
If it's a new thing or we haven't tried it in this spot yet, add it to the arrangement, reduce its count, and keep building the arrangement.
Once the arrangement is complete (we've used up all the things), add it to our list of final arrangements.
After adding something to the arrangement, we need to 'undo' that addition so we can try other possibilities. Increase the thing's count again, and remove it from the arrangement.
By being careful about which things we try in each spot, we avoid creating the same arrangement multiple times, making the whole process much faster.

Code Implementation

def find_unique_permutations(numbers):
    number_counts = {}
    for number in numbers:
        number_counts[number] = number_counts.get(number, 0) + 1

    unique_permutations = []
    current_permutation = []

    def backtrack():
        if len(current_permutation) == len(numbers):
            unique_permutations.append(current_permutation[:] * 1)
            return

        used_numbers = set()
        for number in number_counts:

            # Only process if count exists and it's the first time at this level
            if number_counts[number] > 0 and number not in used_numbers:

                # Mark the current number as used in the current iteration
                used_numbers.add(number)

                current_permutation.append(number)

                # Decrement count and recurse
                number_counts[number] -= 1

                backtrack()

                # Backtrack: restore state by incrementing the count
                number_counts[number] += 1
                current_permutation.pop()

    backtrack()
    return unique_permutations

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty list if the input array is null or empty to avoid null pointer exceptions or unnecessary computations.
Input array with one element	Return a list containing a list with the single element to satisfy the permutation definition.
Input array with two identical elements	The algorithm should produce only one permutation: [element, element].
Input array with all identical elements (e.g., [1, 1, 1, 1])	The algorithm should produce only one permutation consisting of the identical elements repeated.
Large input array size	Consider the time and space complexity; backtracking solutions can be inefficient for very large inputs, potentially leading to timeouts or memory issues so use appropriate optimization like pruning during the DFS.
Input array with many duplicate numbers	Sorting the array before backtracking and skipping identical adjacent elements during recursion helps to avoid generating duplicate permutations, optimizing the solution.
Input array containing negative numbers, zeros, and positive numbers	The algorithm should handle all integer values correctly without special treatment based on sign or value of zero, as they do not affect the permutation logic itself.
Integer overflow if calculating factorials for very large n	Since we're returning permutations rather than counting them, and the input array size is likely constrained to avoid excessive runtime, integer overflow in calculating the number of permutations is less of a concern, and the direct permutation generation should proceed without explicit overflow checks; though large arrays may still take a while to process.

Null or empty input array

How to Handle:

Return an empty list if the input array is null or empty to avoid null pointer exceptions or unnecessary computations.

Input array with one element

How to Handle:

Return a list containing a list with the single element to satisfy the permutation definition.

Input array with two identical elements

How to Handle:

The algorithm should produce only one permutation: [element, element].

Input array with all identical elements (e.g., [1, 1, 1, 1])

How to Handle:

The algorithm should produce only one permutation consisting of the identical elements repeated.

Large input array size

How to Handle:

Input array with many duplicate numbers

How to Handle:

Sorting the array before backtracking and skipping identical adjacent elements during recursion helps to avoid generating duplicate permutations, optimizing the solution.

Input array containing negative numbers, zeros, and positive numbers

How to Handle:

The algorithm should handle all integer values correctly without special treatment based on sign or value of zero, as they do not affect the permutation logic itself.

Integer overflow if calculating factorials for very large n

How to Handle: