Make Two Arrays Equal by Reversing Subarrays

EASY

Description

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

Approaches

Checkout 3 different approaches to solve Make Two Arrays Equal by Reversing Subarrays. Click on different approaches to view the approach and algorithm in detail.

Array as a Frequency Counter

This approach is an optimization of the frequency counting method. Given the problem's constraint that all numbers are between 1 and 1000, we can use a simple array as a direct-access table instead of a hash map. This eliminates the overhead of hashing and object creation, making it the most efficient solution in terms of both time and space.

Algorithm

Create an integer array counts of size 1001, initialized to zeros.
Iterate through the input arrays from i = 0 to N-1.
In each iteration, increment the count for the target element (counts[target[i]]++) and decrement the count for the arr element (counts[arr[i]]--).
After the loop, iterate through the counts array. If any value is non-zero, return false.
If all counts are zero, return true.

The core idea remains the same: check if the arrays are permutations by comparing element frequencies.

We create an integer array, counts, of size 1001 (to accommodate numbers from 1 to 1000) and initialize it with zeros.
We can process both arrays in a single loop. For each index i, we treat the appearance of target[i] as a credit and the appearance of arr[i] as a debit. We do this by incrementing counts[target[i]] and decrementing counts[arr[i]].
If the two arrays are permutations, then for any number x, it must appear the same number of times in target as in arr. Therefore, after the loop, the net count for x in our counts array should be zero.
We perform a final check by iterating through the counts array. If any entry is not zero, it signifies a mismatch in frequencies, and we return false.
If all counts are zero, it confirms the arrays are permutations, and we return true.

class Solution {
    public boolean canBeEqual(int[] target, int[] arr) {
        if (target.length != arr.length) {
            return false;
        }
        int[] counts = new int[1001];
        for (int i = 0; i < target.length; i++) {
            counts[target[i]]++;
            counts[arr[i]]--;
        }
        
        for (int count : counts) {
            if (count != 0) {
                return false;
            }
        }
        
        return true;
    }
}

Complexity Analysis

Time Complexity: O(N + M), where N is the length of the arrays and M is the range of possible values (1001). Since M is a constant, the complexity simplifies to `O(N)`.Space Complexity: O(1). We use an array of a fixed size (1001) based on the problem's constraints on element values. This space usage does not scale with the input array length N.

Pros and Cons

Pros:

Optimal time complexity of O(N).
Optimal space complexity of O(1), as the counts array size is constant and does not depend on the input size N.
Extremely fast in practice due to the use of array indexing instead of hash map operations.

Cons:

This approach is only suitable when the range of values in the input is known and small enough to be used as array indices.

Code Solutions

Checking out 4 solutions in different languages for Make Two Arrays Equal by Reversing Subarrays. Click on different languages to view the code.

class Solution {
public
  boolean canBeEqual(int[] target, int[] arr) {
    Arrays.sort(target);
    Arrays.sort(arr);
    return Arrays.equals(target, arr);
  }
}

Video Solution

Watch the video walkthrough for Make Two Arrays Equal by Reversing Subarrays

Algorithms:

Sorting

Data Structures:

ArrayHash Table