Make Two Arrays Equal by Reversing Subarrays solution and explanation
9 more videos on this problem
Make Two Arrays Equal by Reversing Subarrays - Leetcode 1460 - PythonNeetCodeIO · 8:19 · 9K views
Make Two Arrays Equal by Reversing Sub-arrays | LeetCode 1460 | C++, Java, Python solutionKnowledge Center · 13:40 · 8K views
Make Two Arrays Equal by Reversing Subarrays | Easy | Leetcode 1460 | codestorywithMIKcodestorywithMIK · 12:03 · 4K views
Leetcode Solution - 1460 Make Two Arrays Equal by Reversing Sub-arraysJohn Leonardo · 3:47 · 780 views
1460 Make Two Arrays Equal By Reversing Subarrays | Sorting | HashMap | Java Solution | LeetcodeCakot Coding · 8:15 · 611 views
LeetCode 1460. Make Two Arrays Equal by Reversing Sub-arrays | JSer - JavaScript & AlgorithmJSer · 8:16 · 553 views
1460. Make Two Arrays Equal by Reversing Sub-arrays (python) (Leetcode Easy)Programming Live with Larry · 2:43 · 536 views
Make Two Arrays Equal by Reversing Subarrays (LeetCode 1460) (Sorting, counter)CodeWithARB · 12:37 · 360 views
Make Two Arrays Equal by Reversing Sub-arrayscoding interview questions · 6:33 · 346 views
Leetcode | 1460. Make Two Arrays Equal by Reversing Subarrays | Easy | Java SolutionDeveloper Docs · 8:02 · 304 views
The problem
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.length1 <= target.length <= 10001 <= target[i] <= 10001 <= arr[i] <= 1000
Approach overview
Problem Overview: You are given two integer arrays target and arr. You can reverse any subarray of arr any number of times. The goal is to determine whether these operations can transform arr into target. The key observation: reversing subarrays changes order but never changes the elements themselves.
Approach 1: Sort and Compare (Time: O(n log n), Space: O(1) or O(n))
If reversing subarrays can rearrange elements arbitrarily, the only requirement for equality is that both arrays contain the same multiset of numbers. Sorting both arrays exposes this directly. Sort target and arr, then iterate once to check whether every element matches at the same index. If they match completely, you can reorder arr through subarray reversals to reach target. Sorting dominates the runtime with O(n log n) complexity, while the comparison step is O(n). Many standard library sorting implementations use O(log n) auxiliary stack space or O(n) depending on the language.
This approach is straightforward and reliable. It works well when implementation speed matters and constraints are small to medium. Since the logic is simple—sort then compare—it is often the first solution developers write during interviews.
Approach 2: Use Hashing to Count Frequencies (Time: O(n), Space: O(n))
A more optimal solution avoids sorting by counting element frequencies. Traverse target and store counts in a hash map (or frequency array if values are bounded). Then iterate through arr and decrement the corresponding count for each element. If any element appears more times than expected or is missing from the map, the arrays cannot be made equal.
This works because reversing subarrays only changes ordering, not frequency. If both arrays contain the same elements with identical counts, any permutation is achievable through a sequence of reversals. Hash table lookups and updates run in constant time on average, so the full traversal remains O(n).
This method uses concepts from hash tables and arrays. Compared with sorting, it improves runtime but uses additional memory to store counts.
Recommended for interviews: The hashing approach is typically preferred because it achieves O(n) time while clearly demonstrating understanding of element frequency comparison. The sorting solution still shows correct reasoning and knowledge of sorting, but interviewers often expect you to recognize that order is irrelevant and only counts matter.
Approach 1: Approach 1: Sort and Compare
This approach leverages the property that reversing subarrays can reorder elements but will not affect the element counts. Thus, if the sorted versions of the arrays are the same, then the arrays can be made equal.
def canBeEqual(target, arr):
return sorted(target) == sorted(arr)import java.util.Arrays;
class Solution {
public boolean canBeEqual(int[] target, int[] arr) {
Arrays.sort(target);
Arrays.sort(arr);
return Arrays.equals(target, arr);
}
}#include <vector>
#include <algorithm>
bool canBeEqual(std::vector<int>& target, std::vector<int>& arr) {
std::sort(target.begin(), target.end());
std::sort(arr.begin(), arr.end());
return target == arr;
}function canBeEqual(target, arr) {
target.sort((a, b) => a - b);
arr.sort((a, b) => a - b);
return target.every((value, index) => value === arr[index]);
}#include <stdbool.h>
#include <stdlib.h>
int cmpFunc(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
bool canBeEqual(int *target, int targetSize, int *arr, int arrSize) {
qsort(target, targetSize, sizeof(int), cmpFunc);
qsort(arr, arrSize, sizeof(int), cmpFunc);
for (int i = 0; i < targetSize; ++i) {
if (target[i] != arr[i]) {
return false;
}
}
return true;
}using System;
public class Solution {
public bool CanBeEqual(int[] target, int[] arr) {
Array.Sort(target);
Array.Sort(arr);
for (int i = 0; i < target.Length; i++) {
if (target[i] != arr[i]) return false;
}
return true;
}
}This Python solution sorts the arrays and directly compares them using the equality operator.
Time complexity: O(n log n) for sorting.
Space complexity: O(n) due to the creation of a new list during sorting.
Approach 2: Approach 2: Use Hashing to Count Frequencies
Instead of sorting, we can simply count the occurrences of each element in both arrays. If the frequency distributions are the same, the arrays can be made equal.
def canBeEqual(target, arr):
from collections import Counter
return Counter(target) == Counter(arr)class Solution {
public boolean canBeEqual(int[] target, int[] arr) {
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;
}
}#include <vector>
bool canBeEqual(std::vector<int>& target, std::vector<int>& arr) {
int counts[1001] = {0};
for (int i = 0; i < target.size(); ++i) {
counts[target[i]]++;
counts[arr[i]]--;
}
for (int i : counts) {
if (i != 0) return false;
}
return true;
}function canBeEqual(target, arr) {
let counts = new Array(1001).fill(0);
for (let i = 0; i < target.length; i++) {
counts[target[i]]++;
counts[arr[i]]--;
}
return counts.every(count => count === 0);
}#include <stdbool.h>
bool canBeEqual(int* target, int targetSize, int* arr, int arrSize) {
int counts[1001] = {0};
for(int i = 0; i < targetSize; ++i) {
counts[target[i]]++;
counts[arr[i]]--;
}
for(int i = 0; i < 1001; ++i) {
if(counts[i] != 0) {
return false;
}
}
return true;
}using System;
public class Solution {
public bool CanBeEqual(int[] target, int[] arr) {
int[] counts = new int[1001];
for (int i = 0; i < target.Length; ++i) {
counts[target[i]]++;
counts[arr[i]]--;
}
foreach (int count in counts) {
if (count != 0) return false;
}
return true;
}
}Python uses the Counter class from the collections module to easily tally frequencies and compare them directly.
Time complexity: O(n) for counting elements.
Space complexity: O(n) to store the frequency dictionary.
Approach 3: Sorting
If two arrays are equal after sorting, then they can be made equal by reversing sub-arrays.
Therefore, we only need to sort the two arrays and then check if the sorted arrays are equal.
The time complexity is O(n times log n), and the space complexity is O(log n), where n is the length of the array arr.
function canBeEqual(target: number[], arr: number[]): boolean {
target.sort();
arr.sort();
return target.every((x, i) => x === arr[i]);
}func canBeEqual(target []int, arr []int) bool {
sort.Ints(target)
sort.Ints(arr)
return reflect.DeepEqual(target, arr)
}impl Solution {
pub fn can_be_equal(mut target: Vec<i32>, mut arr: Vec<i32>) -> bool {
target.sort();
arr.sort();
target == arr
}
}class Solution {
/**
* @param Integer[] $target
* @param Integer[] $arr
* @return Boolean
*/
function canBeEqual($target, $arr) {
sort($target);
sort($arr);
return $target === $arr;
}
}Approach 4: Counting
We note that the range of the array elements given in the problem is 1 \sim 1000. Therefore, we can use two arrays cnt1 and cnt2 of length 1001 to record the number of times each element appears in the arrays target and arr respectively. Finally, we just need to check if the two arrays are equal.
We can also use only one array cnt. We traverse the arrays target and arr. For target[i], we increment cnt[target[i]], and for arr[i], we decrement cnt[arr[i]]. In the end, we check if all elements in the array cnt are 0.
The time complexity is O(n + M), and the space complexity is O(M). Here, n is the length of the array arr, and M is the range of the array elements. In this problem, M = 1001.
function canBeEqual(target: number[], arr: number[]): boolean {
const n = target.length;
const cnt = Array(1001).fill(0);
for (let i = 0; i < n; i++) {
cnt[target[i]]++;
cnt[arr[i]]--;
}
return cnt.every(v => !v);
}func canBeEqual(target []int, arr []int) bool {
cnt1 := make([]int, 1001)
cnt2 := make([]int, 1001)
for _, v := range target {
cnt1[v]++
}
for _, v := range arr {
cnt2[v]++
}
return reflect.DeepEqual(cnt1, cnt2)
}impl Solution {
pub fn can_be_equal(mut target: Vec<i32>, mut arr: Vec<i32>) -> bool {
let n = target.len();
let mut cnt = [0; 1001];
for i in 0..n {
cnt[target[i] as usize] += 1;
cnt[arr[i] as usize] -= 1;
}
cnt.iter().all(|v| *v == 0)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sort and Compare | Time complexity: O(n log n) for sorting. |
| Approach 2: Use Hashing to Count Frequencies | Time complexity: O(n) for counting elements. |
| Sorting | – |
| Counting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort and Compare | O(n log n) | O(1) to O(n) | Simple implementation when sorting cost is acceptable |
| Hash Frequency Counting | O(n) | O(n) | Optimal solution when linear time comparison is preferred |
Frequently asked questions
Is Make Two Arrays Equal by Reversing Subarrays easy or hard?
Make Two Arrays Equal by Reversing Subarrays is classified as an Easy problem. The main insight is recognizing that reversing subarrays allows any permutation, so the problem reduces to checking whether both arrays contain the same elements with identical frequencies.
Make Two Arrays Equal by Reversing Subarrays Python/Java solution
In Python or Java, the typical implementation either sorts both arrays and compares them or uses a hash map to count frequencies. Python often uses collections.Counter, while Java typically uses HashMap or sorts with Arrays.sort().
How to solve Make Two Arrays Equal by Reversing Subarrays in O(n)?
Create a hash map storing frequencies of elements from the target array. Traverse the arr array and decrement the count for each value. If any value is missing or its count becomes negative, the arrays cannot match. If all counts end at zero, the arrays can be made equal using subarray reversals.
What is the best approach for Make Two Arrays Equal by Reversing Subarrays?
The best approach uses hashing to compare element frequencies in both arrays. Since reversing subarrays only changes order, both arrays must contain the same elements with the same counts. Using a hash map allows you to verify this in O(n) time and O(n) space.
Is Make Two Arrays Equal by Reversing Subarrays asked at Google/Amazon/Meta?
Problems involving array transformations and frequency comparison appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the core idea—checking whether two arrays are permutations of each other—is a common interview pattern.
What data structure is used in Make Two Arrays Equal by Reversing Subarrays?
The optimal solution uses a hash table (hash map) to store element frequencies. This allows constant-time updates and lookups while comparing counts between the two arrays.
What is the time complexity of Make Two Arrays Equal by Reversing Subarrays?
Two common solutions exist. Sorting both arrays and comparing them takes O(n log n) time. Using a hash map to count frequencies runs in O(n) time with O(n) extra space, which is the optimal approach.