3400. Maximum Number of Matching Indices After Right Shifts 🔒

MediumArrayTwo PointersSimulation

Leetcode Link

Problem Description

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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To solve this problem, we start by understanding what a right shift entails. A right shift effectively moves each element in nums1 one position to the right, with the last element wrapping around to the first position. Our task is to determine how many indices match between nums1 and nums2 after performing such shifts any number of times.

The intuition behind finding the solution lies in the idea that for each possible shift position k (ranging from 0 to n-1), we need to calculate the number of indices that match between nums1 and nums2. For a given shift k, the element at nums1[i] will be compared against nums2[(i - k + n) % n]. We can then count these matching indices for each shift position, updating our maximum count as we evaluate each one.

Our approach involves iterating over each shift position, applying the shifting logic to determine matches, and keeping track of the highest number of matches found. This approach guarantees that we explore all possible configurations resulting from the right shifts.

Learn more about Two Pointers patterns.

Solution Approach

The solution uses an enumeration approach by iterating over all possible right shift amounts k. The key steps involved in the solution are:

Determine the length n of the input arrays nums1 and nums2.
Initialize a variable ans to store the maximum number of matching indices found.
For every possible shift k (from 0 to n-1):
- Calculate the number of indices where the elements in nums1 matched with nums2 after shifting nums1 to the right by k positions.
- This matching check can be carried out with a single line using the formula: nums1[(i + k) % n] == nums2[i] for each index i.
- The generator expression sum(nums1[(i + k) % n] == x for i, x in enumerate(nums2)) sums up the matches.
- Update ans with the maximum of its current value and the number of matches found for this particular shift k.
Finally, return ans which holds the maximum number of matching indices across all possible right shifts.

This approach ensures we explore each potential alignment by systematically shifting nums1 through all possible positions, optimizing the solution through enumeration.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach.

Suppose we have the following input arrays:

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

We need to find the maximum number of matching indices after performing any number of right shifts on nums1.

Step-by-Step Execution:

Initial State (No Shift):
- nums1 = [3, 1, 2]
- Compare with nums2 = [1, 2, 3].
- No indices match: 0 matches.
First Right Shift:
- Shift nums1 to become [2, 3, 1].
- Compare with nums2 = [1, 2, 3].
- Again, no indices match: 0 matches.
Second Right Shift:
- Shift nums1 to become [1, 2, 3].
- Compare with nums2 = [1, 2, 3].
- All indices match: 3 matches.

After evaluating all possible shifts, the maximum number of matching indices is found to be 3, which occurs after the second right shift.

Thus, the solution would return 3 as the maximum number of matching indices.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maximumMatchingIndices(self, nums1: List[int], nums2: List[int]) -> int:
5        """
6        This function returns the maximum number of indices such that 
7        nums1 and nums2 are identical after any number of rotations on nums1.
8        """
9        n = len(nums1)  # Length of the list
10        max_matches = 0  # To keep track of the maximum number of matching indices
11
12        # Traverse through all possible rotations
13        for k in range(n):
14            # Check how many indices match for this specific rotation
15            matching_count = sum(nums1[(i + k) % n] == nums2[i] for i in range(n))
16          
17            # Update the maximum matches found
18            max_matches = max(max_matches, matching_count)
19      
20        return max_matches
21

1class Solution {
2    public int maximumMatchingIndices(int[] nums1, int[] nums2) {
3        int n = nums1.length; // Length of the arrays
4        int ans = 0; // Variable to store the maximum matching count
5      
6        // Loop through each possible rotation of nums1
7        for (int k = 0; k < n; ++k) {
8            int matchingCount = 0; // Count matches for current rotation
9          
10            // Check matching indices for this rotation
11            for (int i = 0; i < n; ++i) {
12                // Calculate rotated index for nums1 using modulo to wrap around
13                if (nums1[(i + k) % n] == nums2[i]) {
14                    ++matchingCount; // Increase count if elements match
15                }
16            }
17          
18            // Update maximum matching indices found so far
19            ans = Math.max(ans, matchingCount);
20        }
21      
22        return ans; // Return the maximum matching indices count
23    }
24}
25

1#include <vector>
2#include <algorithm> // For std::max
3
4class Solution {
5public:
6    int maximumMatchingIndices(std::vector<int>& nums1, std::vector<int>& nums2) {
7        // Get the size of the vectors
8        int n = nums1.size();
9        // Initialize the variable to store the maximum count of matching indices
10        int ans = 0;
11
12        // Iterate over each possible rotation of nums1
13        for (int k = 0; k < n; ++k) {
14            // Initialize a counter for matching indices in this rotation
15            int matchCount = 0;
16
17            // Check each index i for a match between the rotated nums1 and nums2
18            for (int i = 0; i < n; ++i) {
19                // Calculate rotated index and compare values
20                if (nums1[(i + k) % n] == nums2[i]) {
21                    // If they match, increment the match counter
22                    ++matchCount;
23                }
24            }
25
26            // Update the maximum match count with the current rotation's matches
27            ans = std::max(ans, matchCount);
28        }
29
30        // Return the maximum number of matching indices found for any rotation
31        return ans;
32    }
33};
34

1function maximumMatchingIndices(nums1: number[], nums2: number[]): number {
2    const n: number = nums1.length;  // Get the length of the arrays
3    let maxMatches: number = 0; // Initialize to keep track of maximum matching indices
4
5    // Iterate over possible shifts
6    for (let shift = 0; shift < n; ++shift) {
7        let currentMatches: number = 0; // Count of matches for current shift
8
9        // Compare elements with shifted version of nums1
10        for (let i = 0; i < n; ++i) {
11            // Check if the rotated element in nums1 matches the element in nums2 at the same index
12            if (nums1[(i + shift) % n] === nums2[i]) {
13                ++currentMatches; // Increment if there is a match
14            }
15        }
16
17        // Update maximum matches found so far
18        maxMatches = Math.max(maxMatches, currentMatches);
19    }
20
21    return maxMatches; // Return the maximum number of matching indices
22}
23

Time and Space Complexity

The time complexity of the code is O(n^2), where n is the length of the array nums1. This complexity arises because the outer loop runs n times, and for each iteration, the inner sum operation also runs n times, making it a nested loop contributing to the quadratic complexity.

The space complexity of the code is O(1). This is because the algorithm uses a constant amount of extra space regardless of the input size, with variables n, ans, k, t, and the iteration index i and value x in the list comprehension.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Add another stack to store the minimums

Add a heap to store the minimums

Add a variable to track the minimum

Add a queue to store the minumums

I don't know