Make Two Arrays Equal by Reversing Subarrays - Video Solutions

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.