We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Consecutive Cards to Pick Up

Number: 2338

Difficulty: Medium

Paid? No

Companies: Adobe, Google

Problem Description

Given an array where each element represents the value of a card, find the minimum number of consecutive cards you need to pick such that there is at least one pair of matching cards. If there is no way to obtain a pair from any consecutive subarray, return -1.

Key Insights

  • Use a hash table (or map) to store the last seen index of each card.
  • As you iterate over the array, check if a card has been seen before; if so, calculate the length of the subarray between the previous appearance and the current index.
  • Update the minimum length whenever a shorter valid subarray is found.
  • The problem can be solved in one pass through the array, ensuring an efficient O(n) time complexity.

Space and Time Complexity

Time Complexity: O(n) - We iterate over the array once. Space Complexity: O(n) - In the worst-case scenario, we store each element's index in the hash table.

Solution

The solution involves iterating through the array using a hash table to record the most recent index when each card value is encountered. If a duplicate card is found, calculate the subarray length (current index - last seen index + 1) and update the minimum length accordingly. After processing, if a valid subarray was found, return its length; otherwise, return -1.

Code Solutions

def min_consecutive_cards(cards):
    # Dictionary to store the last seen index of each card value.
    last_seen = {}
    # Initialize the minimum subarray length to a value greater than possible.
    min_length = len(cards) + 1
    # Iterate over each card in the list.
    for i, card in enumerate(cards):
        # If the card is seen before, calculate the window length.
        if card in last_seen:
            current_length = i - last_seen[card] + 1
            # Update the minimum length if the current window is smaller.
            min_length = min(min_length, current_length)
        # Record or update the last seen index for this card.
        last_seen[card] = i
    # Return the answer if a valid subarray was found; otherwise, return -1.
    return min_length if min_length <= len(cards) else -1

# Example usage:
cards = [3, 4, 2, 3, 4, 7]
print(min_consecutive_cards(cards))
← Back to All Questions