Minimum Consecutive Cards to Pick Up — Problem & Solution
Minimum Consecutive Cards to Pick Up solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Consecutive Cards to Pick Up is a medium coding problem on arrays, hash table and sliding window, asked in Amazon, Microsoft and Infosys interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Sliding Window
- Asked at: Amazon, Microsoft, Infosys
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
cards[i] is the value on the i-th card. You must pick up some consecutive cards and want a matching pair among them.
Return the minimum number of consecutive cards you have to pick up to get a pair of equal values, or -1 if no pair exists.
Example 1
Input: cards = [3,4,2,3,4,7]
Output: 4
Explanation: Cards 0 through 3 hold two 3s.
Example 2
Input: cards = [1,0,5,3]
Output: -1
Explanation: Every value is distinct.
Example 3
Input: cards = [9,9]
Output: 2
Constraints
1 <= cards.length <= 1000000 <= cards[i] <= 1000000
Hints for Minimum Consecutive Cards to Pick Up
Hint 1
The shortest run containing a pair is bounded by two occurrences of the same value.
Hint 2
For each value, only the gap to its previous occurrence can be the smallest.
Hint 3
Keep a map from value to its last index and take the minimum gap plus one.
How to solve Minimum Consecutive Cards to Pick Up
The answer is the smallest distance between two equal values, plus one for inclusivity. Only consecutive occurrences of a value matter, so one pass with a last-seen map suffices.
Approach
- Keep
last[v], the most recent index of each value. - At index
i, ifcards[i]was seen before, the candidate isi - last[cards[i]] + 1. - Update
last[cards[i]]and keep the minimum candidate; return-1if none was ever found.
Why it works
Any run containing a pair contains two occurrences of some value, and shrinking it to just those two occurrences is no longer — so the answer is realised by some adjacent pair of equal values. Non-adjacent occurrences are strictly further apart, so only the previous one needs checking.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Comparing against the first occurrence of a value rather than the previous one gives a longer run.
- The answer is a count of cards, so the gap needs the
+ 1. - All-distinct input must return
-1, not a large sentinel.
Reference solution
Python
from typing import List
def minimumCardPickup(cards: List[int]) -> int:
last = {}
best = -1
for i, v in enumerate(cards):
if v in last:
d = i - last[v] + 1
if best < 0 or d < best:
best = d
last[v] = i
return bestJava
public static int minimumCardPickup(int[] cards) {
Map<Integer, Integer> last = new HashMap<>();
int best = -1;
for (int i = 0; i < cards.length; i++) {
Integer prev = last.get(cards[i]);
if (prev != null) {
int d = i - prev + 1;
if (best < 0 || d < best) best = d;
}
last.put(cards[i], i);
}
return best;
}C++
int minimumCardPickup(vector<int>& cards) {
unordered_map<int, int> last;
int best = -1;
for (int i = 0; i < (int) cards.size(); i++) {
auto it = last.find(cards[i]);
if (it != last.end()) {
int d = i - it->second + 1;
if (best < 0 || d < best) best = d;
}
last[cards[i]] = i;
}
return best;
}JavaScript
var minimumCardPickup = function(cards) {
var last = {};
var best = -1;
for (var i = 0; i < cards.length; i++) {
var v = cards[i];
if (last[v] !== undefined) {
var d = i - last[v] + 1;
if (best < 0 || d < best) best = d;
}
last[v] = i;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets