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; }