# Least Consecutive Cards to Match - Two Pointers / Sliding Window

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;
}
``````
``````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;
}
``````