Make Two Arrays Equal by Reversing Subarrays

Easy
1103.

Make Two Arrays Equal by Reversing Subarrays

Make Two Arrays Equal by Reversing Subarrays is an easy coding problem on arrays, hash table and sorting, asked in Amazon and Meta interviews.

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.length
  • 1 <= target.length <= 1000
  • 1 <= target[i] <= 1000
  • 1 <= arr[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} target
 * @param {number[]} arr
 * @return {boolean}
 */
var canBeEqual = function(target, arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.length
  • 1 <= target.length <= 1000
  • 1 <= target[i] <= 1000
  • 1 <= arr[i] <= 1000

Hints for Make Two Arrays Equal by Reversing Subarrays

  1. Hint 1

    Reversing a subarray of length 2 swaps two neighbours.

  2. Hint 2

    Adjacent swaps are enough to sort any array — so they can produce any arrangement of the same values.

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

  1. Keep a count per value (values are at most 1000).
  2. Add 1 for every value of target and subtract 1 for every value of arr.
  3. Return true if 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