Minimum Consecutive Cards to Pick Up - Solution & Explanation
Problem Statement
You are given an integer array cards where cards[i] represents the value of the ith card. A pair of cards are matching if the cards have the same value.
Return the minimum number of consecutive cards you have to pick up to have a pair of matching cards among the picked cards. If it is impossible to have matching cards, return -1.
Example 1:
Input: cards = [3,4,2,3,4,7] Output: 4 Explanation: We can pick up the cards [3,4,2,3] which contain a matching pair of cards with value 3. Note that picking up the cards [4,2,3,4] is also optimal.
Example 2:
Input: cards = [1,0,5,3] Output: -1 Explanation: There is no way to pick up a set of consecutive cards that contain a pair of matching cards.
Constraints:
1 <= cards.length <= 1050 <= cards[i] <= 106
Approach Overview
Problem Overview: You are given an integer array cards where each value represents a card number. The goal is to find the smallest length of a consecutive subarray that contains two cards with the same value. If no such pair exists, return -1. The key challenge is efficiently detecting duplicate values while minimizing the window length.
Approach 1: Hash Map (Dictionary) Tracking Last Index (O(n) time, O(n) space)
Store the last index where each card value appeared using a hash map. Iterate through the array once. When you encounter a card value that already exists in the map, compute the window length i - lastIndex + 1. Update the minimum answer if this window is smaller. Then update the stored index to the current position. The hash lookup gives constant-time duplicate detection, making the entire scan linear. This approach works well because the shortest valid window must occur between two closest duplicate occurrences. The data structure used is a hash table for O(1) lookups while iterating the array.
Approach 2: Sliding Window Technique (O(n) time, O(n) space)
Maintain a sliding window using two pointers and a frequency map. Expand the right pointer while tracking card counts inside the window. When a card frequency becomes greater than 1, a duplicate exists in the window. Update the answer using the current window length. Then shrink the window from the left until the duplicate condition disappears. This ensures the window always moves toward the smallest valid segment containing duplicate cards. Each element enters and leaves the window at most once, so the total runtime stays linear. This method demonstrates a classic sliding window pattern used for subarray optimization problems.
Recommended for interviews: The hash map index-tracking solution is usually what interviewers expect. It directly captures the key insight: the smallest valid segment occurs between two nearest equal cards. The sliding window approach also runs in O(n) time and shows strong understanding of window-based subarray optimization, but the hash map solution is simpler and easier to implement under time pressure.
Approach 1: Approach 1: Use a Hash Map (Dictionary)
In this approach, we'll use a hash map to keep track of the last index of each card value encountered as we iterate through the array. The hash map will store the card value as the key and its last occurrence index as the value. As we scan through the cards, if a card has been seen before, compute the distance from its last occurrence. This distance will be the number of consecutive cards needed to include these two matching cards. We'll update our minimum distance whenever we find a smaller value. This approach is efficient and runs in O(n) time complexity.
The function iterates over the cards using a for-loop. It maintains a dictionary last_seen to store the last index where each card value was observed. If the card has been seen before, it calculates the current sequence length needed to include these two, by taking the difference between the current index and the last seen index. If this length is smaller than the previously recorded minimum, it updates the min_length. Finally, if no pair is found, it returns -1.
Complexity
Time Complexity: O(n) because we only make a single pass through the cards. Space Complexity: O(u) where u is the number of unique card values.
Approach 2: Approach 2: Sliding Window Technique
In this method, we leverage a sliding window combined with a hash map (or dictionary) to track the last seen position of each card value. The sliding window allows us to efficiently find the shortest subarray with a pair by adjusting the window as needed. This approach optimally processes the input while maintaining minimal space usage and constant time checks for duplicates within the current window range.
This function uses a sliding window to keep track of the range of cards being considered. card_map records the most recent index of each card. If a card reappears within the current window (i.e., from the left to the current right index), we compute the window size and update the minimum length. The sliding window is adjusted by moving the left side to one index past the last duplicate.
Complexity
Time Complexity: O(n), Space Complexity: O(u).
Approach 3: Hash Table
We initialize the answer as +infty. We traverse the array, and for each number x, if last[x] exists, it means x has a matching pair of cards. In this case, we update the answer to ans = min(ans, i - last[x] + 1). Finally, if the answer is +infty, we return -1; otherwise, we return the answer.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Use a Hash Map (Dictionary) | Time Complexity: O(n) because we only make a single pass through the cards. Space Complexity: O(u) where u is the number of unique card values. |
| Approach 2: Sliding Window Technique | Time Complexity: O(n), Space Complexity: O(u). |
| Hash Table | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map (Track Last Index) | O(n) | O(n) | Best general solution. Quickly computes minimum distance between duplicate values. |
| Sliding Window with Frequency Map | O(n) | O(n) | Useful when practicing sliding window patterns or when solving similar subarray problems with duplicates. |
Video Solution
Minimum Consecutive Cards to Pick Up | Leetcode 2260 | Maps | Contest 291 🔥🔥 • Coding Decoded • 2,414 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Consecutive Cards to Pick Up easy or hard?
How to solve Minimum Consecutive Cards to Pick Up in O(n)?
Minimum Consecutive Cards to Pick Up Python or Java solution?
What is the best approach for Minimum Consecutive Cards to Pick Up?
What data structure is used in Minimum Consecutive Cards to Pick Up?
What is the time complexity of Minimum Consecutive Cards to Pick Up?
Is Minimum Consecutive Cards to Pick Up asked at Google or Amazon interviews?
Ready to solve this problem?
Practice Minimum Consecutive Cards to Pick Up with our built-in code editor and test cases.
Practice on FleetCode