Scale Engineer

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
ArrayHash 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.

  1. We create an integer array, counts, of size 1001 (to accommodate numbers from 1 to 1000) and initialize it with zeros.
  2. 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]].
  3. 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.
  4. 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.
  5. 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

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.

Solutions

class Solution {public  boolean canBeEqual(int[] target, int[] arr) {    Arrays.sort(target);    Arrays.sort(arr);    return Arrays.equals(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 →

Next problem