LeetCode 2260. Minimum Consecutive Cards to Pick Up Solution in Java, C++, Python & More | Explanation + Code

Description

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

Solutions

Solution 1: Hash Table

We initialize the answer as +∞. We traverse the array, and for each number x, if last[x] exists, it means x has a matching pair of cards. In this case, we update the answer to ans = min(ans, i - last[x] + 1). Finally, if the answer is +∞, we return -1; otherwise, we return the answer.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array.

PythonJavaC++GoTypeScript

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(code-box)

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; } }(code-box)

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; } };(code-box)

func minimumCardPickup(cards []int) int { last := map[int]int{} n := len(cards) ans := n + 1 for i, x := range cards { if j, ok := last[x]; ok && ans > i-j+1 { ans = i - j + 1 } last[x] = i } if ans > n { return -1 } return ans }(code-box)

function minimumCardPickup(cards: number[]): number { const n = cards.length; const last = new Map<number, number>(); let ans = n + 1; for (let i = 0; i < n; ++i) { if (last.has(cards[i])) { ans = Math.min(ans, i - last.get(cards[i]) + 1); } last.set(cards[i], i); } return ans > n ? -1 : ans; }(code-box)