Minimum Consecutive Cards to Pick Up

Medium

Amazon

3 views

Topics:

ArraysSliding WindowsTwo Pointers

You are given an integer array cards where cards[i] represents the value of the i<sup>th</sup> card. A pair of cards are matching if the cards have the same value.

Return the minimum number of consecutive cards you have to pick up to have a pair of matching cards among the picked cards. If it is impossible to have matching cards, return -1.

Example 1:

Input: cards = [3,4,2,3,4,7]
Output: 4
Explanation: We can pick up the cards [3,4,2,3] which contain a matching pair of cards with value 3. Note that picking up the cards [4,2,3,4] is also optimal.

Example 2:

Input: cards = [1,0,5,3]
Output: -1
Explanation: There is no way to pick up a set of consecutive cards that contain a pair of matching cards.

Constraints:

1 <= cards.length <= 10^5
0 <= cards[i] <= 10^6

Minimum Consecutive Cards to Pick Up

Medium

Amazon

3 views

Topics:

ArraysSliding WindowsTwo Pointers

You are given an integer array cards where cards[i] represents the value of the i<sup>th</sup> card. A pair of cards are matching if the cards have the same value.

Return the minimum number of consecutive cards you have to pick up to have a pair of matching cards among the picked cards. If it is impossible to have matching cards, return -1.

Example 1:

Input: cards = [3,4,2,3,4,7]
Output: 4
Explanation: We can pick up the cards [3,4,2,3] which contain a matching pair of cards with value 3. Note that picking up the cards [4,2,3,4] is also optimal.

Example 2:

Input: cards = [1,0,5,3]
Output: -1
Explanation: There is no way to pick up a set of consecutive cards that contain a pair of matching cards.

Constraints:

1 <= cards.length <= 10^5
0 <= cards[i] <= 10^6

Solution

Naive Solution

The most straightforward approach is to iterate through all possible sub-arrays of the input array cards and check if any sub-array contains a matching pair. We keep track of the minimum length of such sub-arrays. If no matching pair is found, we return -1.

Code (Naive)

def min_consecutive_cards_naive(cards):
    min_length = float('inf')
    n = len(cards)

    for i in range(n):
        for j in range(i + 1, n):
            sub_array = cards[i:j+1]
            if len(set(sub_array)) < len(sub_array):
                min_length = min(min_length, len(sub_array))

    return min_length if min_length != float('inf') else -1

Time and Space Complexity (Naive)

Time Complexity: O(n^3) due to the nested loops and set creation.
Space Complexity: O(n) in the worst case for storing the sub-array.

Optimal Solution

We can use a dictionary (hash map) to store the last seen index of each card value. While iterating through the cards array, we check if the current card value exists in the dictionary. If it does, we have found a matching pair, and we update the minimum length if the current distance is smaller than the current minimum. If the card is not in the dictionary, we store its index in the dictionary.

Code (Optimal)

def min_consecutive_cards_optimal(cards):
    min_length = float('inf')
    last_seen = {}

    for i, card in enumerate(cards):
        if card in last_seen:
            min_length = min(min_length, i - last_seen[card] + 1)
        last_seen[card] = i

    return min_length if min_length != float('inf') else -1

Time and Space Complexity (Optimal)

Time Complexity: O(n) because we iterate through the array once.
Space Complexity: O(n) in the worst case, where n is the number of unique elements in the cards array. This is because the last_seen dictionary could potentially store all unique card values.

Edge Cases

Empty Array: If the input array is empty, the algorithm should return -1 (although the problem statement specifies the array length will be greater than or equal to 1).
No Matching Pairs: If there are no matching pairs, the algorithm should return -1.
All Elements Are the Same: The algorithm should correctly return 2 as the minimum length.
Large Input: The algorithm should handle large input arrays efficiently (the optimal solution does this).

Solution

Naive Solution

Code (Naive)

def min_consecutive_cards_naive(cards):
    min_length = float('inf')
    n = len(cards)

    for i in range(n):
        for j in range(i + 1, n):
            sub_array = cards[i:j+1]
            if len(set(sub_array)) < len(sub_array):
                min_length = min(min_length, len(sub_array))

    return min_length if min_length != float('inf') else -1

Time and Space Complexity (Naive)

Time Complexity: O(n^3) due to the nested loops and set creation.
Space Complexity: O(n) in the worst case for storing the sub-array.

Optimal Solution

Code (Optimal)

def min_consecutive_cards_optimal(cards):
    min_length = float('inf')
    last_seen = {}

    for i, card in enumerate(cards):
        if card in last_seen:
            min_length = min(min_length, i - last_seen[card] + 1)
        last_seen[card] = i

    return min_length if min_length != float('inf') else -1

Time and Space Complexity (Optimal)

Time Complexity: O(n) because we iterate through the array once.
Space Complexity: O(n) in the worst case, where n is the number of unique elements in the cards array. This is because the last_seen dictionary could potentially store all unique card values.

Edge Cases

Empty Array: If the input array is empty, the algorithm should return -1 (although the problem statement specifies the array length will be greater than or equal to 1).
No Matching Pairs: If there are no matching pairs, the algorithm should return -1.
All Elements Are the Same: The algorithm should correctly return 2 as the minimum length.
Large Input: The algorithm should handle large input arrays efficiently (the optimal solution does this).