Welcome to Subscribe On Youtube

3400. Maximum Number of Matching Indices After Right Shifts 🔒

Description

You are given two integer arrays, nums1 and nums2, of the same length.

An index i is considered matching if nums1[i] == nums2[i].

Return the maximum number of matching indices after performing any number of right shifts on nums1.

A right shift is defined as shifting the element at index i to index (i + 1) % n, for all indices.

 

Example 1:

Input: nums1 = [3,1,2,3,1,2], nums2 = [1,2,3,1,2,3]

Output: 6

Explanation:

If we right shift nums1 2 times, it becomes [1, 2, 3, 1, 2, 3]. Every index matches, so the output is 6.

Example 2:

Input: nums1 = [1,4,2,5,3,1], nums2 = [2,3,1,2,4,6]

Output: 3

Explanation:

If we right shift nums1 3 times, it becomes [5, 3, 1, 1, 4, 2]. Indices 1, 2, and 4 match, so the output is 3.

 

Constraints:

  • nums1.length == nums2.length
  • 1 <= nums1.length, nums2.length <= 3000
  • 1 <= nums1[i], nums2[i] <= 109

Solutions

Solution 1: Enumeration

We can enumerate the number of right shifts $k$, where $0 \leq k < n$. For each $k$, we can calculate the number of matching indices between the array $\textit{nums1}$ after right shifting $k$ times and $\textit{nums2}$. The maximum value is taken as the answer.

The time complexity is $O(n^2)$, where $n$ is the length of the array $\textit{nums1}$. The space complexity is $O(1)$.

  • class Solution {
        public int maximumMatchingIndices(int[] nums1, int[] nums2) {
            int n = nums1.length;
            int ans = 0;
            for (int k = 0; k < n; ++k) {
                int t = 0;
                for (int i = 0; i < n; ++i) {
                    if (nums1[(i + k) % n] == nums2[i]) {
                        ++t;
                    }
                }
                ans = Math.max(ans, t);
            }
            return ans;
        }
    }
    
    
  • class Solution {
    public:
        int maximumMatchingIndices(vector<int>& nums1, vector<int>& nums2) {
            int n = nums1.size();
            int ans = 0;
            for (int k = 0; k < n; ++k) {
                int t = 0;
                for (int i = 0; i < n; ++i) {
                    if (nums1[(i + k) % n] == nums2[i]) {
                        ++t;
                    }
                }
                ans = max(ans, t);
            }
            return ans;
        }
    };
    
    
  • class Solution:
        def maximumMatchingIndices(self, nums1: List[int], nums2: List[int]) -> int:
            n = len(nums1)
            ans = 0
            for k in range(n):
                t = sum(nums1[(i + k) % n] == x for i, x in enumerate(nums2))
                ans = max(ans, t)
            return ans
    
    
  • func maximumMatchingIndices(nums1 []int, nums2 []int) (ans int) {
    	n := len(nums1)
    	for k := range nums1 {
    		t := 0
    		for i, x := range nums2 {
    			if nums1[(i+k)%n] == x {
    				t++
    			}
    		}
    		ans = max(ans, t)
    	}
    	return
    }
    
    
  • function maximumMatchingIndices(nums1: number[], nums2: number[]): number {
        const n = nums1.length;
        let ans: number = 0;
        for (let k = 0; k < n; ++k) {
            let t: number = 0;
            for (let i = 0; i < n; ++i) {
                if (nums1[(i + k) % n] === nums2[i]) {
                    ++t;
                }
            }
            ans = Math.max(ans, t);
        }
        return ans;
    }
    
    

All Problems

All Solutions