We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Matching Indices After Right Shifts

Number: 3740

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given two integer arrays nums1 and nums2 of equal length, determine the maximum number of indices where the two arrays have the same value after performing any number of right shifts on nums1. A right shift moves every element of nums1 one position to the right (with the last element wrapping around to the first position).

Key Insights

  • A right shift on nums1 rotates the array, and we want to align as many elements as possible with nums2.
  • For any index i in nums1, after k right shifts, the element moves to index (i + k) mod n.
  • To get a match at an index j in nums2, for each element at index i in nums1, we want (i + k) mod n == j where nums1[i] == nums2[j]. This gives k = (j - i + n) mod n.
  • Counting the frequency of each shift k that results in a match across the arrays allows us to choose the optimal shift.

Space and Time Complexity

Time Complexity: O(n * m) in the worst-case scenario where m is the average occurrences of a number in nums2. With n bounded by 3000, this approach is acceptable. Space Complexity: O(n) for the hash map storing indices of nums2 values and O(n) for counting frequencies.

Solution

The idea is to precompute a mapping from each value in nums2 to its indices. Then, iterate over nums1 and for each element, check all corresponding positions in nums2 where the same value occurs. For each such pair, calculate the required shift (k = (j - i + n) % n) that would align these two elements. Count the frequency for each k and finally return the maximum frequency. This provides the maximum number of matching indices after an optimal right shift.

Code Solutions

# Python solution for Maximum Number of Matching Indices After Right Shifts

def max_matching_indices(nums1, nums2):
    n = len(nums1)
    # Build a mapping from value in nums2 to list of its indices
    indices_map = {}
    for i, val in enumerate(nums2):
        if val not in indices_map:
            indices_map[val] = []
        indices_map[val].append(i)
        
    shift_count = [0] * n  # Array to count frequency of shift k

    # For each element in nums1, check all matching indices in nums2
    for i, val in enumerate(nums1):
        if val in indices_map:
            for j in indices_map[val]:
                shift = (j - i + n) % n  # Determine required shift k
                shift_count[shift] += 1

    return max(shift_count)

# Example usage:
nums1 = [3,1,2,3,1,2]
nums2 = [1,2,3,1,2,3]
print(max_matching_indices(nums1, nums2))  # Output: 6
← Back to All Questions