Minimum Consecutive Cards to Pick Up

Medium
803.

Minimum Consecutive Cards to Pick Up

Minimum Consecutive Cards to Pick Up is a medium coding problem on arrays, hash table and sliding window, asked in Amazon, Microsoft and Infosys interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} cards
 * @return {number}
 */
var minimumCardPickup = function(cards) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Consecutive Cards to Pick Up — Problem & Solution

Minimum Consecutive Cards to Pick Up solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimum Consecutive Cards to Pick Up is a medium coding problem on arrays, hash table and sliding window, asked in Amazon, Microsoft and Infosys interviews.

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

Hints for Minimum Consecutive Cards to Pick Up

  1. Hint 1

    The shortest run containing a pair is bounded by two occurrences of the same value.

  2. Hint 2

    For each value, only the gap to its previous occurrence can be the smallest.

  3. Hint 3

    Keep a map from value to its last index and take the minimum gap plus one.

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

Java

public static int minimumCardPickup(int[] cards) {
    Map<Integer, Integer> last = new HashMap<>();
    int best = -1;
    for (int i = 0; i < cards.length; i++) {
        Integer prev = last.get(cards[i]);
        if (prev != null) {
            int d = i - prev + 1;
            if (best < 0 || d < best) best = d;
        }
        last.put(cards[i], i);
    }
    return best;
}

C++

int minimumCardPickup(vector<int>& cards) {
    unordered_map<int, int> last;
    int best = -1;
    for (int i = 0; i < (int) cards.size(); i++) {
        auto it = last.find(cards[i]);
        if (it != last.end()) {
            int d = i - it->second + 1;
            if (best < 0 || d < best) best = d;
        }
        last[cards[i]] = 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets