Watch 10 video solutions for Minimum Consecutive Cards to Pick Up, a medium level problem involving Array, Hash Table, Sliding Window. This walkthrough by Coding Decoded has 2,405 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 106Problem 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 | 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. |