Make Two Arrays Equal by Reversing Subarrays

Easy

#1348Time: 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: 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.

Algorithms

Sorting

Data structures

Array Hash Table

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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.

1class Solution {2    public boolean canBeEqual(int[] target, int[] arr) {3        if (target.length != arr.length) {4            return false;5        }6        int[] counts = new int[1001];7        for (int i = 0; i < target.length; i++) {8            counts[target[i]]++;9            counts[arr[i]]--;10        }11        12        for (int count : counts) {13            if (count != 0) {14                return false;15            }16        }17        18        return true;19    }20}

Complexity

Time

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

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.

Trade-offs

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.

The fundamental insight is that the ability to reverse any subarray allows for the complete reordering of the elements in arr. This means arr can be transformed into target if and only if arr is a permutation of target—that is, they contain the same elements with the same frequencies. A straightforward way to verify this is to sort both arrays. If they are permutations of each other, their sorted versions will be identical.

Algorithm

Sort the target array.
Sort the arr array.
Compare the two sorted arrays. If they are identical, return true. Otherwise, return false.

Walkthrough

This approach leverages standard sorting algorithms to check for equivalence.

The target array is sorted in non-decreasing order.
The arr array is also sorted in non-decreasing order.
After sorting, if the original arrays contained the same set of numbers, their sorted versions must be identical. We can then compare the two sorted arrays element by element.
A convenient way to perform this comparison in Java is by using the Arrays.equals() method, which returns true if two arrays are of the same length and all corresponding pairs of elements are equal.

1import java.util.Arrays;2 3class Solution {4    public boolean canBeEqual(int[] target, int[] arr) {5        if (target.length != arr.length) {6            return false;7        }8        Arrays.sort(target);9        Arrays.sort(arr);10        return Arrays.equals(target, arr);11    }12}

Complexity

Time

O(N log N), where N is the number of elements in the arrays. The dominant operation is sorting both arrays.

Space

O(log N) to O(N). The space complexity depends on the sorting algorithm used. In Java, `Arrays.sort()` for primitive types is implemented using a dual-pivot quicksort, which requires `O(log N)` space on average for the recursion stack. In the worst case, it can take `O(N)` space.

Trade-offs

Pros

Simple to conceptualize and implement.
The code is very concise, especially when using built-in library functions.

Cons

The time complexity of O(N log N) is less efficient than linear time solutions.
Modifies the input arrays unless copies are made, which would increase space usage.

Instead of sorting, we can verify that the arrays are permutations by counting the frequency of each element. If both arrays have the same count for every number present, they are permutations. A hash map is a suitable data structure for this task, as it can efficiently map each number to its frequency.

Algorithm

Create a HashMap to store the frequency of each number in the target array.
Iterate through target and populate the frequency map.
Iterate through arr. For each number, decrement its count in the map.
If a number from arr is not in the map or its count is already zero, return false immediately.
If the loop completes, it means the arrays are permutations, so return true.

Walkthrough

This method involves two passes over the arrays.

First, we create a hash map. We iterate through the target array, and for each number, we store or update its frequency in the map. For example, if target is [1, 2, 2], the map will become {1: 1, 2: 2}.
Second, we iterate through the arr array. For each number in arr, we check its status in the map.
- If the number is not a key in the map or its count is 0, it means arr has an element that target doesn't have, or has it in a higher frequency. We can immediately conclude they are not permutations and return false.
- Otherwise, we decrement the count for that number in the map.
If we successfully complete the iteration over arr without returning false, it confirms that every element in arr had a corresponding element in target, and thus the arrays are permutations. We return true.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public boolean canBeEqual(int[] target, int[] arr) {6        if (target.length != arr.length) {7            return false;8        }9        Map<Integer, Integer> counts = new HashMap<>();10        for (int num : target) {11            counts.put(num, counts.getOrDefault(num, 0) + 1);12        }13        14        for (int num : arr) {15            if (!counts.containsKey(num) || counts.get(num) == 0) {16                return false;17            }18            counts.put(num, counts.get(num) - 1);19        }20        21        return true;22    }23}

Complexity

Time

O(N), where N is the length of the arrays. We perform two separate passes through the arrays, and hash map operations take, on average, O(1) time.

Space

O(K), where K is the number of unique elements. In the worst case, all N elements are unique, making the space complexity `O(N)`.

Trade-offs

Pros

Achieves a linear time complexity of O(N), which is more efficient than sorting for large N.
Flexible and works for any range of integer values, not just small, constrained ones.

Cons

Requires extra space for the hash map, which can be up to O(N) in the worst case.
Slightly more complex to implement than the sorting approach.
Can have higher constant overhead than using a simple array due to hashing.

Solutions

Solution

1class Solution {2public3  boolean canBeEqual(int[] target, int[] arr) {4    Arrays.sort(target);5    Arrays.sort(arr);6    return Arrays.equals(target, arr);7  }8}

1function canBeEqual ( target , arr ) { target . sort (); arr . sort (); return target . every (( x , i ) => x === arr [ i ]); }

1class Solution {2public:3  bool canBeEqual(vector<int> &target, vector<int> &arr) {4    sort(target.begin(), target.end());5    sort(arr.begin(), arr.end());6    return target == arr;7  }8};

1class Solution:2    def canBeEqual(self, target: List[int], arr: List[int]) -> bool: target . sort() arr . sort() return target == arr

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  boolean canBeEqual(int[] target, int[] arr) {4    Arrays.sort(target);5    Arrays.sort(arr);6    return Arrays.equals(target, arr);7  }8}

1function canBeEqual ( target , arr ) { target . sort (); arr . sort (); return target . every (( x , i ) => x === arr [ i ]); }

1class Solution {2public:3  bool canBeEqual(vector<int> &target, vector<int> &arr) {4    sort(target.begin(), target.end());5    sort(arr.begin(), arr.end());6    return target == arr;7  }8};

1class Solution:2    def canBeEqual(self, target: List[int], arr: List[int]) -> bool: target . sort() arr . sort() return target == arr

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.