https://algo.monster/problems/least_consecutive_cards_to_match
Space complexity is O(n) right? Due to the window map
I was wondering why we need a sliding window approach here. The way I implemented is just with a map to check if we have seen the current value previously. If so, we try to update the smallest value. And just override the index for the current value. That’s because we are always going from left to right, which means that the last index for a given value will always be the best possible if we find another match in the future. I passed all the tests but I am not sure if they are missing some test case for which my solution would be invalid. Or maybe I misunderstood the problem and got it right by chance?
std::unordered_map<int, int> seenCards;
int smallest = std::numeric_limits<int>::max();
for(int idx = 0; idx < cards.size(); ++idx)
{
if (seenCards.count(cards[idx]) > 0)
{
smallest = std::min(smallest, idx - seenCards[idx] + 1);
}
seenCards[cards[idx]] = idx;
}
if (smallest == std::numeric_limits<int>::max())
return -1;
return smallest;
I believe I came up with the same solution in Python:
def least_consecutive_cards_to_match(cards: List[int]) -> int:
# Initialize dictionary to hold card and most recent index {card: index}
positions = {}
# Initialize variable for solution
sol = -1
# Loop through cards
for i, card in enumerate(cards):
# If this card has been seen before, record number of cards in the range (inclusive)
if card in positions:
sol = i - positions[card] + 1
# Record the card's position
positions[card] = i
return sol
I was trying hard to come up with a solution with O(1) storage since this in the Two Pointers section. I think our solution is simpler than the one currently in the article. (Maybe because the mods suggest using the template?)
The link to flexible sliding window template returns a 404 error when clicked.
It seems like the link should point to subarray_sum_shortest instead of target_subarray_sum_shortest.
Yeah, I also came up with similar solution. The proposed sliding window solution seems unnecessarily complicated.
Here is my JS solution
export function leastConsecutiveCardsToMatch(cards: number[]) {
if (cards.length === 0) return -1;
const map = new Map<number, number>();
let min = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < cards.length; i++) {
if (map.has(cards[i])) {
min = Math.min(min, i - map.get(cards[i]) + 1);
}
map.set(cards[i], i);
}
return min === Number.MAX_SAFE_INTEGER ? -1 : min;
}
Hello guys, I agree that the sliding window solution is an overkill here because the valid condition is just matching a card. That means we need just two indexes (instead of a range of indexes) to check for the validity. For the problems where we need a range of indexes to check for the validity, sliding window is an apt technique.
// My Generic HashMap Solution
public static int leastConsecutiveCardsToMatch(List<Integer> cards) {
int shortestLength = cards.size() + 1;
int currentLength = cards.size() + 1;
int index, previousIndex;
HashMap<Integer, Integer> map = new HashMap<>();
for (index=0; index < cards.size(); index++) {
if (map.containsKey(cards.get(index))) {
previousIndex = map.get(cards.get(index));
currentLength = index - previousIndex + 1;
shortestLength = Math.min(shortestLength, currentLength);
}
map.put(cards.get(index), index);
}
return shortestLength == cards.size() + 1 ? -1 : shortestLength;
}
1 Like
def least_consecutive_cards_to_match(cards: List[int]) -> int:
seen = {}
ans = math.inf
for i, val in enumerate(cards):
if val in seen:
ans = min(ans, i - seen[val] + 1)
seen[val] = i
return -1 if ans == math.inf else ans
Same I found the same solution without sliding window.
public static int leastConsecutiveCardsToMatch(List<Integer> cards) {
int minCards = Integer.MAX_VALUE;
HashMap<Integer, Integer> countMap = new HashMap<>();
for (int end = 0; end < cards.size(); end++) {
int currentValue = cards.get(end);
if(countMap.get(currentValue) != null) {
//pair found
minCards = Math.min(minCards, end - countMap.get(currentValue) + 1);
}
countMap.put(currentValue, end);
}
return minCards == Integer.MAX_VALUE ? -1 : minCards;
}
Sliding window solution using Set instead of Dictionary.
def least_consecutive_cards_to_match(cards: List[int]) -> int:
left, window, min_length = 0, set(), len(cards)+1
for right in range(len(cards)):
while cards[right] in window:
min_length = min(min_length, right-left+1)
window.remove(cards[left])
left += 1
window.add(cards[right])
return min_length if min_length <= len(cards) else -1
Corresponding Leetcode Question: 2260. Minimum Consecutive Cards to Pick Up
We can further optimize on space if needed using the two pointer approach. Instead of keeping track of all pairs of cards in a dictionary, we can just keep track of min length of matching pairs.
Time: O(n), Space O(1)
def least_consecutive_cards_to_match(cards: List[int]) -> int:
# use a two pointer approach
L = 0
R = 1
min_len = float('inf')
while R < len(cards):
while L < R and cards[L] == cards[R]:
# capture length
min_len = min(min_len,R - L + 1)
L += 1
R += 1
return -1 if min_len == float('inf') else min_len
Hope this helps 
I feel like just using a hashmap here makes more sense, instead of sliding window
class Solution:
def minimumCardPickup(self, cards: List[int]) -> int:
minCards = float("inf")
cMap = {}
for i,c in enumerate(cards):
if c in cMap:
minCards = min(i - cMap[c] + 1, minCards)
cMap[c] = i
if minCards == float("inf"):
return -1
return minCards