Get started

Minimum Consecutive Cards to Pick Up — Medium Problem & Solution

cards[i] is the value on the i-th card. You must pick up some consecutive cards and want a matching pair among them.

Problem statement

cards[i] is the value on the i-th card. You must pick up some consecutive cards and want a matching pair among them.

Return the minimum number of consecutive cards you have to pick up to get a pair of equal values, or -1 if no pair exists.

Example 1

Input: cards = [3,4,2,3,4,7]
Output: 4
Explanation: Cards 0 through 3 hold two 3s.

Example 2

Input: cards = [1,0,5,3]
Output: -1
Explanation: Every value is distinct.

Example 3

Input: cards = [9,9]
Output: 2

Constraints

  • 1 <= cards.length <= 100000
  • 0 <= cards[i] <= 1000000

How to solve Minimum Consecutive Cards to Pick Up

The answer is the smallest distance between two equal values, plus one for inclusivity. Only consecutive occurrences of a value matter, so one pass with a last-seen map suffices.

Approach

  1. Keep last[v], the most recent index of each value.
  2. At index i, if cards[i] was seen before, the candidate is i - last[cards[i]] + 1.
  3. Update last[cards[i]] and keep the minimum candidate; return -1 if none was ever found.

Why it works

Any run containing a pair contains two occurrences of some value, and shrinking it to just those two occurrences is no longer — so the answer is realised by some adjacent pair of equal values. Non-adjacent occurrences are strictly further apart, so only the previous one needs checking.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Comparing against the first occurrence of a value rather than the previous one gives a longer run.
  • The answer is a count of cards, so the gap needs the + 1.
  • All-distinct input must return -1, not a large sentinel.

Reference solution

Python

from typing import List

def minimumCardPickup(cards: List[int]) -> int:
    last = {}
    best = -1
    for i, v in enumerate(cards):
        if v in last:
            d = i - last[v] + 1
            if best < 0 or d < best:
                best = d
        last[v] = i
    return best

JavaScript

var minimumCardPickup = function(cards) {
    var last = {};
    var best = -1;
    for (var i = 0; i < cards.length; i++) {
        var v = cards[i];
        if (last[v] !== undefined) {
            var d = i - last[v] + 1;
            if (best < 0 || d < best) best = d;
        }
        last[v] = i;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue