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

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

✓ Brute Force Simulation

⏱️ Time: O(n²) Space: O(n)

For each possible number of right shifts (0 to n-1), simulate the rotation and count matching indices. Keep track of the maximum matches found.

Optimized Single Pass

⏱️ Time: O(n²) Space: O(1)

Instead of creating rotated arrays, we simulate the effect by checking what each element of nums1 would match at different shift positions. This avoids array creation overhead.

Brute Force Simulation — Algorithm Steps

Try 0, 1, 2, ..., n-1 right shifts
For each shift count, rotate nums1 and count matches
Return maximum matches found

Visualization

Tap to expand

Step-by-Step Walkthrough

Original

nums1 = [1,2,3], nums2 = [3,1,2]

Try Shifts

Test 0, 1, 2 right shifts

Count Matches

Find maximum matching indices

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++) {
        // Create rotated version of nums1
        int* rotated = (int*)malloc(n * sizeof(int));
        for (int i = 0; i < n; i++) {
            rotated[(i + shifts) % n] = nums1[i];
        }
        
        // Count matches
        int matches = 0;
        for (int i = 0; i < n; i++) {
            if (rotated[i] == nums2[i]) {
                matches++;
            }
        }
        
        if (matches > maxMatches) {
            maxMatches = matches;
        }
        
        free(rotated);
    }
    
    return maxMatches;
}

int parseArray(char* line, int* arr) {
    int n = 0;
    char* p = line;
    
    // Skip opening bracket
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    
    // Parse numbers
    while (*p && *p != ']') {
        if (*p >= '0' && *p <= '9') {
            arr[n] = 0;
            while (*p >= '0' && *p <= '9') {
                arr[n] = arr[n] * 10 + (*p - '0');
                p++;
            }
            n++;
        } else {
            p++;
        }
    }
    
    return n;
}

int main() {
    char line1[1000], line2[1000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    int nums1[100], nums2[100];
    int n1 = parseArray(line1, nums1);
    int n2 = parseArray(line2, nums2);
    
    int result = solution(nums1, nums2, n1);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Outer loop runs n times, inner loop counts n elements each time

⚠ Quadratic Growth

Space Complexity

O(n)

Creates rotated array copy for each shift attempt

⚡ Linearithmic 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

Maximum Number of Matching Indices After Right Shifts - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler