Minimum Consecutive Card Pickup

Q: What is the time complexity of Minimum Consecutive Card Pickup?

O(n). The algorithm iterates through the cards array once, performing O(1) average-time hash map lookups and updates per element.

Q: What pattern does Minimum Consecutive Card Pickup use?

The Pattern: Hash Maps (Index Tracking for Duplicate Detection) The Heuristic: When searching for the shortest subarray containing duplicates, track the last occurrence of each element in a hash map to instantly compute distances and update the minimum length in a single pass.

Medium Hash Maps

Problem

Given an array of integers cards, return the minimum length of a contiguous subarray containing at least two equal cards. If no such subarray exists, return -1.

1 ≤ cards.length ≤ 10⁵
1 ≤ cards[i] ≤ 10⁶

Example

Input: cards = [3,4,2,3,4,7]

Output: 4

The subarray [3,4,2,3] contains two '3's and has length 4. Another subarray [4,2,3,4] contains two '4's and also has length 4. No shorter subarray contains duplicates, so the answer is 4.

Approach

Straightforward Solution

A brute-force approach would check every subarray for duplicates, resulting in O(n^2) time complexity, which is infeasible for large inputs.

Core Observation

The problem requires finding the shortest subarray containing duplicate elements. This translates to finding the minimum distance between two identical elements in the array.

Path to Optimal

Preview

The key recognition signals are 'minimum length subarray with duplicates' and 'check for repeated elements'. These indicate a Hash Map pattern because we need to track the last seen index of each card to quickly compute distances between duplicates…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Iterate through the cards array once, maintaining a hash map from card value to its last seen index. For each card, if it has been seen before, calculate the subarray length between the current and previous indices and update the minimum answer…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm iterates through the cards array once, performing O(1) average-time hash map lookups and updates per element.

Space

O(n)

In the worst case, all elements are unique and stored in the hash map, requiring O(n) auxiliary space.

Pattern Spotlight

Hash Maps (Index Tracking for Duplicate Detection)

When searching for the shortest subarray containing duplicates, track the last occurrence of each element in a hash map to instantly compute distances and update the minimum length in a single pass.

Solution

Python

1from collections import defaultdict
2
3class Solution:
4    def minimumCardPickup(self, cards: List[int]) -> int:
5        dic = defaultdict(int)
6        ans = float("inf")
7        for i in range(len(cards)):
8            if cards[i] in dic:
9                ans = min(ans, i - dic[cards[i]] + 1)
10            
11            dic[cards[i]] = i
12
13        return ans if ans < float("inf") else -1

Step-by-Step Solution

Track Last Seen Indices and Update Minimum Subarray Length

5dic = defaultdict(int)
6ans = float("inf")
7for i in range(len(cards)):
8    if cards[i] in dic:
9        ans = min(ans, i - dic[cards[i]] + 1)
11    dic[cards[i]] = i
13return ans if ans < float("inf") else -1

Objective

To iterate through the cards array, track the last occurrence of each card, and update the minimum length of subarrays containing duplicates.

Key Insight

By storing the last seen index of each card in a hash map, the algorithm can instantly compute the length of the subarray between the current and previous occurrence of the same card. This approach transforms the problem from a costly nested search into a linear scan with constant-time lookups, enabling efficient detection of the shortest duplicate-containing subarray.

Interview Quick-Check

Core Logic

Maintain a hash map from card value to last seen index; for each card, if seen before, compute subarray length and update minimum answer.

State & Boundaries

Initialize answer to infinity and update only when duplicates are found; return -1 if no duplicates exist.

Common Pitfalls & Bugs

Forgetting to update the last seen index after checking for duplicates can cause incorrect subarray length calculations.

Complexity

This single-pass approach achieves O(n) time and O(n) space complexity, optimal for the problem constraints.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 9 Critical

ans = min(ans, i - dic[cards[i]] + 1)

Update the answer with the minimum length between the current and last seen indices of the duplicate card.

Calculating the distance between the current and previous indices directly gives the length of the subarray containing duplicates, enabling efficient minimum tracking.

Line 11 Critical

dic[cards[i]] = i

Update the last seen index of the current card to the current index.

Updating the last seen index ensures future duplicate detections use the most recent occurrence, maintaining correctness of subarray length calculations.

Full line-by-line criticality + rationale for all 7 lines available on Pro.

Test Your Understanding

Why does tracking the last seen index of each card enable finding the minimum subarray length with duplicates in O(n) time?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Minimum Consecutive Card Pickup from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Minimum Consecutive Card Pickup drill

or drill a free problem

1	`from collections import defaultdict`
2
3	`class Solution:`
4	`def minimumCardPickup(self, cards: List[int]) -> int:`
5	`dic = defaultdict(int)`
6	`ans = float("inf")`
7	`for i in range(len(cards)):`
8	`if cards[i] in dic:`
9	`ans = min(ans, i - dic[cards[i]] + 1)`
10
11	`dic[cards[i]] = i`
12
13	`return ans if ans < float("inf") else -1`

5	`dic = defaultdict(int)`
6	`ans = float("inf")`
7	`for i in range(len(cards)):`
8	`if cards[i] in dic:`
9	`ans = min(ans, i - dic[cards[i]] + 1)`
11	`dic[cards[i]] = i`
13	`return ans if ans < float("inf") else -1`