2260. Minimum Consecutive Cards to Pick Up

MediumArrayHash TableSliding Window
Leetcode Link

Problem Description

In this problem, you're given an array cards with each element representing the value of a card. The task is to find the minimum number of consecutive cards you need to pick from the array to get a pair of matching cards (i.e., two cards with the same value). If it is possible to get a matching pair by picking cards consecutively, you should return the minimum number of cards you need to pick. If no matching pairs exist in the sequence of cards, the function should return -1.

Intuition

To solve this problem, we can utilize a HashMap to keep track of the last seen indices of card values. As we iterate over the array of cards, we check if the current card's value has already been seen before by consulting the HashMap. If it has been seen before, we subtract the previous index where this value was seen from the current index to find the distance between them, which also includes the currently picked card (hence we add 1). We continuously update the minimum distance whenever we find a pair of matching cards.

  1. Start by initializing a HashMap last to store the last index where each card value was seen.
  2. Initialize a variable ans to store the answer, initialized to inf (infinity), which represents that the initial distance is infinitely large.
  3. Iterate over the cards array using an index i and the card value x: a. If the card x is already in the HashMap (last), it means a previous card with the same value was seen. Therefore, calculate the distance from the current card to the last card with the same value, which can be done by i - last[x] + 1, and update the answer ans by the minimum of the current answer and this new distance. b. Update the last HashMap to mark the current index i as the latest index at which the card value x was seen.
  4. After the loop, check if ans is still inf. If it is, that means no matching cards were found, and you should return -1. Otherwise, return ans as the minimum number of consecutive cards to pick up to have a pair of matching cards.

The strength of this approach lies in its time complexity. Because the HashMap access/update is O(1) on average and the iteration of the cards is O(n) where n is the number of cards, the overall time complexity of this approach is O(n) which is efficient.

Learn more about Sliding Window patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Solution Approach

The solution uses a simple yet effective algorithm combined with a dictionary (a.k.a. HashMap in other languages) data structure to efficiently track the last occurrence index of card values.

Here's a walkthrough of the code implementation:

  • A dictionary named last is created to store the last occurrence index of each card value encountered as we iterate over the array.
  • A variable named ans is initialized with inf, which represents infinity. This variable will eventually hold the minimum number of cards required to find a matching pair or stay as infinity if no match is found.
  • The code then iterates over each card in the cards array using a for loop with the index i and card value x.
    • If the card value x is found in the last dictionary, this implies that we have encountered this value before, and therefore, we have found a pair of matching cards. The current distance to the last seen matching card is calculated by i - last[x] + 1. +1 is included because both the current card and the last card are part of the set we are considering. We then update ans with the minimum of its current value and the newly calculated distance.
    • Whether a match is found or not, the last dictionary is updated such that x now points to the current index i. This operation ensures that the next time x is encountered, the distance will be calculated from this point.
  • After the loop concludes, the ans variable is checked to determine whether it still contains inf (meaning no pairs were found). If ans is still inf, the function returns -1, as it is not possible to have matching cards. Otherwise, it returns the value of ans, which is the minimum number of consecutive cards needed to pick up to get a matching pair.

The efficiency of the algorithm comes from the use of the last dictionary, which allows constant time lookup and update for the indices of card values. This means that the algorithm will perform well, even for large arrays, as the time complexity remains linear (O(n)), where n is the number of cards.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How many times is a tree node visited in a depth first search?

Example Walkthrough

To illustrate the solution approach, let's consider a small example using the array of cards: [5, 1, 3, 4, 5, 6, 7, 3].

  • We start with an empty dictionary last and initialize ans to inf.
  • Iteration 1: Card value is 5. Since 5 is not present in the dictionary last, we add it to last with index 0: last[5] = 0.
  • Iteration 2: Card value is 1. It's also not in last, thus we add last[1] = 1.
  • Iteration 3: Card value is 3. We add it to last: last[3] = 2.
  • Iteration 4: Card value is 4. We add last[4] = 3.
  • Iteration 5: Card value is 5. This time, 5 is already in last with the index 0. We calculate the distance: i - last[5] + 1 = 5 - 0 + 1 = 6. We then update ans to 6 since 6 < inf. We also update last[5] to the current index: last[5] = 4.
  • Iteration 6: Card value is 6. We add last[6] = 5.
  • Iteration 7: Card value is 7. We add last[7] = 6.
  • Iteration 8: Card value is 3. As 3 is in last with the index 2, we find another pair. We calculate the distance: i - last[3] + 1 = 8 - 2 + 1 = 7. We compare this with the current ans, which is 6, and since 7 is larger, we don't update ans. Update last[3] = 7.

After the iterations, the smallest value in ans that was updated is 6. Therefore, the minimum number of consecutive cards you need to pick up to get a pair of matching cards is 6.

In contrast, if our cards array was something like [8, 5, 1, 3, 4] where no values repeat, at the end of our iteration, the ans would still be inf, and we would return -1 since there are no consecutive cards that form a pair.

Solution Implementation

1from math import inf
2
3class Solution:
4    def minimumCardPickup(self, cards: List[int]) -> int:
5        # Create a dictionary to keep track of the last index where each card was seen.
6        last_seen = {}
7        # Initialize the answer to infinity to represent a large number.
8        min_pickup_length = inf
9      
10        # Iterate over the list of cards with their indices.
11        for index, card_value in enumerate(cards):
12            # If the card was seen before, calculate the pickup length.
13            if card_value in last_seen:
14                # Update the minimum pickup length if a shorter one is found.
15                min_pickup_length = min(min_pickup_length, index - last_seen[card_value] + 1)
16            # Update the last seen index for the current card.
17            last_seen[card_value] = index
18      
19        # Return -1 if the answer remains infinity (no pickup found), else return the minimum pickup length.
20        return -1 if min_pickup_length == inf else min_pickup_length
21
1class Solution {
2    public int minimumCardPickup(int[] cards) {
3        // Create a map to store the last index of each card value
4        Map<Integer, Integer> lastIndexMap = new HashMap<>();
5        int numOfCards = cards.length;
6        // Initialize the smallest sequence length to maximum possible value
7        int minSequenceLength = numOfCards + 1;
8      
9        // Iterate through each card in the array
10        for (int i = 0; i < numOfCards; ++i) {
11            // If the current card has been seen before...
12            if (lastIndexMap.containsKey(cards[i])) {
13                // Update the smallest sequence length with the minimum between 
14                // the current smallest sequence length and 
15                // the length of the current sequence of cards
16                minSequenceLength = Math.min(minSequenceLength, i - lastIndexMap.get(cards[i]) + 1);
17            }
18            // Update the last index for this card value
19            lastIndexMap.put(cards[i], i);
20        }
21      
22        // If no sequence is found (minSequenceLength was not updated), return -1
23        // Otherwise, return the smallest sequence length
24        return minSequenceLength > numOfCards ? -1 : minSequenceLength;
25    }
26}
27
1#include <vector>
2#include <unordered_map>
3#include <algorithm>
4
5class Solution {
6public:
7    // Function to find the minimum number of cards to be picked up in order 
8    // to get a pair of cards with the same value.
9    int minimumCardPickup(vector<int>& cards) {
10        unordered_map<int, int> lastIndex; // Stores the last index where each card was seen
11        int n = cards.size(); // The number of cards
12        int minPickup = n + 1; // Initialize it to an impossible maximum
13
14        // Iterate over the cards
15        for (int i = 0; i < n; ++i) {
16            // If we have seen cards[i] before, calculate the distance from its last occurrence
17            if (lastIndex.count(cards[i])) {
18                minPickup = min(minPickup, i - lastIndex[cards[i]] + 1);
19            }
20            // Update the last seen index of cards[i]
21            lastIndex[cards[i]] = i;
22        }
23
24        // If minPickup did not change from its initial value, no pair was found; return -1
25        // Otherwise, return the minimum number of cards picked up to find a pair
26        return minPickup > n ? -1 : minPickup;
27    }
28};
29
1function minimumCardPickup(cards: number[]): number {
2    // Store the length of the cards array.
3    const cardCount = cards.length;
4    // Create a new map to store the last occurrence index of each card.
5    const lastIndexMap = new Map<number, number>();
6    // Initialize the answer to be larger than any possible minimum pickup length.
7    let minPickupLength = cardCount + 1;
8    // Iterate through the cards.
9    for (let index = 0; index < cardCount; ++index) {
10        // Check if we have seen the current card before.
11        if (lastIndexMap.has(cards[index])) {
12            // Update the minimum pickup length if we've found a shorter subarray.
13            minPickupLength = Math.min(minPickupLength, index - lastIndexMap.get(cards[index])! + 1);
14        }
15        // Update the map with the latest index of the current card.
16        lastIndexMap.set(cards[index], index);
17    }
18    // If the answer is still larger than any possible value, return -1 as no valid subarray was found.
19    return minPickupLength > cardCount ? -1 : minPickupLength;
20}
21
Not Sure What to Study? Take the 2-min Quiz：

Which of the following problems can be solved with backtracking (select multiple)

Time and Space Complexity

Time Complexity

The time complexity of the provided code is O(n), where n is the number of cards. This is because the code iterates through the list of cards exactly once with a single loop (for i, x in enumerate(cards):). Within this loop, checking if x is in last (if x in last:) and updating last[x] (last[x] = i) are both operations that take O(1) time on average when using a dictionary in Python.

Space Complexity

The space complexity of the provided code is O(u), where u is the number of unique cards. This is because a dictionary last is used to store the last index at which each card appears. In the worst-case scenario where all card values are unique, the dictionary would need to store an entry for each card, thus requiring O(u) space.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used in a depth first search?

Recommended Readings

Sliding Window Maximum

https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