Least Consecutive Cards to Match - Two Pointers / Sliding Window

Problems
1

https://algo.monster/problems/least_consecutive_cards_to_match

2

Space complexity is O(n) right? Due to the window map

4

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;
5

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?)

6

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.

7

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

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
9 
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
10

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

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
13

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 :slight_smile: