Minimum Consecutive Cards to Pick Up — LeetCode 2260 Python Solution

The problem

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.

Example

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.

Python solution

class Solution:
    def minimumCardPickup(self, cards: List[int]) -> int:
        last = {}
        ans = inf
        for i, x in enumerate(cards):
            if x in last:
                ans = min(ans, i - last[x] + 1)
            last[x] = i
        return -1 if ans == inf else ans

Complexity

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 2260. Minimum Consecutive Cards to Pick Up is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems