Maximum Number of Matching Indices After Right Shifts

Maximum Number of Matching Indices After Right Shifts - Problem

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.

Input & Output

Example 1 — Perfect Match After One Shift

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

› Output: 3

💡 Note: After 1 right shift, nums1 becomes [3,1,2] which perfectly matches nums2, giving us 3 matching indices.

Example 2 — Partial Matches

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

› Output: 2

💡 Note: After 3 right shifts, nums1 becomes [2,3,4,1]. This matches nums2 at indices 1 and 2, giving us 2 matches.

Example 3 — No Improvement

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

› Output: 0

💡 Note: No elements match regardless of rotation since all elements in nums1 are 1 and all in nums2 are 2.

Constraints

1 ≤ nums1.length, nums2.length ≤ 100
nums1.length == nums2.length
1 ≤ nums1[i], nums2[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

nums1=[1,2,3], nums2=[3,1,2] - initially 0 matches

Apply Right Shift

1 right shift moves each element one position right (with wraparound)

Count Matches

After shift: [3,1,2] matches [3,1,2] perfectly = 3 matches

Key Takeaway

🎯 Key Insight: Try all n possible rotations to find the alignment that maximizes matching indices

Asked in

M Microsoft 15 a Amazon 12 G Google 8

The key insight is that there are only n possible right shifts to try. We can check each rotation in O(n) time by either creating rotated arrays or calculating positions mathematically. Best approach uses O(1) space by avoiding array creation. Time: O(n²), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Single Pass	O(n²)	O(1)	Check all rotations without creating new arrays
Brute Force Simulation	O(n²)	O(n)	Try all possible right shifts and count matches for each

Optimized Single Pass — Algorithm Steps

For each possible shift count
Count matches by checking nums1[i] against nums2[(i+shift)%n]
Track maximum without creating arrays

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Position

For position i after k shifts, original was at (i-k+n)%n

Direct Comparison

Compare nums1[originalPos] with nums2[i]

Count Efficiently

Track maximum without extra memory

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums1, int* nums2, int n) {
    int maxMatches = 0;
    
    // Try all possible right shifts (0 to n-1)
    for (int shifts = 0; shifts < n; shifts++) {
        int matches = 0;
        // Count matches without creating rotated array
        for (int i = 0; i < n; i++) {
            int originalPos = (i - shifts + n) % n;
            if (nums1[originalPos] == nums2[i]) {
                matches++;
            }
        }
        
        if (matches > maxMatches) {
            maxMatches = matches;
        }
    }
    
    return maxMatches;
}

int main() {
    char line1[1000], line2[1000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    // Parse arrays (simple parsing for format [1,2,3])
    int nums1[100], nums2[100];
    int n = 0;
    
    char* token = strtok(line1 + 1, ",]");
    while (token != NULL) {
        nums1[n] = atoi(token);
        token = strtok(NULL, ",]");
        n++;
    }
    
    token = strtok(line2 + 1, ",]");
    int i = 0;
    while (token != NULL) {
        nums2[i] = atoi(token);
        token = strtok(NULL, ",]");
        i++;
    }
    
    int result = solution(nums1, nums2, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Outer loop for n shifts, inner loop counts n elements

⚠ Quadratic Growth

Space Complexity

O(1)

Only uses constant extra space for counters

✓ Linear Space

25.5K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Single Pass — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler