Problem Description

You have an array of integer cards where cards[i] represents the value of the i-th card. Two cards are considered matching if they have the same value.

Your task is to find the minimum number of consecutive cards you need to pick up such that among those picked cards, there exists at least one pair of matching cards.

For example:

• If cards = [3, 4, 2, 3, 4, 7], you could pick up cards from index 0 to 3 (cards [3, 4, 2, 3]), which contains a matching pair of 3s. This requires picking up 4 consecutive cards.
• Alternatively, you could pick up cards from index 1 to 4 (cards [4, 2, 3, 4]), which contains a matching pair of 4s. This also requires picking up 4 consecutive cards.
• The minimum would be picking up cards from index 2 to 4 (cards [2, 3, 4]), wait that doesn't have a match. Actually from index 0 to 3 gives us 4 cards with matching 3s.

The goal is to minimize the number of consecutive cards picked while ensuring at least one matching pair exists.

If no matching pair can be found in the entire array (all cards have unique values), return -1.

The key insight is that you want to find two cards with the same value that are as close together as possible in the array, as this minimizes the number of consecutive cards needed to include both matching cards.

Intuition

To find the minimum number of consecutive cards containing a matching pair, we need to think about what we're really looking for: two cards with the same value that are as close together as possible in the array.

Consider this: if we have two matching cards at positions i and j (where j > i), the minimum number of consecutive cards we need to pick up to include both is j - i + 1. This is because we must pick all cards from position i to position j inclusive.

The key realization is that we don't need to check every possible subarray. Instead, for each card value, we only care about the closest pair of that value. Why? Because if we have three cards with value x at positions a, b, and c (where a < b < c), the smallest consecutive segment would be either from a to b or from b to c, never from a to c.

This leads us to a single-pass solution: as we traverse the array, we keep track of the last position where we saw each card value. When we encounter a card value we've seen before, we calculate the distance from its last occurrence. This distance represents the number of consecutive cards needed to include this matching pair.

By maintaining a hash table last that stores the most recent index of each card value, we can efficiently:

1. Check if we've seen the current card value before
2. Calculate the distance if we have: current_index - last_index + 1
3. Update our minimum answer if this distance is smaller
4. Update the last seen position for this card value

This way, we automatically find the closest matching pairs for each value in just one pass through the array, giving us an optimal O(n) time complexity solution.

Learn more about Sliding Window patterns.

Solution Approach

We use a hash table approach to track the most recent position of each card value as we traverse the array.

Algorithm Steps:

1. Initialize variables:

   • last = {}: A hash table to store the most recent index where each card value was seen
   • ans = inf: Initialize the answer to infinity to track the minimum distance found

2. Single pass through the array: For each card at index i with value x:

   • Check if we've seen this value before: If x in last, it means we found a matching pair
     • Calculate the number of consecutive cards needed: i - last[x] + 1
     • Update the minimum answer: ans = min(ans, i - last[x] + 1)
   • Update the hash table: Set last[x] = i to record the current position as the most recent occurrence of value x

3. Return the result:

   • If ans == inf, no matching pair was found, return -1
   • Otherwise, return ans

Example walkthrough with cards = [3, 4, 2, 3, 4, 7]:

• i=0, x=3: last = {3: 0}, no match yet
• i=1, x=4: last = {3: 0, 4: 1}, no match yet
• i=2, x=2: last = {3: 0, 4: 1, 2: 2}, no match yet
• i=3, x=3: Found 3 in last! Distance = 3 - 0 + 1 = 4, ans = 4, update last = {3: 3, 4: 1, 2: 2}
• i=4, x=4: Found 4 in last! Distance = 4 - 1 + 1 = 4, ans = min(4, 4) = 4, update last = {3: 3, 4: 4, 2: 2}
• i=5, x=7: last = {3: 3, 4: 4, 2: 2, 7: 5}, no match

Final answer: 4

Time Complexity: O(n) where n is the length of the cards array - we make a single pass through the array.

Space Complexity: O(min(n, m)) where m is the number of unique card values - in the worst case where all cards are unique, we store n entries in the hash table.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach with cards = [7, 7, 3, 4, 7].

Initial Setup:

• last = {} (empty hash table)
• ans = infinity

Step-by-step traversal:

Step 1: Index 0, card value = 7

• Check if 7 is in last: No
• Add to hash table: last = {7: 0}
• No matching pair found yet

Step 2: Index 1, card value = 7

• Check if 7 is in last: Yes! (at index 0)
• Calculate consecutive cards needed: 1 - 0 + 1 = 2
• Update minimum: ans = min(infinity, 2) = 2
• Update hash table: last = {7: 1}

Step 3: Index 2, card value = 3

• Check if 3 is in last: No
• Add to hash table: last = {7: 1, 3: 2}
• Current minimum remains 2

Step 4: Index 3, card value = 4

• Check if 4 is in last: No
• Add to hash table: last = {7: 1, 3: 2, 4: 3}
• Current minimum remains 2

Step 5: Index 4, card value = 7

• Check if 7 is in last: Yes! (at index 1)
• Calculate consecutive cards needed: 4 - 1 + 1 = 4
• Update minimum: ans = min(2, 4) = 2
• Update hash table: last = {7: 4, 3: 2, 4: 3}

Result: The minimum number of consecutive cards needed is 2 (picking cards at indices 0 and 1, both with value 7).

This demonstrates how the algorithm efficiently finds the closest matching pair by tracking only the most recent position of each card value, avoiding the need to check all possible subarrays.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through the array exactly once using a single for loop that processes each element. For each element, it performs constant time operations:

• Checking if a value exists in the dictionary: O(1)
• Updating the minimum answer: O(1)
• Updating the dictionary with the current index: O(1)

Since we perform constant time operations for each of the n elements in the array, the overall time complexity is O(n).

Space Complexity: O(n)

The space complexity is determined by the last dictionary, which stores the most recent index for each unique value in the array. In the worst case, when all elements in the array are unique, the dictionary will store n key-value pairs. Therefore, the space complexity is O(n).

The additional variables (ans, i, x) use constant space O(1), which doesn't affect the overall space complexity.

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

Common Pitfalls

1. Off-by-one error in distance calculation

The Pitfall: A common mistake is calculating the distance between two matching cards as current_index - last_index instead of current_index - last_index + 1. This error occurs because we need to count the number of cards picked up inclusively from both ends.

Wrong Implementation:

# INCORRECT - misses the +1
distance = current_index - last_seen_index[card_value]  # Wrong!

Why it's wrong: If we have matching cards at indices 1 and 4, the consecutive cards we pick up are at indices [1, 2, 3, 4], which is 4 cards total. But 4 - 1 = 3 would give us only 3 cards.

Correct Implementation:

# CORRECT - includes both endpoints
distance = current_index - last_seen_index[card_value] + 1

2. Not updating the hash table after finding a match

The Pitfall: Some might think that once a matching pair is found for a value, we don't need to update its position in the hash table anymore.

Wrong Implementation:

if card_value in last_seen_index:
    distance = current_index - last_seen_index[card_value] + 1
    min_distance = min(min_distance, distance)
    # FORGOT to update last_seen_index here!
else:
    last_seen_index[card_value] = current_index

Why it's wrong: Consider cards = [3, 4, 3, 2, 3]. If we don't update after finding the first pair of 3s (at indices 0 and 2), we'll miss the closer pair of 3s at indices 2 and 4, which would give us a smaller distance of 3 instead of 3.

Correct Implementation:

if card_value in last_seen_index:
    distance = current_index - last_seen_index[card_value] + 1
    min_distance = min(min_distance, distance)

# Always update the position, regardless of whether a match was found
last_seen_index[card_value] = current_index

3. Using 0 or a large constant instead of infinity for initialization

The Pitfall: Initializing min_distance with 0 or an arbitrary large number like 10000.

Wrong Implementation:

min_distance = 0  # Wrong - will always return 0 if no match found
# or
min_distance = 10000  # Wrong - might not be large enough for all cases

Why it's wrong:

• Using 0: The minimum distance will never update since all valid distances are positive
• Using arbitrary large numbers: May fail for arrays larger than your constant

Correct Implementation:

from math import inf
min_distance = inf  # Guarantees any valid distance will be smaller