Make Two Arrays Equal by Reversing Subarrays

easy hashing frequency count array

Problem

You are given two integer arrays of equal length target and arr. In one step you may pick any non-empty subarray of arr and reverse it, and you may do this any number of times. Return true if you can make arr equal to target, otherwise false. Reversing subarrays can reorder the elements arbitrarily, so the answer is true exactly when both arrays contain the same values with the same multiplicities.

Inputtarget = [1,2,3,4], arr = [2,4,1,3]

Outputtrue

Both arrays are permutations of {1,2,3,4}, so a sequence of reversals turns arr into target.

Inputtarget = [3,7,9], arr = [3,7,11]

Outputfalse

arr has an 11 but no 9, so no amount of reversing can match target.

target (comma-separated)

arr (comma-separated)

def can_be_equal(target, arr):
    count = {}
    for v in target:
        count[v] = count.get(v, 0) + 1
    for v in arr:
        if v not in count or count[v] == 0:
            return False
        count[v] -= 1
    return True

function canBeEqual(target, arr) {
  const count = new Map();
  for (const v of target) {
    count.set(v, (count.get(v) || 0) + 1);
  }
  for (const v of arr) {
    if (!count.get(v)) return false;
    count.set(v, count.get(v) - 1);
  }
  return true;
}

boolean canBeEqual(int[] target, int[] arr) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int v : target) {
        count.merge(v, 1, Integer::sum);
    }
    for (int v : arr) {
        int c = count.getOrDefault(v, 0);
        if (c == 0) return false;
        count.put(v, c - 1);
    }
    return true;
}

bool canBeEqual(vector<int>& target, vector<int>& arr) {
    unordered_map<int, int> count;
    for (int v : target) {
        count[v]++;
    }
    for (int v : arr) {
        if (count[v] == 0) return false;
        count[v]--;
    }
    return true;
}

Explanation

The operation we are allowed — reverse any subarray, any number of times — is powerful enough to produce any permutation of arr. Reversing two-element windows is just an adjacent swap, and adjacent swaps generate every reordering. So the geometry of the moves does not matter at all.

That collapses the problem to a single question: do target and arr contain exactly the same values with the same counts? In other words, is one a permutation of the other? This is a classic frequency / multiset comparison, the natural home of a hash map.

We build a hash map count that tallies how many times each value appears in target. Then we walk through arr and, for each value, try to "spend" one unit from count. If the value is missing or its tally has already dropped to zero, the multisets differ and we return false.

If every element of arr is consumed successfully, the two arrays held identical multisets and every tally ends at zero, so we return true. The arrays are guaranteed to have equal length, which is what lets a single decrementing pass be conclusive.

Each value is touched a constant number of times, giving linear time, and the hash map stores at most one entry per distinct value, giving linear space. Sorting both arrays is an alternative but slower O(n log n) approach.

Time: O(n) Space: O(n)