# Minimum Consecutive Cards to Pick Up
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-consecutive-cards-to-pick-up)
Canonical: https://scaleengineer.com/dsa/problems/minimum-consecutive-cards-to-pick-up
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Array, Hash Table
---
## 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 _the **minimum** 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`.

**Example 1:**

**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:**

**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 <= 105`
* `0 <= cards[i] <= 106`

# Approaches
## Brute Force with Nested Loops
This approach involves checking every possible pair of cards in the array to see if they match. For each pair of matching cards found, we calculate the number of consecutive cards required to pick them up and keep track of the minimum number found.
**Time:** O(n^2), where n is the number of cards. The two nested loops lead to a quadratic time complexity as we compare every card with every other card that comes after it. · **Space:** O(1), as we only use a few variables to store the minimum length and loop indices, not dependent on the input size.
**Pros:** Simple to understand and implement.; Requires no extra space besides a few variables.
**Cons:** Highly inefficient for large inputs due to the O(n^2) time complexity.; Will likely result in a 'Time Limit Exceeded' error for the given constraints (n <= 10^5).
### Explanation
The brute-force solution directly translates the problem statement into code. We iterate through all possible pairs of indices `(i, j)` where `i < j`. For each pair, we check if `cards[i]` is equal to `cards[j]`. If they are equal, we have found a matching pair. The subarray that contains these two cards is `cards[i...j]`, and its length is `j - i + 1`. We maintain a variable, `minLength`, initialized to a very large value. Whenever we find a matching pair, we update `minLength` with the minimum of its current value and the newly calculated length. After checking all pairs, if `minLength` remains at its initial large value, it means no matching pairs were found, and we return -1. Otherwise, we return the final `minLength`.

Here is the Java implementation:
```java
class Solution {
    public int minimumCardPickup(int[] cards) {
        int n = cards.length;
        int minLength = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (cards[i] == cards[j]) {
                    minLength = Math.min(minLength, j - i + 1);
                }
            }
        }
        return minLength == Integer.MAX_VALUE ? -1 : minLength;
    }
}
```
### Algorithm
- Initialize a variable `minLength` to a very large number (e.g., `Integer.MAX_VALUE`).
- Get the total number of cards, `n`.
- Use a `for` loop with an index `i` to iterate from `0` to `n-1`.
- Inside this loop, use a nested `for` loop with an index `j` to iterate from `i+1` to `n-1`.
- In the inner loop, check if the cards at the current indices match: `cards[i] == cards[j]`.
- If they match, calculate the length of the consecutive segment: `length = j - i + 1`.
- Update `minLength` to be the minimum of its current value and the new `length`.
- After the loops finish, check if `minLength` is still at its initial large value.
- If it is, no matching pair was found, so return `-1`.
- Otherwise, return `minLength`.

## Sorting Approach
This approach improves upon the brute-force method by first sorting the cards based on their values while keeping track of their original positions. This allows us to find matching cards by just checking adjacent elements in the sorted list.
**Time:** O(n log n), which is dominated by the sorting step. Creating the pairs and iterating through the sorted list both take O(n) time. · **Space:** O(n) to store the `indexedCards` array which holds the value and original index for each card.
**Pros:** Significantly more efficient than the brute-force approach.; Passes for larger test cases where brute-force would time out.
**Cons:** Not the most optimal solution in terms of time complexity.; Requires extra space proportional to the input size.
### Explanation
The core idea is that after sorting by card value, all cards with the same value will be grouped together. Since we need the original indices to calculate the distance, we first create a new data structure, like a 2D array, to store both the card's value and its original index `(value, index)`. We then sort this new structure based on the card values. After sorting, we can find the minimum distance between identical cards by iterating through the sorted list once and comparing each element with its predecessor. If two adjacent elements have the same value, we calculate the difference between their original indices, add one, and update our minimum length. This is because for any card value that appears multiple times, the minimum distance will be between two occurrences that become adjacent after sorting by index.

Here is the Java implementation:
```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int minimumCardPickup(int[] cards) {
        int n = cards.length;
        int[][] indexedCards = new int[n][2];
        for (int i = 0; i < n; i++) {
            indexedCards[i][0] = cards[i];
            indexedCards[i][1] = i;
        }

        // Sort by card value, then by index
        Arrays.sort(indexedCards, Comparator.comparingInt(a -> a[0]).thenComparingInt(a -> a[1]));

        int minLength = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            if (indexedCards[i][0] == indexedCards[i-1][0]) {
                int length = indexedCards[i][1] - indexedCards[i-1][1] + 1;
                minLength = Math.min(minLength, length);
            }
        }

        return minLength == Integer.MAX_VALUE ? -1 : minLength;
    }
}
```
### Algorithm
- Create a 2D array or a list of objects, let's call it `indexedCards`, to store pairs of `(card_value, original_index)`.
- Iterate through the input `cards` array from `i = 0` to `n-1` and populate `indexedCards` with `(cards[i], i)`.
- Sort the `indexedCards` structure. The primary sorting key should be the card value.
- Initialize `minLength` to `Integer.MAX_VALUE`.
- Iterate through the sorted `indexedCards` from the second element (`i = 1` to `n-1`).
- For each element, compare its value with the previous element's value: `indexedCards[i].value == indexedCards[i-1].value`.
- If the values are the same, calculate the distance between their original indices: `length = indexedCards[i].index - indexedCards[i-1].index + 1`.
- Update `minLength = Math.min(minLength, length)`.
- After the loop, if `minLength` has not changed from its initial value, return `-1`. Otherwise, return `minLength`.

## Optimal Single Pass with a HashMap
This is the most efficient approach. It involves a single pass through the array while using a HashMap to keep track of the last seen index of each card value. This allows us to calculate the distance between matching cards in constant time.
**Time:** O(n), where n is the number of cards. We iterate through the array only once, and HashMap operations (put and get) take, on average, O(1) time. · **Space:** O(k), where k is the number of unique cards. In the worst case, if all cards are unique, the space complexity is O(n).
**Pros:** Optimal time complexity of O(n).; Solves the problem in a single pass, making it very fast.; The logic is straightforward and easy to reason about.
**Cons:** Requires extra space for the HashMap, which could be up to O(n) in the worst case if all cards are unique.
### Explanation
The problem asks for the minimum number of consecutive cards, which corresponds to the minimum distance between two identical cards. We can find this efficiently by iterating through the array once. We use a HashMap to store the most recent index at which we've seen each card value. As we iterate through the `cards` array at index `i`, we check if the current card's value already exists as a key in our HashMap. If it does, we have found a matching pair. The distance is `i - prevIndex + 1`, where `prevIndex` is the index stored in the map. We update our overall `minLength` with this new length if it's smaller. Then, we update the map with the current card's index. This ensures that for any future matches, we are comparing against the most recent previous occurrence, which is key to finding the minimum distance.

Here is the Java implementation:
```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int minimumCardPickup(int[] cards) {
        Map<Integer, Integer> lastIndexMap = new HashMap<>();
        int minLength = Integer.MAX_VALUE;
        for (int i = 0; i < cards.length; i++) {
            int currentCard = cards[i];
            if (lastIndexMap.containsKey(currentCard)) {
                int prevIndex = lastIndexMap.get(currentCard);
                minLength = Math.min(minLength, i - prevIndex + 1);
            }
            lastIndexMap.put(currentCard, i);
        }
        return minLength == Integer.MAX_VALUE ? -1 : minLength;
    }
}
```
### Algorithm
- Initialize `minLength` to `Integer.MAX_VALUE`.
- Create a `HashMap` named `lastIndexMap` to store the last seen index of each card value, mapping `card_value` to `index`.
- Iterate through the `cards` array using an index `i` from `0` to `n-1`.
- For each `card = cards[i]`, check if `lastIndexMap` contains the key `card`.
- If it does, retrieve its last seen index: `prevIndex = lastIndexMap.get(card)`.
- Calculate the number of consecutive cards: `length = i - prevIndex + 1`.
- Update `minLength` with the minimum of its current value and this new `length`.
- After the check, update the map with the current card's index: `lastIndexMap.put(card, i)`.
- After the loop completes, if `minLength` is still `Integer.MAX_VALUE`, return `-1`.
- Otherwise, return the final `minLength`.

# Solutions
### Java

```java
class Solution {
public
  int minimumCardPickup(int[] cards) {
    Map<Integer, Integer> last = new HashMap<>();
    int n = cards.length;
    int ans = n + 1;
    for (int i = 0; i < n; ++i) {
      if (last.containsKey(cards[i])) {
        ans = Math.min(ans, i - last.get(cards[i]) + 1);
      }
      last.put(cards[i], i);
    }
    return ans > n ? -1 : ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumCardPickup(vector<int> &cards) {
    unordered_map<int, int> last;
    int n = cards.size();
    int ans = n + 1;
    for (int i = 0; i < n; ++i) {
      if (last.count(cards[i])) {
        ans = min(ans, i - last[cards[i]] + 1);
      }
      last[cards[i]] = i;
    }
    return ans > n ? -1 : ans;
  }
};

```

### Python

```python
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

```