LeetCode 3400 - Maximum Number of Matching Indices After Right Shifts

The problem gives us two arrays, nums1 and nums2, both of the same length n. We are allowed to repeatedly perform a right circular shift on nums1. A right shift moves every element one position to the right, and the last element wraps around to the beginning.

leetcodemediumarraytwo-pointerssimulation

LeetCode Problem 3400

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Simulation

Solution

Problem Understanding

The problem gives us two arrays, nums1 and nums2, both of the same length n. We are allowed to repeatedly perform a right circular shift on nums1. A right shift moves every element one position to the right, and the last element wraps around to the beginning.

For example:

  • [1, 2, 3, 4]
  • after one right shift becomes [4, 1, 2, 3]
  • after two right shifts becomes [3, 4, 1, 2]

After applying any number of right shifts, we want to maximize the number of indices i where:

nums1[i] == nums2[i]

These are called matching indices.

The task is to compute the largest possible number of matching positions over all possible circular right shifts of nums1.

The constraints are important:

  • 1 <= n <= 3000
  • Array values can be as large as 10^9
  • Arrays may contain duplicates

The array size of 3000 is small enough that an O(n^2) solution is acceptable, since 3000^2 = 9,000,000, which is manageable in most programming languages. However, cubic solutions would be too slow.

There are several important edge cases to consider:

  • Arrays may already be identical, so zero shifts could be optimal.
  • Arrays may have no common values at all, resulting in zero matches regardless of shifts.
  • Arrays can contain many duplicate values, meaning multiple shifts may produce the same number of matches.
  • Arrays of length 1 must always return either 1 or 0 depending on equality.
  • Since shifts are circular, we must handle wraparound carefully using modulo arithmetic.

Approaches

Brute Force Approach

The most direct approach is to simulate every possible right shift of nums1.

There are exactly n distinct circular shifts. For each shift:

  1. Construct the shifted array.
  2. Compare it against nums2.
  3. Count how many indices match.
  4. Track the maximum count.

This works because trying every possible shift guarantees we eventually examine the optimal alignment.

However, constructing a shifted array for every shift introduces unnecessary work. If we explicitly rebuild the shifted array each time, the total complexity becomes:

  • O(n) shifts
  • each requiring O(n) construction
  • plus O(n) comparison

This can become O(n^2) or worse depending on implementation details.

Although O(n^2) is acceptable for this problem size, we can improve the implementation by avoiding explicit shifting.

Key Insight

Instead of physically shifting the array, we can determine directly which element from the original array would appear at each position after a given number of right shifts.

If we perform shift right shifts, then:

shifted[i] = nums1[(i - shift + n) % n]

So for every possible shift:

  • iterate through all indices
  • compare the implied shifted element with nums2[i]
  • count matches

This avoids creating temporary arrays and keeps the implementation clean and efficient.

The resulting complexity is still O(n^2), but with minimal overhead and straightforward logic.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Explicitly builds shifted arrays
Optimal O(n²) O(1) Uses index arithmetic instead of constructing shifts

Algorithm Walkthrough

  1. Let n be the length of the arrays.

We need to examine every possible circular right shift from 0 to n - 1. 2. Initialize a variable max_matches = 0.

This stores the best answer found so far. 3. For each possible shift value:

A shift value k means every element moves k positions to the right. 4. For the current shift, iterate through every index i.

Instead of actually shifting the array, compute which original element lands at index i. 5. Use circular indexing.

After k right shifts:

shifted[i] = nums1[(i - k + n) % n]

The modulo operation handles wraparound correctly. 6. Compare the shifted value with nums2[i].

If they are equal, increment the current match counter. 7. After checking all indices for the current shift:

Update:

max_matches = max(max_matches, current_matches)
  1. After all shifts are processed, return max_matches.

Why it works

A circular right shift only changes where elements appear, not their relative cyclic order. For any shift value k, the formula:

nums1[(i - k + n) % n]

correctly identifies which original element moves into position i.

Since the algorithm checks every possible shift and counts exact matches for each one, the maximum recorded value must be the optimal answer.

Python Solution

from typing import List

