Make Two Arrays Equal by Reversing Sub-arrays Leetcode Solution

The problem Make Two Arrays Equal by Reversing Sub-arrays Leetcode Solution provides us with two arrays. One of them is a target array and the other is an input array. Using the input array, we need to make the target array. We can reverse any of the sub-array in the input array. But we cannot change the elements of the input array. We do not need to find a way for how to perform the manipulation. Return true if possible else false. So, as usual before diving deep into the solution let us take a look at a few examples.

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

true

Explanation: We can reverse the first sub-array from index 0 to 2, then we reverse the sub-array from 1 to 2. In the end, we reverse index 2 to 3. And in this way, we can make the target array. It can be better understood by taking a look at the above image.

Table of Contents

Approach for Make Two Arrays Equal by Reversing Sub-arrays Leetcode Solution

The problem can be easily solved using counting method. The counting method is some of the standard algorithms. It is used in count sort as well as in many other questions. so here we keep count of elements from the target array. Then we traverse the elements of the input array. When we encounter any element, we decrement its count from the frequency or count array. If somehow during this operation, any index holds a negative value we return false.

A negative count in the frequency array shows the input array has a larger count for an element. But how does doing this solve the problem? The answer is simple once you know the observation. Once you try to perform some the reversals of sub-arrays. You can easily figure out that you can place any element of the input array at any place wherever you want. So, using this rule we need to check if the elements in the target array are the same as that of the input array.

Code for Make Two Arrays Equal by Reversing Sub-arrays Leetcode Solution

C++ code

#include <bits/stdc++.h>
using namespace std;

bool canBeEqual(vector<int>& target, vector<int>& arr) {
    vector<int> cnt(1001, 0);
    for(int i=0;i<target.size();i++)
        ++cnt[target[i]];
    for (int i=0;i<arr.size();i++) {
        if (--cnt[arr[i]] < 0) {
            return false;
        }
    }
    return true;
}

int main(){
    vector<int> target = {1, 2, 3, 4};
    vector<int> arr = {2, 3, 1, 4};
    cout<<(canBeEqual(target, arr) ? "true" : "false");
}

true

Java code

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static boolean canBeEqual(int[] target, int[] arr) {
        int[] cnt = new int[1001];
        for(int i=0;i<target.length;i++)
            ++cnt[target[i]];
        for (int i=0;i<arr.length;i++) {
            if (--cnt[arr[i]] < 0) {
                return false;
            }
        }
        return true;
    }
    
  public static void main (String[] args) throws java.lang.Exception
  {
    int[] target = {1, 2, 3, 4};
      int[] arr = {2, 3, 1, 4};
      System.out.print(canBeEqual(target, arr) ? "true" : "false");
  }
}

true

Make Two Arrays Equal by Reversing Sub-arrays Leetcode Solution

Approach for Make Two Arrays Equal by Reversing Sub-arrays Leetcode Solution

Code for Make Two Arrays Equal by Reversing Sub-arrays Leetcode Solution

C++ code

Java code

Complexity Analysis

Time Complexity

Space Complexity