Make Two Arrays Equal by Reversing Subarrays — Solution
Make Two Arrays Equal by Reversing Subarrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Make Two Arrays Equal by Reversing Subarrays is an easy coding problem on arrays, hash table and sorting, asked in Amazon and Meta interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Sorting
- Asked at: Amazon, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You get two integer arrays target and arr of the same length. In one move you may pick any non-empty contiguous subarray of arr and reverse it, and you may make as many moves as you like.
Return true if some sequence of moves turns arr into target.
Example 1
Input: target = [1,2,3,4], arr = [2,4,1,3]
Output: true
Explanation: Reverse [2,4,1] to get [1,4,2,3], then [4,2] to get [1,2,4,3], then [4,3] to get [1,2,3,4].
Example 2
Input: target = [7], arr = [7]
Output: true
Example 3
Input: target = [3,7,9], arr = [3,7,11]
Output: false
Explanation: `arr` has no 9, and reversing never creates a value.
Constraints
target.length == arr.length1 <= target.length <= 10001 <= target[i] <= 10001 <= arr[i] <= 1000
Hints for Make Two Arrays Equal by Reversing Subarrays
Hint 1
Reversing a subarray of length 2 swaps two neighbours.
Hint 2
Adjacent swaps are enough to sort any array — so they can produce any arrangement of the same values.
Hint 3
The answer only depends on whether both arrays hold the same values with the same multiplicities.
How to solve Make Two Arrays Equal by Reversing Subarrays
Reversals of length 2 are adjacent swaps, and adjacent swaps reach every permutation; reversals never change which values are present. So the arrays can be made equal exactly when they are equal as multisets.
Approach
- Keep a count per value (values are at most 1000).
- Add 1 for every value of
targetand subtract 1 for every value ofarr. - Return
trueif every count ends at zero.
Why it works
Bubble sort shows that adjacent swaps can move arr into any order of its own elements, including the order of target when the multisets agree. If the multisets differ, no reversal can help, because a reversal only rearranges existing elements.
Complexity
- Time —
O(n + V) with V = 1000 - Space —
O(V)
Pitfalls
- Comparing sets instead of counts misses duplicates:
[1,1,2]and[1,2,2]are not equal. - There is no limit on the number of moves, so do not simulate them.
- Sorting both copies is fine too, in O(n log n).
Reference solution
Python
from typing import List
def canBeEqual(target: List[int], arr: List[int]) -> bool:
return sorted(target) == sorted(arr)Java
public static boolean canBeEqual(int[] target, int[] arr) {
int[] count = new int[1001];
for (int i = 0; i < target.length; i++) {
count[target[i]]++;
count[arr[i]]--;
}
for (int c : count) {
if (c != 0) return false;
}
return true;
}C++
bool canBeEqual(vector<int>& target, vector<int>& arr) {
vector<int> count(1001, 0);
for (size_t i = 0; i < target.size(); i++) {
count[target[i]]++;
count[arr[i]]--;
}
for (int c : count) {
if (c != 0) return false;
}
return true;
}JavaScript
var canBeEqual = function(target, arr) {
var count = new Map();
for (var i = 0; i < target.length; i++) {
count.set(target[i], (count.get(target[i]) || 0) + 1);
count.set(arr[i], (count.get(arr[i]) || 0) - 1);
}
var ok = true;
count.forEach(function(c) {
if (c !== 0) ok = false;
});
return ok;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets