Minimum Consecutive Cards to Pick Up

Minimum Consecutive Cards to Pick Up

What is this problem about?

The Minimum Consecutive Cards to Pick Up problem gives you an array representing a deck of cards. You want to pick up a consecutive sequence of cards from the deck such that at least one card appears twice in that sequence. You need to find the minimum length of such a sequence. If no card appears twice, return -1.

Why is this asked in interviews?

This is a standard Minimum Consecutive Cards interview question at Meta and Bloomberg. it tests Hash Tables and the "Sliding Window" concept (though it's more of a "Distance between duplicates" problem). It evaluates if you can keep track of the most recent position of each element to calculate distances efficiently.

Algorithmic pattern used

The Hash Table / Last Position Tracking interview pattern is the optimal way to solve this in $O(N)$ time.

1. Initialize a Hash Map to store the last seen index of each card.
2. Iterate through the array.
3. If the current card is already in the Map:
   • Calculate the distance: current_index - last_index + 1.
   • Update the global minimum length.
4. Update the Map with the current card's index.

Example explanation

Cards: [3, 4, 2, 3, 4, 7].

1. Card 3 at index 0. Map: {3: 0}.
2. Card 4 at index 1. Map: {3: 0, 4: 1}.
3. Card 2 at index 2. Map: {3: 0, 4: 1, 2: 2}.
4. Card 3 at index 3. Found 3 in Map! Distance = 3 - 0 + 1 = 4. Min = 4. Update Map: {3: 3, 4: 1, 2: 2}.
5. Card 4 at index 4. Found 4 in Map! Distance = 4 - 1 + 1 = 4. Min = 4. Minimum length = 4.

Common mistakes candidates make

• Nested loops: Checking every pair of cards to see if they are the same. This is $O(N^2)$ and will time out on large inputs.
• Incorrect length calculation: Using current - last instead of current - last + 1. For cards at index 0 and 3, the sequence length is 4 ([0, 1, 2, 3]).
• Not updating the last index: Forgetting to update the Map with the most recent index, which is critical if a card appears three or more times.

Interview preparation tip

This problem is a variation of "Finding the closest pair of identical elements." Use a Hash Map to remember where you've been. This Hash Table interview pattern is a core building block for many complex string and array problems.