Jobs

Interviews

Discussions

Make Two Arrays Equal by Reversing Subarrays

Easy

Asked by:

23 views

Topics:

Arrays

You are given two integer arrays of equal length target and arr. In one step, you can select any non-empty subarray of arr and reverse it. You are allowed to make any number of steps.

Return true if you can make arr equal to target or false otherwise.

Example 1:

Input: target = [1,2,3,4], arr = [2,4,1,3]
Output: true
Explanation: You can follow the next steps to convert arr to target:
1- Reverse subarray [2,4,1], arr becomes [1,4,2,3]
2- Reverse subarray [4,2], arr becomes [1,2,4,3]
3- Reverse subarray [4,3], arr becomes [1,2,3,4]
There are multiple ways to convert arr to target, this is not the only way to do so.

Example 2:

Input: target = [7], arr = [7]
Output: true
Explanation: arr is equal to target without any reverses.

Example 3:

Input: target = [3,7,9], arr = [3,7,11]
Output: false
Explanation: arr does not have value 9 and it can never be converted to target.

Constraints:

target.length == arr.length
1 <= target.length <= 1000
1 <= target[i] <= 1000
1 <= arr[i] <= 1000

Try coding it in LeetCode

Make Two Arrays Equal by Reversing Subarrays

Easy

Asked by:

23 views

Topics:

Arrays

You are given two integer arrays of equal length target and arr. In one step, you can select any non-empty subarray of arr and reverse it. You are allowed to make any number of steps.

Return true if you can make arr equal to target or false otherwise.

Example 1:

Input: target = [1,2,3,4], arr = [2,4,1,3]
Output: true
Explanation: You can follow the next steps to convert arr to target:
1- Reverse subarray [2,4,1], arr becomes [1,4,2,3]
2- Reverse subarray [4,2], arr becomes [1,2,4,3]
3- Reverse subarray [4,3], arr becomes [1,2,3,4]
There are multiple ways to convert arr to target, this is not the only way to do so.

Example 2:

Input: target = [7], arr = [7]
Output: true
Explanation: arr is equal to target without any reverses.

Example 3:

Input: target = [3,7,9], arr = [3,7,11]
Output: false
Explanation: arr does not have value 9 and it can never be converted to target.

Constraints:

target.length == arr.length
1 <= target.length <= 1000
1 <= target[i] <= 1000
1 <= arr[i] <= 1000

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 are the possible ranges for the integer values within the input arrays?
Can the input arrays, `target` and `arr`, be empty or null?
Are there any constraints on the lengths of the arrays? Should I expect them to always be the same length?
If `arr` cannot be transformed into `target` by reversing subarrays, what should my function return (e.g., `false`, throw an exception)?
Are duplicate numbers allowed within the arrays, and if so, how should I handle their ordering when determining equality?

Brute Force Solution

Approach

To figure out if two lists of numbers can be made the same by flipping sections of the first list, the brute force method tries every possible combination of flips. We'll systematically explore flipping different parts of the first list and seeing if any of those flips makes it match the second list.

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

Start by considering all possible sections of the first list that you could flip.
For each section, actually flip it around (reverse the order of the numbers in that section).
After flipping that section, compare the entire first list to the second list to see if they are now exactly the same.
If they are the same, you've found a way to make the lists equal, so you're done.
If they are not the same, undo the flip you just did, putting the section back in its original order.
Move on to trying a different section to flip, repeating the process of flipping, comparing, and undoing until you've tried every possible section. Also consider the case where you flip multiple sections in a row.
If, after trying all possible sections and combinations of flips, you never find a way to make the lists the same, then it's impossible to make them equal by flipping sections.

Code Implementation

def can_be_equal_brute_force(target_array, array_to_modify):
    array_length = len(target_array)

    # Iterate through all possible start indices for subarrays
    for start_index in range(array_length):
        # Iterate through all possible end indices for subarrays
        for end_index in range(start_index, array_length):

            # Create a copy to avoid modifying the original array
            temporary_array = array_to_modify[:]

            # Reverse the selected subarray
            temporary_array[start_index:end_index+1] = temporary_array[start_index:end_index+1][::-1]

            # Check if the modified array matches the target array
            if temporary_array == target_array:
                return True

    # Consider multiple reversals by recursion
    for start_index in range(array_length):
        for end_index in range(start_index, array_length):
            temporary_array = array_to_modify[:]
            temporary_array[start_index:end_index+1] = temporary_array[start_index:end_index+1][::-1]

            #Recursively check if it can be equal.
            if can_be_equal_brute_force(target_array, temporary_array):
               return True

    # If no combination of reversals results in equality, return False
    return False

Big(O) Analysis

Time Complexity

O(n^n * n) – The algorithm iterates through all possible subarrays of the target array. There can be up to O(n^2) subarrays. Reversing each subarray takes O(n) time. Furthermore, after each subarray reversal, the algorithm compares the modified array with the target array, which takes O(n) time. The brute force method also considers the case where you flip multiple sections in a row. Hence, for each of the n^2 subarrays to flip, we can choose to flip or not flip it, resulting in 2^(n^2) possibilities, so, for each one, we verify it, which is O(n). So, the total time complexity could reach O(2^(n^2) * n), but as it uses a recursive style, it must keep track of each subarray state. Considering each of the n subarrays, and whether to flip or not flip each subarray, implies n to the power of n different possible flips. Considering this, each flip may take O(n) time to reverse the subarray and O(n) time to do the comparision, so O(2n) ~ O(n). Therefore, it can lead to O(n^n * n) operations, where n is the length of the array.

Space Complexity

O(N) – The provided solution reverses subarrays in place but needs to make a copy to compare. When a subarray is reversed, a copy of the array must be made to compare with the target array. Therefore, the algorithm utilizes an auxiliary array with a size equal to that of the input array, which we denote as N. This auxiliary space is used to hold a copy of the modified array to compare for equality. This results in O(N) auxiliary space complexity.

Optimal Solution

Approach

The key idea is that the order of subarrays doesn't matter when you only care about the final content. Therefore, if two collections have the same elements in them, even if they are arranged differently, you can always rearrange one to match the other by reversing parts of it.

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

Check if both collections of items contain the exact same items, regardless of the order they're in.
If the two collections do not contain the same items, then it is impossible to make them identical by reversing pieces.
If the collections do contain the same items, then it *is* always possible to make them identical by reversing pieces. This is because all the needed items exist to swap into the correct place, even if the order needs to be changed.

Code Implementation

def can_be_equal(target_array, array_to_modify):
    # Convert lists to dictionaries to count element occurrences.
    target_counts = {}
    modify_counts = {}

    for element in target_array:
        target_counts[element] = target_counts.get(element, 0) + 1

    for element in array_to_modify:
        modify_counts[element] = modify_counts.get(element, 0) + 1

    # Ensure both arrays have the same elements, regardless of order.
    if target_counts != modify_counts:
        return False

    # If the element counts are equal, it's always possible to make them equal.
    return True

Big(O) Analysis

Time Complexity

O(n) – The core operation is checking if two arrays contain the same elements. This can be efficiently done by comparing frequency counts of elements in both arrays. Building the frequency counts requires iterating through each array once, which takes O(n) time for each array. Comparing the two frequency counts then also takes O(n) operations in the worst case, leading to a total time complexity of O(n).

Space Complexity

O(N) – The provided plain English explanation suggests comparing the elements of the two input arrays to check if they contain the same items, regardless of order. A common way to efficiently perform this check is to use a hash map or frequency counter to store the count of each element in one array. In the worst-case scenario, all elements in the input arrays are distinct, so the hash map will need to store N key-value pairs, where N is the number of elements in either array. Thus, the auxiliary space required scales linearly with the input size, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Null or undefined input arrays	Throw an IllegalArgumentException or return false/error code immediately, as a meaningful comparison is impossible.
Empty input arrays	Return true, as two empty arrays are considered equal.
Arrays of different lengths	Return false immediately as arrays of different sizes cannot be made equal by reversing subarrays.
Arrays with single element	Return true, as single element arrays are equal if the elements are identical.
Arrays with duplicate elements where frequencies differ	Frequency counting/hash map based solutions will detect and return false if element counts differ.
Arrays containing negative numbers, zeros, and large positive numbers	Frequency counting/hash map based solutions will handle all integer values correctly as keys.
Large array sizes that might cause memory issues	Frequency counting/hash map approach is reasonably efficient, but consider using alternative data structures if memory becomes a bottleneck.
Arrays are identical from the start	Return true immediately as no reversals are needed.

Null or undefined input arrays

How to Handle:

Throw an IllegalArgumentException or return false/error code immediately, as a meaningful comparison is impossible.

Empty input arrays

How to Handle:

Return true, as two empty arrays are considered equal.

Arrays of different lengths

How to Handle:

Return false immediately as arrays of different sizes cannot be made equal by reversing subarrays.

Arrays with single element

How to Handle:

Return true, as single element arrays are equal if the elements are identical.

Arrays with duplicate elements where frequencies differ

How to Handle:

Frequency counting/hash map based solutions will detect and return false if element counts differ.

Arrays containing negative numbers, zeros, and large positive numbers

How to Handle:

Frequency counting/hash map based solutions will handle all integer values correctly as keys.

Large array sizes that might cause memory issues

How to Handle:

Frequency counting/hash map approach is reasonably efficient, but consider using alternative data structures if memory becomes a bottleneck.

