Given two arrays A[] and B[] of N unique elements, the task is to find the maximum number of matched elements from the two given arrays.
Elements of the two arrays are matched if they are of the same value and can be placed at the same index (0-based indexing).(By right shift or left shift of the two arrays).
Examples:
Input: A[] = { 5, 3, 7, 9, 8 }, B[] = { 8, 7, 3, 5, 9 }
Output: 3
Explanation: Left shifting B[] by 1 index modifies B[] to { 7, 3, 5, 9, 8 }.
Therefore, elements in indices 1, 3 and 4 match. Therefore, the required count is 3.Input: A[] = { 9, 5, 6, 2 }, B[] = { 6, 2, 9, 5 }
Output: 4
Naive Approach: The simplest approach to solve this problem is to observe that one right shift is the same as the (N-1) left shift, so perform only one type of shift, say right shift. Also, performing the right shift on A is the same as performing left shift B, so perform the right shift on only one array, say on A[]. Apply the right shift operations on A while keeping B as it is and compare all the values of A and B to find the total number of matches and keep track of the maximum of all.
Time complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by using a Map to keep track of the difference between indices of equal elements present in arrays A[] and B[]. If the difference comes out to be negative, then change A[] by doing k( = N + difference) left shifts, which is equivalent to N – K right shifts.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count maximum matched // elements from the arrays A[] and B[] int maxMatch(int A[], int B[], int M, int N){ // Stores position of elements of // array A[] in the array B[] map<int,int> Aindex; // Keep track of difference // between the indices map<int,int> diff; // Traverse the array A[] for(int i = 0; i < M; i++) { Aindex[A[i]] = i ; } // Traverse the array B[] for(int i = 0; i < N; i++) { // If difference is negative, add N to it if (i - Aindex[B[i]] < 0) { diff[M + i - Aindex[B[i]]] += 1; } // Keep track of the number of shifts // required to place elements at same indices else { diff[i - Aindex[B[i]]] += 1; } } // Return the max matches int max = 0; for(auto ele = diff.begin(); ele != diff.end(); ele++) { if(ele->second > max) { max = ele->second; } } return max; }// Driver codeint main(){ int A[] = { 5, 3, 7, 9, 8 }; int B[] = { 8, 7, 3, 5, 9 }; int M = sizeof(A) / sizeof(A[0]); int N = sizeof(B) / sizeof(B[0]); // Returns the count // of matched elements cout << maxMatch(A, B, M, N); return 0;}// This code is contributed by divyeshrabadiya07 |
Java
// Java program for the above approach import java.io.Console;import java.util.HashMap;import java.util.Map;class GFG{ // Function to count maximum matched // elements from the arrays A[] and B[] static int maxMatch(int[] A, int[] B) { // Stores position of elements of // array A[] in the array B[] HashMap<Integer, Integer> Aindex = new HashMap<Integer, Integer>(); // Keep track of difference // between the indices HashMap<Integer, Integer> diff = new HashMap<Integer, Integer>(); // Traverse the array A[] for (int i = 0; i < A.length; i++) { Aindex.put(A[i], i); } // Traverse the array B[] for (int i = 0; i < B.length; i++) { // If difference is negative, add N to it if (i - Aindex.get(B[i]) < 0) { if (!diff.containsKey(A.length + i - Aindex.get(B[i]))) { diff.put(A.length + i - Aindex.get(B[i]), 1); } else { diff.put(A.length + i - Aindex.get(B[i]), diff.get(A.length + i - Aindex.get(B[i])) + 1); } } // Keep track of the number of shifts // required to place elements at same indices else { if (!diff.containsKey(i - Aindex.get(B[i]))) { diff.put(i - Aindex.get(B[i]), 1); } else { diff.put(i - Aindex.get(B[i]), diff.get(i - Aindex.get(B[i])) + 1); } } } // Return the max matches int max = 0; for (Map.Entry<Integer, Integer> ele : diff.entrySet()) { if (ele.getValue() > max) { max = ele.getValue(); } } return max; } // Driver Code public static void main(String[] args) { int[] A = { 5, 3, 7, 9, 8 }; int[] B = { 8, 7, 3, 5, 9 }; // Returns the count // of matched elements System.out.println(maxMatch(A, B)); }}// This code is contributed by 29AjayKumar |
Python3
# Python program for the above approach# Function to count maximum matched# elements from the arrays A[] and B[]def maxMatch(A, B): # Stores position of elements of # array A[] in the array B[] Aindex = {} # Keep track of difference # between the indices diff = {} # Traverse the array A[] for i in range(len(A)): Aindex[A[i]] = i # Traverse the array B[] for i in range(len(B)): # If difference is negative, add N to it if i-Aindex[B[i]] < 0: if len(A)+i-Aindex[B[i]] not in diff: diff[len(A)+i-Aindex[B[i]]] = 1 else: diff[len(A)+i-Aindex[B[i]]] += 1 # Keep track of the number of shifts # required to place elements at same indices else: if i-Aindex[B[i]] not in diff: diff[i-Aindex[B[i]]] = 1 else: diff[i-Aindex[B[i]]] += 1 # Return the max matches return max(diff.values())# Driver CodeA = [5, 3, 7, 9, 8]B = [8, 7, 3, 5, 9]# Returns the count # of matched elementsprint(maxMatch(A, B)) |
C#
// C# program for the above approach using System;using System.Collections.Generic; class GFG{ // Function to count maximum matched // elements from the arrays A[] and B[] static int maxMatch(int[] A, int[] B){ // Stores position of elements of // array A[] in the array B[] Dictionary<int, int> Aindex = new Dictionary<int, int>(); // Keep track of difference // between the indices Dictionary<int, int> diff = new Dictionary<int, int>(); // Traverse the array A[] for(int i = 0; i < A.Length; i++) { Aindex[A[i]] = i ; } // Traverse the array B[] for(int i = 0; i < B.Length; i++) { // If difference is negative, add N to it if (i - Aindex[B[i]] < 0) { if (!diff.ContainsKey(A.Length + i - Aindex[B[i]])) { diff[A.Length + i - Aindex[B[i]]] = 1; } else { diff[A.Length + i - Aindex[B[i]]] += 1; } } // Keep track of the number of shifts // required to place elements at same indices else { if (!diff.ContainsKey(i - Aindex[B[i]])) { diff[i - Aindex[B[i]]] = 1; } else { diff[i - Aindex[B[i]]] += 1; } } } // Return the max matches int max = 0; foreach(KeyValuePair<int, int> ele in diff) { if (ele.Value > max) { max = ele.Value; } } return max; }// Driver Code static void Main() { int[] A = { 5, 3, 7, 9, 8 }; int[] B = { 8, 7, 3, 5, 9 }; // Returns the count // of matched elements Console.WriteLine(maxMatch(A, B));}}// This code is contributed by divyesh072019 |
Javascript
<script> // JavaScript program for the above approach // Function to count maximum matched // elements from the arrays A[] and B[] function maxMatch(A, B) { // Stores position of elements of // array A[] in the array B[] var Aindex = {}; // Keep track of difference // between the indices var diff = {}; // Traverse the array A[] for (var i = 0; i < A.length; i++) { Aindex[A[i]] = i; } // Traverse the array B[] for (var i = 0; i < B.length; i++) { // If difference is negative, add N to it if (i - Aindex[B[i]] < 0) { if (!diff.hasOwnProperty(A.length + i - Aindex[B[i]])) { diff[A.length + i - Aindex[B[i]]] = 1; } else { diff[A.length + i - Aindex[B[i]]] += 1; } } // Keep track of the number of shifts // required to place elements at same indices else { if (!diff.hasOwnProperty(i - Aindex[B[i]])) { diff[i - Aindex[B[i]]] = 1; } else { diff[i - Aindex[B[i]]] += 1; } } } // Return the max matches var max = 0; for (const [key, value] of Object.entries(diff)) { if (value > max) { max = value; } } return max; } // Driver Code var A = [5, 3, 7, 9, 8]; var B = [8, 7, 3, 5, 9]; // Returns the count // of matched elements document.write(maxMatch(A, B));</script> |
Output:
3
Time Complexity: O(M+N), where M and N are the sizes of the input arrays A and B, respectively.
Auxiliary Space: O(M+N)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
