Maximum Number of Matching Indices After Right Shifts - Video Solutions
3400. Maximum Number of Matching Indices After Right Shifts (Leetcode Medium)
Maximum Number of Matching Indices After Right Shifts - Video Solution
Watch the video solution for Maximum Number of Matching Indices After Right Shifts, a medium level problem involving Array, Two Pointers, Simulation. This walkthrough by Programming Live with Larry has 293 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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.length1 <= nums1.length, nums2.length <= 30001 <= nums1[i], nums2[i] <= 109
Approach Overview
Problem Overview: You are given two arrays of equal length. You can perform any number of right shifts on the first array. After each rotation, count how many indices i satisfy nums1[i] == nums2[i]. The goal is to return the maximum possible number of matching indices across all right shifts.
Approach 1: Shift Enumeration / Simulation (O(n²) time, O(1) space)
The most direct strategy is to simulate every possible right shift. For a shift k, element nums1[(i - k + n) % n] lands at index i. Iterate through all indices and count matches with nums2[i]. Repeat this process for all k from 0 to n-1 and track the maximum count. This approach uses simple array traversal and modular indexing, making it easy to implement and reliable for smaller input sizes.
Approach 2: Shift Counting with Index Mapping (O(n) average time, O(n) space)
A rotation by k shifts every element in nums1 from index i to (i + k) % n. If nums1[i] == nums2[j], the shift that aligns them is k = (j - i + n) % n. Iterate through both arrays and record how many element pairs produce the same shift value. Each time a pair matches, increment the frequency of that shift. The shift with the highest frequency produces the maximum matching indices.
This technique converts the rotation problem into a counting problem. Instead of simulating each rotation, you compute which rotation would align matching values and accumulate frequencies. A hash map or array of size n stores shift counts. This avoids repeated comparisons and reduces the runtime significantly. The logic is closely related to cyclic alignment problems in array processing and rotational matching patterns often solved with two pointers or index arithmetic.
Recommended for interviews: Start by describing the brute-force rotation simulation to show you understand how the shift works. Then move to the shift-counting optimization. Interviewers typically expect you to recognize that every matching pair implies exactly one valid shift and that counting these shifts yields the optimal solution in linear time.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Shift Enumeration / Simulation | O(n²) | O(1) | Good for understanding the rotation mechanics or when n is small |
| Shift Counting with Index Mapping | O(n) average | O(n) | Best for large arrays; avoids repeated rotation simulation |