Arrays are identical from the start

How to Handle:

Return true immediately as no reversals are needed.

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 are the possible ranges for the integer values within the input arrays?
Can the input arrays, `target` and `arr`, be empty or null?
Are there any constraints on the lengths of the arrays? Should I expect them to always be the same length?
If `arr` cannot be transformed into `target` by reversing subarrays, what should my function return (e.g., `false`, throw an exception)?
Are duplicate numbers allowed within the arrays, and if so, how should I handle their ordering when determining equality?

Brute Force Solution

Approach

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

Start by considering all possible sections of the first list that you could flip.
For each section, actually flip it around (reverse the order of the numbers in that section).
After flipping that section, compare the entire first list to the second list to see if they are now exactly the same.
If they are the same, you've found a way to make the lists equal, so you're done.
If they are not the same, undo the flip you just did, putting the section back in its original order.
Move on to trying a different section to flip, repeating the process of flipping, comparing, and undoing until you've tried every possible section. Also consider the case where you flip multiple sections in a row.
If, after trying all possible sections and combinations of flips, you never find a way to make the lists the same, then it's impossible to make them equal by flipping sections.

Code Implementation

def can_be_equal_brute_force(target_array, array_to_modify):
    array_length = len(target_array)

    # Iterate through all possible start indices for subarrays
    for start_index in range(array_length):
        # Iterate through all possible end indices for subarrays
        for end_index in range(start_index, array_length):

            # Create a copy to avoid modifying the original array
            temporary_array = array_to_modify[:]

            # Reverse the selected subarray
            temporary_array[start_index:end_index+1] = temporary_array[start_index:end_index+1][::-1]

            # Check if the modified array matches the target array
            if temporary_array == target_array:
                return True

    # Consider multiple reversals by recursion
    for start_index in range(array_length):
        for end_index in range(start_index, array_length):
            temporary_array = array_to_modify[:]
            temporary_array[start_index:end_index+1] = temporary_array[start_index:end_index+1][::-1]

            #Recursively check if it can be equal.
            if can_be_equal_brute_force(target_array, temporary_array):
               return True

    # If no combination of reversals results in equality, return False
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Check if both collections of items contain the exact same items, regardless of the order they're in.
If the two collections do not contain the same items, then it is impossible to make them identical by reversing pieces.
If the collections do contain the same items, then it *is* always possible to make them identical by reversing pieces. This is because all the needed items exist to swap into the correct place, even if the order needs to be changed.

Code Implementation

def can_be_equal(target_array, array_to_modify):
    # Convert lists to dictionaries to count element occurrences.
    target_counts = {}
    modify_counts = {}

    for element in target_array:
        target_counts[element] = target_counts.get(element, 0) + 1

    for element in array_to_modify:
        modify_counts[element] = modify_counts.get(element, 0) + 1

    # Ensure both arrays have the same elements, regardless of order.
    if target_counts != modify_counts:
        return False

    # If the element counts are equal, it's always possible to make them equal.
    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or undefined input arrays	Throw an IllegalArgumentException or return false/error code immediately, as a meaningful comparison is impossible.
Empty input arrays	Return true, as two empty arrays are considered equal.
Arrays of different lengths	Return false immediately as arrays of different sizes cannot be made equal by reversing subarrays.
Arrays with single element	Return true, as single element arrays are equal if the elements are identical.
Arrays with duplicate elements where frequencies differ	Frequency counting/hash map based solutions will detect and return false if element counts differ.
Arrays containing negative numbers, zeros, and large positive numbers	Frequency counting/hash map based solutions will handle all integer values correctly as keys.
Large array sizes that might cause memory issues	Frequency counting/hash map approach is reasonably efficient, but consider using alternative data structures if memory becomes a bottleneck.
Arrays are identical from the start	Return true immediately as no reversals are needed.

Null or undefined input arrays

How to Handle:

Throw an IllegalArgumentException or return false/error code immediately, as a meaningful comparison is impossible.

Empty input arrays

How to Handle:

Return true, as two empty arrays are considered equal.

Arrays of different lengths

How to Handle:

Return false immediately as arrays of different sizes cannot be made equal by reversing subarrays.

Arrays with single element

How to Handle:

Return true, as single element arrays are equal if the elements are identical.

Arrays with duplicate elements where frequencies differ

How to Handle:

Frequency counting/hash map based solutions will detect and return false if element counts differ.

Arrays containing negative numbers, zeros, and large positive numbers

How to Handle:

Frequency counting/hash map based solutions will handle all integer values correctly as keys.

Large array sizes that might cause memory issues

How to Handle:

Frequency counting/hash map approach is reasonably efficient, but consider using alternative data structures if memory becomes a bottleneck.

Arrays are identical from the start

How to Handle:

Return true immediately as no reversals are needed.