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

<p>Return<em> the <strong>minimum</strong> number of <strong>consecutive</strong> cards you have to pick up to have a pair of <strong>matching</strong> cards among the picked cards.</em> If it is impossible to have matching cards, return <code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> cards = [3,4,2,3,4,7]
<strong>Output:</strong> 4
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= cards.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= cards[i] &lt;= 10<sup>6</sup></code></li>
</ul>

class Solution:
    def minimumCardPickup(self, cards: List[int]) -> int:
        # I know that there exists a monotonic property 
        # since we only care if there exists a single pair
        # grabbing more cards still has TRUE, any less will
        # be false O(nlogn)
        # BUT there may be an easier, for each value we want 
        # to know what the CLOSEST version of it is?!
        # just grab all indices of the cards in order of appearance O(n)
        # go through each values difference and keep the minimum
        # EVEN simpler approach, we only care a bout a single pair
        # and have a STRICT consecutive order, strike it!
        indexOfValue = [-1] * (10**6 + 1)
        n = len(cards)
        minDistance = n+1
        for idx, val in enumerate(cards):
            if indexOfValue[val] != -1:
                minDistance = min(idx - indexOfValue[val] + 1, minDistance)
            indexOfValue[val] = idx
        return minDistance if minDistance < n+1 else -1

        # other counting type approach, like sliding window, still O(n)
        n = len(cards)
        indicesOfValue = {}
        for idx, val in enumerate(cards):
            if val not in indicesOfValue:
                indicesOfValue[val] = [idx]
            else:
                indicesOfValue[val].append(idx)

        minDistance = n+1
        for value in indicesOfValue.keys():
            if len(indicesOfValue[value]) > 1:
                for j in range(len(indicesOfValue[value])-1):
                    minDistance = min(minDistance, indicesOfValue[value][j+1] - indicesOfValue[value][j] +1)
        return minDistance if minDistance < n+1 else -1



        # O(nlogn) binary search on parameter with monotonic function on 'valid'
        
        def targetIsPossible(size: int)->int:
            seen = set()
            for i in range(size):
                if cards[i] in seen:
                    return True
                seen.add(cards[i])

            for r in range(size, n):
                seen.remove(cards[r-size])
                if cards[r] in seen:
                    return True
                seen.add(cards[r])
            return False
        
        lo, hi = 2, n
        while lo <= hi:
            mid = (lo+hi)>>1
            if targetIsPossible(mid):
                hi=mid-1
            else:
                lo=mid+1
        return lo if lo <= n else -1
38000