class Solution:
    def maximumMatchingIndices(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        max_matches = 0

        for shift in range(n):
            current_matches = 0

            for i in range(n):
                shifted_value = nums1[(i - shift + n) % n]

                if shifted_value == nums2[i]:
                    current_matches += 1

            max_matches = max(max_matches, current_matches)

        return max_matches

The implementation begins by storing the array length in n. Since there are exactly n distinct circular shifts, the outer loop iterates through every shift value from 0 to n - 1.

For each shift, the algorithm counts how many positions match. Instead of creating a shifted copy of nums1, it computes the shifted element directly using modular arithmetic.

The expression:

(i - shift + n) % n

maps the current index in the shifted array back to the correct index in the original array. Adding n ensures the value stays non-negative before applying modulo.

Whenever the shifted value equals nums2[i], the match counter increases. After processing all indices for a shift, the algorithm updates the global maximum.

The final answer is the largest match count encountered across all shifts.

Go Solution

func maximumMatchingIndices(nums1 []int, nums2 []int) int {
    n := len(nums1)
    maxMatches := 0

    for shift := 0; shift < n; shift++ {
        currentMatches := 0

        for i := 0; i < n; i++ {
            shiftedValue := nums1[(i-shift+n)%n]

            if shiftedValue == nums2[i] {
                currentMatches++
            }
        }

        if currentMatches > maxMatches {
            maxMatches = currentMatches
        }
    }

    return maxMatches
}

The Go implementation follows the same logic as the Python version. Go arrays are handled as slices, so indexing works naturally with modular arithmetic.

One small difference is that Go does not provide a built-in max function for integers, so the code uses a simple conditional comparison instead.

Integer overflow is not a concern because the indices and counts remain within the bounds of the array size, which is at most 3000.

Worked Examples

Example 1

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

Length:

n = 6

We test every shift.

Shift Shifted nums1 Matching Indices Match Count
0 [3,1,2,3,1,2] none 0
1 [2,3,1,2,3,1] none 0
2 [1,2,3,1,2,3] 0,1,2,3,4,5 6
3 [3,1,2,3,1,2] none 0
4 [2,3,1,2,3,1] none 0
5 [1,2,3,1,2,3] 0,1,2,3,4,5 6

Maximum match count:

6

Example 2

nums1 = [1,4,2,5,3,1]
nums2 = [2,3,1,2,4,6]
Shift Shifted nums1 Matching Indices Match Count
0 [1,4,2,5,3,1] none 0
1 [1,1,4,2,5,3] index 3 1
2 [3,1,1,4,2,5] index 2 1
3 [5,3,1,1,4,2] indices 1,2,4 3
4 [2,5,3,1,1,4] index 0 1
5 [4,2,5,3,1,1] none 0

Maximum match count:

3

Complexity Analysis

Measure Complexity Explanation
Time O(n²) We test all n shifts, each requiring n comparisons
Space O(1) Only a few integer variables are used

The algorithm performs a nested loop structure. The outer loop iterates over every possible circular shift, and the inner loop checks all positions for matches. Since both loops run n times, the total complexity is O(n²).

No auxiliary arrays or hash maps are created, so the extra space usage remains constant.

Test Cases

sol = Solution()

# Provided example 1
assert sol.maximumMatchingIndices(
    [3,1,2,3,1,2],
    [1,2,3,1,2,3]
) == 6

# Provided example 2
assert sol.maximumMatchingIndices(
    [1,4,2,5,3,1],
    [2,3,1,2,4,6]
) == 3

# Arrays already identical
assert sol.maximumMatchingIndices(
    [1,2,3],
    [1,2,3]
) == 3

# No matching values at all
assert sol.maximumMatchingIndices(
    [1,2,3],
    [4,5,6]
) == 0

# Single element equal
assert sol.maximumMatchingIndices(
    [7],
    [7]
) == 1

# Single element not equal
assert sol.maximumMatchingIndices(
    [7],
    [8]
) == 0

# Duplicate values everywhere
assert sol.maximumMatchingIndices(
    [1,1,1],
    [1,1,1]
) == 3

# Best shift is not zero
assert sol.maximumMatchingIndices(
    [1,2,3,4],
    [3,4,1,2]
) == 4

# Multiple shifts give same answer
assert sol.maximumMatchingIndices(
    [1,2,1,2],
    [2,1,2,1]
) == 4

# Partial matching only
assert sol.maximumMatchingIndices(
    [1,2,3,4],
    [2,1,4,3]
) == 2
Test Why
Example 1 Validates complete alignment after shifting
Example 2 Validates partial matching
Already identical arrays Ensures zero shifts are considered
No common values Ensures answer can be zero
Single equal element Smallest valid matching input
Single unequal element Smallest non-matching input
All duplicates Ensures duplicate handling works
Non-zero optimal shift Verifies shifting logic
Multiple optimal shifts Ensures all shifts are checked
Partial matching Tests intermediate cases

Edge Cases

One important edge case is when the arrays are already identical. A buggy implementation might assume at least one shift must occur, but the problem allows zero shifts. The algorithm handles this naturally because it checks shift 0 as part of the iteration.

Another critical edge case involves arrays with duplicate values. When duplicates exist, multiple different shifts can produce the same number of matches. Some incorrect solutions attempt to optimize using unique-value assumptions, which would fail here. This implementation compares positions directly for every shift, so duplicates are handled correctly without special logic.

A third important edge case is arrays of length one. Circular shifting a single-element array has no effect, so the answer depends entirely on whether the two elements are equal. The modular arithmetic still works correctly because:

(0 - shift + 1) % 1 = 0

Thus the implementation handles this case without requiring any special conditions.

Another subtle case is when no elements ever match. Some implementations initialize the answer incorrectly or assume at least one match exists. Since max_matches starts at 0, the algorithm correctly returns 0 when no alignment produces a match.