Minimum Consecutive Cards to Pick Up
Description
You are given an integer array cards where cards[i] represents the value of the ith 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 3s. The distance between the two 3s is 4 cards (indices 0 to 3 inclusive). There's also a pair of 4s at indices 1 and 4, but that requires picking 4 cards as well.
Example 2:
Input: cards = [1, 0, 5, 3]
Output: -1
Explanation: There are no matching pairs in the array, so it's impossible to pick up matching cards.
Example 3:
Input: cards = [0, 0]
Output: 2
Explanation: The two 0s are adjacent, so we need to pick up exactly 2 consecutive cards to get a matching pair.
Constraints
1 <= cards.length <= 10^50 <= cards[i] <= 10^6
Complexity
Show Complexity
- Time:
O(n) - Space:
O(n)
Hints
Show Hints
- Pattern
- Hash map to track last seen index of each card value
- Approach
- Use a hash map to store the most recent index of each card value. For each card, if seen before, calculate the distance and update minimum.
- Complexity
- Single pass through array tracking indices
Solutions
Show PY Solution
def solution(cards: list[int]) -> int:
m = {}
count = float("inf")
for i in range(len(cards)):
if cards[i] in m:
count = min(count, i - m[cards[i]] + 1)
m[cards[i]] = i
return int(count) if count < float("inf") else -1