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.

Return theminimum 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.

Examples

Example 1

1
2
3

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.

Example 2

1
2
3

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

Constraints

  • 1 <= cards.length <= 10^5
  • 0 <= cards[i] <= 10^6

Solution

Method 1 – Hash Map for Last Seen Index

Intuition

To find the minimum consecutive cards with a matching pair, track the last index where each card value was seen. When a duplicate is found, calculate the distance and update the minimum.

Approach

  1. Use a hash map to store the last index of each card value.
  2. Iterate through the array:
    • If the card value was seen before, calculate the distance to the previous index and update the answer.
    • Update the last seen index for the card value.
  3. If no matching pair is found, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int minimumCardPickup(vector<int>& cards) {
        unordered_map<int, int> last;
        int ans = INT_MAX;
        for (int i = 0; i < cards.size(); ++i) {
            if (last.count(cards[i])) {
                ans = min(ans, i - last[cards[i]] + 1);
            }
            last[cards[i]] = i;
        }
        return ans == INT_MAX ? -1 : ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func minimumCardPickup(cards []int) int {
    last := make(map[int]int)
    ans := len(cards) + 1
    for i, v := range cards {
        if idx, ok := last[v]; ok {
            if i-idx+1 < ans {
                ans = i - idx + 1
            }
        }
        last[v] = i
    }
    if ans > len(cards) {
        return -1
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int minimumCardPickup(int[] cards) {
        Map<Integer, Integer> last = new HashMap<>();
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < cards.length; i++) {
            if (last.containsKey(cards[i])) {
                ans = Math.min(ans, i - last.get(cards[i]) + 1);
            }
            last.put(cards[i], i);
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun minimumCardPickup(cards: IntArray): Int {
        val last = mutableMapOf<Int, Int>()
        var ans = Int.MAX_VALUE
        for (i in cards.indices) {
            if (last.containsKey(cards[i])) {
                ans = minOf(ans, i - last[cards[i]]!! + 1)
            }
            last[cards[i]] = i
        }
        return if (ans == Int.MAX_VALUE) -1 else ans
    }
}
1
2
3
4
5
6
7
8

def minimum_card_pickup(cards: list[int]) -> int:
    last: dict[int, int] = {}
    ans: int = float('inf')
    for i, v in enumerate(cards):
        if v in last:
            ans = min(ans, i - last[v] + 1)
        last[v] = i
    return -1 if ans == float('inf') else ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn minimum_card_pickup(cards: Vec<i32>) -> i32 {
        use std::collections::HashMap;
        let mut last = HashMap::new();
        let mut ans = i32::MAX;
        for (i, &v) in cards.iter().enumerate() {
            if let Some(&idx) = last.get(&v) {
                ans = ans.min((i as i32) - idx + 1);
            }
            last.insert(v, i as i32);
        }
        if ans == i32::MAX { -1 } else { ans }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    minimumCardPickup(cards: number[]): number {
        const last: Record<number, number> = {};
        let ans = cards.length + 1;
        for (let i = 0; i < cards.length; i++) {
            if (last[cards[i]] !== undefined) {
                ans = Math.min(ans, i - last[cards[i]] + 1);
            }
            last[cards[i]] = i;
        }
        return ans > cards.length ? -1 : ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the array, as each card is processed once.
  • 🧺 Space complexity: O(n), for storing last seen indices in the hash map.