Check if two arrays can be made equal by reversing any subarray once

0 0 7 minutes read

Given two arrays A[] and B[] of equal size N, the task is to check whether A[] can be made equal to B[] by reversing any sub-array of A only once.

Examples:

Input: A[] = {1, 3, 2, 4}
B[] = {1, 2, 3, 4}
Output: Yes
Explanation:
The sub-array {3, 2} can be reversed to {2, 3}, which makes A equal to B.

Input: A[] = {1, 4, 2, 3}
B[] = {1, 2, 3, 4}
Output: No
Explanation:
There is no sub-array of A which, when reversed, makes A equal to B.

Naive Approach: Check for all sub-arrays of A[] and compare the two arrays after reversing the sub-array.
Time complexity: O(N²).

Efficient Approach:

First, find the starting and the ending index of the sub-array not equal in A and B.
Then, by reversing the required sub-array, we can check whether A can be made equal to B or not.
The starting index is the first index in the arrays for which A[i] != B[i] and the ending index is the last index in arrays for which A[i] != B[i].

Below is the implementation of the above approach.

C++

// C++ implementation to
// check whether two arrays
// can be made equal by
// reversing a sub-array
// only once
#include <bits/stdc++.h>
using namespace std;
 
// Function to check whether two arrays
// can be made equal by reversing
// a sub-array only once
void checkArray(int A[], int B[], int N)
{
    // Integer variable for
    // storing the required
    // starting and ending
    // indices in the array
    int start = 0;
    int end = N - 1;
 
    // Finding the smallest index
    // for which A[i] != B[i]
    // i.e the starting index
    // of the unequal sub-array
    for (int i = 0; i < N; i++) {
        if (A[i] != B[i]) {
            start = i;
            break;
        }
    }
    // Finding the largest index
    // for which A[i] != B[i]
    // i.e the ending index
    // of the unequal sub-array
    for (int i = N - 1; i >= 0; i--) {
        if (A[i] != B[i]) {
            end = i;
            break;
        }
    }
 
    // Reversing the sub-array
    // A[start], A[start+1] .. A[end]
    reverse(A + start, A + end + 1);
 
    // Checking whether on reversing
    // the sub-array A[start]...A[end]
    // makes the arrays equal
 
    for (int i = 0; i < N; i++) {
        if (A[i] != B[i]) {
            // If any element of the
            // two arrays is unequal
            // print No and return
            cout << "No" << endl;
            return;
        }
    }
    // Print Yes if arrays are
    // equal after reversing
    // the sub-array
    cout << "Yes" << endl;
}
// Driver code
int main()
{
    int A[] = { 1, 3, 2, 4 };
    int B[] = { 1, 2, 3, 4 };
    int N = sizeof(A) / sizeof(A[0]);
    checkArray(A, B, N);
 
    return 0;
}

Java

// Java implementation to
// check whether two arrays
// can be made equal by
// reversing a sub-array
// only once
import java.util.*; 
class GFG{
  
// Function to check whether two arrays
// can be made equal by reversing
// a sub-array only once
static void checkArray(int A[], int B[], int N)
{
    // Integer variable for
    // storing the required
    // starting and ending
    // indices in the array
    int start = 0;
    int end = N - 1;
  
    // Finding the smallest index
    // for which A[i] != B[i]
    // i.e the starting index
    // of the unequal sub-array
    for (int i = 0; i < N; i++) 
    {
        if (A[i] != B[i]) 
        {
            start = i;
            break;
        }
    }
    // Finding the largest index
    // for which A[i] != B[i]
    // i.e the ending index
    // of the unequal sub-array
    for (int i = N - 1; i >= 0; i--)
    {
        if (A[i] != B[i])
        {
            end = i;
            break;
        }
    }
  
    // Reversing the sub-array
    // A[start], A[start+1] .. A[end]
    Collections.reverse(Arrays.asList(A)); 
  
    // Checking whether on reversing
    // the sub-array A[start]...A[end]
    // makes the arrays equal
    for (int i = 0; i < N; i++) 
    {
        if (A[i] != B[i])
        {
            // If any element of the
            // two arrays is unequal
            // print No and return
            System.out.println("No");
            return;
        }
    }
    // Print Yes if arrays are
    // equal after reversing
    // the sub-array
   System.out.println("Yes");
}
// Driver code
public static void main(String[] args) 
{
    int A[] = { 1, 3, 2, 4 };
    int B[] = { 1, 2, 3, 4 };
    int N = A.length;
    checkArray(A, B, N);
}
}
 
// This Code is contributed by rock_cool

Python3

# Python3 implementation to
# check whether two arrays
# can be made equal by
# reversing a sub-array
# only once
 
# Function to check whether two arrays
# can be made equal by reversing
# a sub-array only once
def checkArray(A, B, N):
     
    # Integer variable for
    # storing the required
    # starting and ending
    # indices in the array
    start = 0
    end = N - 1
 
    # Finding the smallest index
    # for which A[i] != B[i]
    # i.e the starting index
    # of the unequal sub-array
    for i in range(N):
        if (A[i] != B[i]):
            start = i
            break
             
    # Finding the largest index
    # for which A[i] != B[i]
    # i.e the ending index
    # of the unequal sub-array
    for i in range(N - 1, -1, -1):
        if (A[i] != B[i]):
            end = i
            break
 
    # Reversing the sub-array
    # A[start], A[start+1] .. A[end]
    A[start:end + 1] = reversed(A[start:end + 1])
     
    # Checking whether on reversing
    # the sub-array A[start]...A[end]
    # makes the arrays equal
    for i in range(N):
        if (A[i] != B[i]):
             
            # If any element of the
            # two arrays is unequal
            # print No and return
            print("No")
            return
             
    # Print Yes if arrays are
    # equal after reversing
    # the sub-array
    print("Yes")
     
# Driver code
if __name__ == '__main__':
     
    A = [ 1, 3, 2, 4 ]
    B = [ 1, 2, 3, 4 ]
    N = len(A)
     
    checkArray(A, B, N)
     
# This code is contributed by mohit kumar 29

C#

// C# implementation to
// check whether two arrays
// can be made equal by
// reversing a sub-array
// only once
using System;
 
class GFG{
 
// Function to check whether two arrays
// can be made equal by reversing
// a sub-array only once
static void checkArray(int []A, int []B, int N)
{
     
    // Integer variable for
    // storing the required
    // starting and ending
    // indices in the array
    int start = 0;
    int end = N - 1;
 
    // Finding the smallest index
    // for which A[i] != B[i]
    // i.e the starting index
    // of the unequal sub-array
    for(int i = 0; i < N; i++) 
    {
        if (A[i] != B[i]) 
        {
            start = i;
            break;
        }
    }
     
    // Finding the largest index
    // for which A[i] != B[i]
    // i.e the ending index
    // of the unequal sub-array
    for(int i = N - 1; i >= 0; i--)
    {
        if (A[i] != B[i])
        {
            end = i;
            break;
        }
    }
 
    // Reversing the sub-array
    // A[start], A[start+1] .. A[end]
    Array.Reverse(A, start, end);
 
 
    // Checking whether on reversing
    // the sub-array A[start]...A[end]
    // makes the arrays equal
    for(int i = 0; i < N; i++) 
    {
        if (A[i] != B[i])
        {
             
            // If any element of the
            // two arrays is unequal
            // print No and return
            Console.Write("No");
            return;
        }
    }
     
    // Print Yes if arrays are
    // equal after reversing
    // the sub-array
    Console.Write("Yes");
}
 
// Driver code
public static void Main(string[] args) 
{
    int []A = { 1, 3, 2, 4 };
    int []B = { 1, 2, 3, 4 };
    int N = A.Length;
    checkArray(A, B, N);
}
}
 
// This code is contributed by rutvik_56

Javascript

<script>
 
 
// Javascript implementation to
// check whether two arrays
// can be made equal by
// reversing a sub-array
// only once
 
// Function to check whether two arrays
// can be made equal by reversing
// a sub-array only once
function checkArray(A, B, N)
{
    // Integer variable for
    // storing the required
    // starting and ending
    // indices in the array
    var start = 0;
    var end = N - 1;
 
    // Finding the smallest index
    // for which A[i] != B[i]
    // i.e the starting index
    // of the unequal sub-array
    for (var i = 0; i < N; i++) {
        if (A[i] != B[i]) {
            start = i;
            break;
        }
    }
    // Finding the largest index
    // for which A[i] != B[i]
    // i.e the ending index
    // of the unequal sub-array
    for (var i = N - 1; i >= 0; i--) {
        if (A[i] != B[i]) {
            end = i;
            break;
        }
    }
 
    // Reversing the sub-array
    // A[start], A[start+1] .. A[end]
    var l = start;
    var r = end;
    var d = parseInt((r-l+2)/2);
      for(var i=0;i<d;i++)
      {
         var t = A[l+i];
         A[l+i] = A[r-i];
         A[r-i] = t;
      }
 
    // Checking whether on reversing
    // the sub-array A[start]...A[end]
    // makes the arrays equal
 
    for (var i = 0; i < N; i++) {
        if (A[i] != B[i]) {
            // If any element of the
            // two arrays is unequal
            // print No and return
            document.write( "No" );
            return;
        }
    }
    // Print Yes if arrays are
    // equal after reversing
    // the sub-array
    document.write( "Yes" );
}
// Driver code
var A = [1, 3, 2, 4];
var B = [1, 2, 3, 4];
var N = A.length;
checkArray(A, B, N);
 
 
</script>

Output:

Yes

Time Complexity: O(N)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!