Skip to main content
Talentd

Maximum Number of Matching Indices After Right Shifts - Solution & Explanation

MediumPremiumFree on FleetCodeArrayTwo PointersSimulation6 min read
Practice this problem

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.length
  • 1 <= nums1.length, nums2.length <= 3000
  • 1 <= 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.

Solution

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 nums1 after right shifting k times and nums2. The maximum value is taken as the answer.

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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Shift Enumeration / SimulationO(n²)O(1)Good for understanding the rotation mechanics or when n is small
Shift Counting with Index MappingO(n) averageO(n)Best for large arrays; avoids repeated rotation simulation

Video Solution

3400. Maximum Number of Matching Indices After Right Shifts (Leetcode Medium) • Programming Live with Larry • 293 views views

Frequently Asked Questions

Is Maximum Number of Matching Indices After Right Shifts easy or hard?
Maximum Number of Matching Indices After Right Shifts is generally classified as a Medium difficulty problem. The brute-force idea is straightforward, but recognizing that matching pairs imply a unique rotation shift is the key insight that leads to the optimal linear-time solution.
Maximum Number of Matching Indices After Right Shifts Python/Java solution
Typical implementations iterate through indices and compute the shift needed to align matching elements. A frequency map tracks how often each shift occurs. The maximum frequency represents the best rotation. The same logic works in Python, Java, C++, Go, and TypeScript with O(n) average time complexity.
How to solve Maximum Number of Matching Indices After Right Shifts in O(n)?
Iterate through elements of nums1 and nums2. When nums1[i] equals nums2[j], compute the shift required to align them using k = (j - i + n) % n. Track how many pairs produce the same shift using a hash map or frequency array. The shift with the highest frequency yields the maximum number of matching indices.
What is the best approach for Maximum Number of Matching Indices After Right Shifts?
The most efficient approach counts how many element pairs align for each possible rotation shift. For every pair where nums1[i] equals nums2[j], compute the shift k = (j - i + n) % n and increment its frequency. The shift with the highest count gives the maximum matching indices. This method runs in O(n) average time with O(n) extra space.
Is Maximum Number of Matching Indices After Right Shifts asked at Google/Amazon/Meta?
Rotation alignment and cyclic array matching problems appear frequently in interviews at large tech companies such as Google, Amazon, and Meta. Variants often test understanding of array rotations, modular arithmetic, and counting strategies to reduce brute-force simulations.
What data structure is used in Maximum Number of Matching Indices After Right Shifts?
The optimized solution uses arrays or hash maps to count how many element pairs correspond to each rotation shift. The problem itself revolves around array traversal and modular index calculations, sometimes combined with frequency counting.
What is the time complexity of Maximum Number of Matching Indices After Right Shifts?
The brute-force simulation checks all n rotations and compares n elements per rotation, resulting in O(n^2) time. An optimized shift-counting approach reduces the complexity to O(n) on average by computing the rotation that aligns matching values and counting frequencies.

Ready to solve this problem?

Practice Maximum Number of Matching Indices After Right Shifts with our built-in code editor and test cases.

Practice on FleetCode
Previous

Rotate Array