Minimum Consecutive Cards to Pick Up

🎯

Minimum Consecutive Cards to Pick Up

mediumSLIDING_WINDOWAmazonGoogle

Imagine you have a deck of cards laid out in a row, and you want to quickly find the smallest group of consecutive cards that contains two identical cards.

💡 This problem is about finding the shortest subarray containing duplicates. Beginners often struggle because they try brute force without realizing that tracking last seen positions and using a sliding window can optimize the search.

📋

Problem Statement

Given an integer array cards where cards[i] represents the value of the ith card, return the minimum number of consecutive cards you need to pick up to have at least two cards with the same value. If no such group exists, return -1.

1 ≤ cards.length ≤ 10^51 ≤ cards[i] ≤ 10^6

💡

Example

Input"[3,4,2,3,4,7]"

Output4

The smallest subarray with duplicate cards is [3,4,2,3], length 4.

Input"[1,0,5,3]"

Output-1

No duplicates exist, so return -1.

• All cards are unique → output -1
• All cards are the same → output 2 (minimum length)
• Duplicates appear at the very start and end → output minimum gap
• Array length is 1 → output -1 (no duplicates possible)

⚠️

Common Mistakes

Not updating the last seen index after finding a duplicate

Incorrect minimum length or infinite loop in sliding window

✅ Always update last seen index after processing each card

Moving left pointer incorrectly when duplicate is outside current window

Window shrinks unnecessarily, missing valid subarrays

✅ Only move left pointer if last seen index is >= left pointer

Returning 0 or wrong value when no duplicates exist

Fails test cases expecting -1

✅ Return -1 if minimum length remains infinity after processing

Using nested loops without breaking early on duplicate detection

Unnecessary computations causing TLE

✅ Break inner loop immediately after finding a duplicate in brute force

🧠

Brute Force (Nested Loops Checking All Subarrays)

💡 This approach exists to build intuition by exhaustively checking all possible consecutive groups to find duplicates, which helps understand the problem deeply before optimizing.

Intuition

Check every possible consecutive subarray and see if it contains duplicates. The smallest such subarray length is the answer.

Algorithm

1. Iterate over all possible start indices of subarrays.
2. For each start, iterate over all possible end indices to form subarrays.
3. Check if the current subarray contains any duplicate card.
4. Track the minimum length of such subarrays and return it, or -1 if none found.

💡 This algorithm is straightforward but inefficient because it checks all subarrays and duplicates inside them repeatedly.

</>

Code

def minimumCardPickup(cards):
    n = len(cards)
    min_len = float('inf')
    for start in range(n):
        seen = set()
        for end in range(start, n):
            if cards[end] in seen:
                min_len = min(min_len, end - start + 1)
                break
            seen.add(cards[end])
    return min_len if min_len != float('inf') else -1

# Driver code
if __name__ == '__main__':
    print(minimumCardPickup([3,4,2,3,4,7]))  # Output: 4
    print(minimumCardPickup([1,0,5,3]))      # Output: -1

Line Notes

for start in range(n):Outer loop picks the start index of the subarray

seen = set()Initialize a set to track duplicates in the current subarray

for end in range(start, n):Inner loop picks the end index of the subarray

if cards[end] in seen:Check if current card is a duplicate in this subarray

import java.util.*;
public class Main {
    public static int minimumCardPickup(int[] cards) {
        int n = cards.length;
        int minLen = Integer.MAX_VALUE;
        for (int start = 0; start < n; start++) {
            Set<Integer> seen = new HashSet<>();
            for (int end = start; end < n; end++) {
                if (seen.contains(cards[end])) {
                    minLen = Math.min(minLen, end - start + 1);
                    break;
                }
                seen.add(cards[end]);
            }
        }
        return minLen == Integer.MAX_VALUE ? -1 : minLen;
    }

    public static void main(String[] args) {
        System.out.println(minimumCardPickup(new int[]{3,4,2,3,4,7})); // 4
        System.out.println(minimumCardPickup(new int[]{1,0,5,3}));     // -1
    }
}

Line Notes

for (int start = 0; start < n; start++) {Outer loop selects subarray start

Set<Integer> seen = new HashSet<>();Track duplicates in current subarray

for (int end = start; end < n; end++) {Inner loop selects subarray end

if (seen.contains(cards[end])) {Detect duplicate card in subarray

#include <iostream>
#include <vector>
#include <unordered_set>
#include <climits>
using namespace std;

int minimumCardPickup(vector<int>& cards) {
    int n = cards.size();
    int minLen = INT_MAX;
    for (int start = 0; start < n; start++) {
        unordered_set<int> seen;
        for (int end = start; end < n; end++) {
            if (seen.count(cards[end])) {
                minLen = min(minLen, end - start + 1);
                break;
            }
            seen.insert(cards[end]);
        }
    }
    return minLen == INT_MAX ? -1 : minLen;
}

int main() {
    vector<int> cards1 = {3,4,2,3,4,7};
    vector<int> cards2 = {1,0,5,3};
    cout << minimumCardPickup(cards1) << endl; // 4
    cout << minimumCardPickup(cards2) << endl; // -1
    return 0;
}

Line Notes

for (int start = 0; start < n; start++) {Outer loop picks subarray start index

unordered_set<int> seen;Set to track duplicates in current subarray

for (int end = start; end < n; end++) {Inner loop picks subarray end index

if (seen.count(cards[end])) {Check if current card is duplicate

function minimumCardPickup(cards) {
    const n = cards.length;
    let minLen = Infinity;
    for (let start = 0; start < n; start++) {
        const seen = new Set();
        for (let end = start; end < n; end++) {
            if (seen.has(cards[end])) {
                minLen = Math.min(minLen, end - start + 1);
                break;
            }
            seen.add(cards[end]);
        }
    }
    return minLen === Infinity ? -1 : minLen;
}

// Test cases
console.log(minimumCardPickup([3,4,2,3,4,7])); // 4
console.log(minimumCardPickup([1,0,5,3]));     // -1

Line Notes

for (let start = 0; start < n; start++) {Outer loop selects start of subarray

const seen = new Set();Track duplicates in current subarray

for (let end = start; end < n; end++) {Inner loop selects end of subarray

if (seen.has(cards[end])) {Detect duplicate card in subarray

⏱

Complexity

TimeO(n^2)

SpaceO(n)

Two nested loops generate O(n^2) subarrays; each subarray uses a set that can grow up to O(n).

💡 For n=1000, this means about 1,000,000 checks, which is too slow for large inputs.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem and correctness before optimizing.

🧠

Using Last Seen Map to Track Duplicates

💡 This approach improves efficiency by remembering the last index where each card appeared, avoiding redundant checks.

Intuition

Keep a map of the last index each card was seen. When a duplicate is found, calculate the distance between indices to update the minimum length.

Algorithm

1. Initialize a dictionary to store last seen indices of cards.
2. Iterate through the cards array.
3. For each card, if it was seen before, calculate the distance to the previous index and update minimum length.
4. Update the last seen index for the current card.
5. Return the minimum length found or -1 if none.

💡 This algorithm efficiently finds duplicates by leveraging a map to avoid scanning subarrays repeatedly.

</>

Code

def minimumCardPickup(cards):
    last_seen = {}
    min_len = float('inf')
    for i, card in enumerate(cards):
        if card in last_seen:
            min_len = min(min_len, i - last_seen[card] + 1)
        last_seen[card] = i
    return min_len if min_len != float('inf') else -1

# Driver code
if __name__ == '__main__':
    print(minimumCardPickup([3,4,2,3,4,7]))  # Output: 4
    print(minimumCardPickup([1,0,5,3]))      # Output: -1

Line Notes

last_seen = {}Dictionary to store last index of each card

for i, card in enumerate(cards):Iterate over cards with index

if card in last_seen:Check if card appeared before to find duplicates

min_len = min(min_len, i - last_seen[card] + 1)Update minimum length with current duplicate gap

import java.util.*;
public class Main {
    public static int minimumCardPickup(int[] cards) {
        Map<Integer, Integer> lastSeen = new HashMap<>();
        int minLen = Integer.MAX_VALUE;
        for (int i = 0; i < cards.length; i++) {
            int card = cards[i];
            if (lastSeen.containsKey(card)) {
                minLen = Math.min(minLen, i - lastSeen.get(card) + 1);
            }
            lastSeen.put(card, i);
        }
        return minLen == Integer.MAX_VALUE ? -1 : minLen;
    }

    public static void main(String[] args) {
        System.out.println(minimumCardPickup(new int[]{3,4,2,3,4,7})); // 4
        System.out.println(minimumCardPickup(new int[]{1,0,5,3}));     // -1
    }
}

Line Notes

Map<Integer, Integer> lastSeen = new HashMap<>();Map to track last index of each card

for (int i = 0; i < cards.length; i++) {Iterate over cards by index

if (lastSeen.containsKey(card)) {Check if card seen before to find duplicates

minLen = Math.min(minLen, i - lastSeen.get(card) + 1);Update minimum length with duplicate gap

#include <iostream>
#include <vector>
#include <unordered_map>
#include <climits>
using namespace std;

int minimumCardPickup(vector<int>& cards) {
    unordered_map<int, int> lastSeen;
    int minLen = INT_MAX;
    for (int i = 0; i < (int)cards.size(); i++) {
        int card = cards[i];
        if (lastSeen.count(card)) {
            minLen = min(minLen, i - lastSeen[card] + 1);
        }
        lastSeen[card] = i;
    }
    return minLen == INT_MAX ? -1 : minLen;
}

int main() {
    vector<int> cards1 = {3,4,2,3,4,7};
    vector<int> cards2 = {1,0,5,3};
    cout << minimumCardPickup(cards1) << endl; // 4
    cout << minimumCardPickup(cards2) << endl; // -1
    return 0;
}

Line Notes

unordered_map<int, int> lastSeen;Map to store last index of each card

for (int i = 0; i < (int)cards.size(); i++) {Iterate over cards by index

if (lastSeen.count(card)) {Check if card appeared before to find duplicates

minLen = min(minLen, i - lastSeen[card] + 1);Update minimum length with current duplicate gap

function minimumCardPickup(cards) {
    const lastSeen = new Map();
    let minLen = Infinity;
    for (let i = 0; i < cards.length; i++) {
        const card = cards[i];
        if (lastSeen.has(card)) {
            minLen = Math.min(minLen, i - lastSeen.get(card) + 1);
        }
        lastSeen.set(card, i);
    }
    return minLen === Infinity ? -1 : minLen;
}

// Test cases
console.log(minimumCardPickup([3,4,2,3,4,7])); // 4
console.log(minimumCardPickup([1,0,5,3]));     // -1

Line Notes

const lastSeen = new Map();Map to track last index of each card

for (let i = 0; i < cards.length; i++) {Iterate over cards by index

if (lastSeen.has(card)) {Check if card appeared before to find duplicates

minLen = Math.min(minLen, i - lastSeen.get(card) + 1);Update minimum length with duplicate gap

⏱

Complexity

TimeO(n)

SpaceO(n)

Single pass through cards with constant time map lookups and updates.

💡 For n=100,000, this means about 100,000 operations, which is efficient for large inputs.

Interview Verdict: Accepted

This approach is efficient and practical for interviews and real-world use.

🧠

Sliding Window with Last Seen Map (Fixed Window Variant)

💡 This approach uses a sliding window to maintain a window of cards without duplicates, shrinking it when duplicates appear, which is a classic sliding window pattern.

Intuition

Expand the window by moving right pointer; when a duplicate is found, move left pointer to exclude the previous occurrence, keeping the window valid and tracking minimum length.

Algorithm

1. Initialize two pointers left and right at 0, and a map to track last seen indices.
2. Expand right pointer over cards.
3. If current card was seen and its last seen index is within the current window, move left pointer to last seen index + 1.
4. Update last seen index of current card to right.
5. Update minimum length with current window size when duplicates are found.
6. Return minimum length or -1 if none.

💡 This algorithm dynamically adjusts the window size to maintain uniqueness and efficiently finds the minimum duplicate subarray.

</>

Code

def minimumCardPickup(cards):
    last_seen = {}
    left = 0
    min_len = float('inf')
    for right, card in enumerate(cards):
        if card in last_seen and last_seen[card] >= left:
            left = last_seen[card] + 1
        last_seen[card] = right
        if right - left + 1 > 1:
            min_len = min(min_len, right - left + 1)
    return min_len if min_len != float('inf') else -1

# Driver code
if __name__ == '__main__':
    print(minimumCardPickup([3,4,2,3,4,7]))  # Output: 4
    print(minimumCardPickup([1,0,5,3]))      # Output: -1

Line Notes

last_seen = {}Map to track last seen indices of cards

left = 0Left pointer of sliding window

if card in last_seen and last_seen[card] >= left:Check if duplicate is inside current window

left = last_seen[card] + 1Move left pointer to exclude previous duplicate

import java.util.*;
public class Main {
    public static int minimumCardPickup(int[] cards) {
        Map<Integer, Integer> lastSeen = new HashMap<>();
        int left = 0, minLen = Integer.MAX_VALUE;
        for (int right = 0; right < cards.length; right++) {
            int card = cards[right];
            if (lastSeen.containsKey(card) && lastSeen.get(card) >= left) {
                left = lastSeen.get(card) + 1;
            }
            lastSeen.put(card, right);
            if (right - left + 1 > 1) {
                minLen = Math.min(minLen, right - left + 1);
            }
        }
        return minLen == Integer.MAX_VALUE ? -1 : minLen;
    }

    public static void main(String[] args) {
        System.out.println(minimumCardPickup(new int[]{3,4,2,3,4,7})); // 4
        System.out.println(minimumCardPickup(new int[]{1,0,5,3}));     // -1
    }
}

Line Notes

Map<Integer, Integer> lastSeen = new HashMap<>();Map to track last seen indices

int left = 0, minLen = Integer.MAX_VALUE;Initialize left pointer and min length

if (lastSeen.containsKey(card) && lastSeen.get(card) >= left) {Check if duplicate inside window

left = lastSeen.get(card) + 1;Move left pointer to exclude duplicate

#include <iostream>
#include <vector>
#include <unordered_map>
#include <climits>
using namespace std;

int minimumCardPickup(vector<int>& cards) {
    unordered_map<int, int> lastSeen;
    int left = 0, minLen = INT_MAX;
    for (int right = 0; right < (int)cards.size(); right++) {
        int card = cards[right];
        if (lastSeen.count(card) && lastSeen[card] >= left) {
            left = lastSeen[card] + 1;
        }
        lastSeen[card] = right;
        if (right - left + 1 > 1) {
            minLen = min(minLen, right - left + 1);
        }
    }
    return minLen == INT_MAX ? -1 : minLen;
}

int main() {
    vector<int> cards1 = {3,4,2,3,4,7};
    vector<int> cards2 = {1,0,5,3};
    cout << minimumCardPickup(cards1) << endl; // 4
    cout << minimumCardPickup(cards2) << endl; // -1
    return 0;
}

Line Notes

unordered_map<int, int> lastSeen;Map to track last seen indices

int left = 0, minLen = INT_MAX;Initialize left pointer and min length

if (lastSeen.count(card) && lastSeen[card] >= left) {Check if duplicate inside current window

left = lastSeen[card] + 1;Move left pointer to exclude duplicate

function minimumCardPickup(cards) {
    const lastSeen = new Map();
    let left = 0, minLen = Infinity;
    for (let right = 0; right < cards.length; right++) {
        const card = cards[right];
        if (lastSeen.has(card) && lastSeen.get(card) >= left) {
            left = lastSeen.get(card) + 1;
        }
        lastSeen.set(card, right);
        if (right - left + 1 > 1) {
            minLen = Math.min(minLen, right - left + 1);
        }
    }
    return minLen === Infinity ? -1 : minLen;
}

// Test cases
console.log(minimumCardPickup([3,4,2,3,4,7])); // 4
console.log(minimumCardPickup([1,0,5,3]));     // -1

Line Notes

const lastSeen = new Map();Map to track last seen indices

let left = 0, minLen = Infinity;Initialize left pointer and min length

if (lastSeen.has(card) && lastSeen.get(card) >= left) {Check if duplicate inside window

left = lastSeen.get(card) + 1;Move left pointer to exclude duplicate

⏱

Complexity

TimeO(n)

SpaceO(n)

Each card is visited once; left pointer only moves forward, so total O(n) time.

💡 This approach is efficient and uses the sliding window pattern to handle duplicates dynamically.

Interview Verdict: Accepted

This is the optimal approach demonstrating sliding window mastery and is ideal for interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the last seen map or sliding window approach in 95% of interviews for efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(n)	No	N/A	Mention only - never code due to inefficiency
2. Last Seen Map	O(n)	O(n)	No	Yes (length only)	Code this for efficient solution
3. Sliding Window with Last Seen Map	O(n)	O(n)	No	Yes (length and indices)	Optimal approach demonstrating sliding window mastery

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to show understanding.Step 3: Explain the last seen map optimization and code it.Step 4: Discuss the sliding window variant for optimal performance.Step 5: Test your code with edge cases and explain complexity.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

The interviewer tests your problem understanding, ability to optimize from brute force to efficient solutions, and your coding accuracy.

Common Follow-ups

• What if you want to find the actual subarray, not just length? → Track indices during processing.
• Can you solve it if cards are streamed one by one? → Use a sliding window with a map and update dynamically.

💡 Follow-ups test your ability to extend solutions and handle streaming or output reconstruction.

🔍

Pattern Recognition

When to Use

1) Problem asks for minimum length subarray with duplicates; 2) Input is array or string; 3) Need to track last seen positions; 4) Sliding window or two pointers can be applied.

Signature Phrases

'minimum number of consecutive cards''at least two cards with the same value'

NOT This Pattern When

Problems asking for maximum length subarray without duplicates or counting distinct elements without minimum length focus.

Similar Problems

Minimum Size Subarray Sum - similar minimum length subarray problemLongest Substring Without Repeating Characters - uses last seen map to track duplicates

Practice

1. You manage a bookstore where customers arrive each minute, but the owner sometimes gets grumpy and ignores customers during certain minutes. You can choose a continuous time window of fixed length to calm the owner, making them satisfied during that window. Which algorithmic approach guarantees finding the maximum total satisfied customers?

easy

A. Sliding window to find the window maximizing extra satisfied customers plus base satisfaction

B. Dynamic programming over all subsets of minutes to maximize satisfaction

C. Greedy approach selecting the largest single minute with grumpy customers

D. Sorting customers by count and picking top X minutes regardless of continuity

Solution

1. Step 1: Understand problem constraints

   The problem requires selecting a continuous window of fixed length to maximize extra satisfaction, so continuity matters.

2. Step 2: Identify suitable algorithm

   Sliding window efficiently finds the maximum sum of grumpy customers in any continuous window, combined with base satisfaction from non-grumpy minutes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window handles continuous windows optimally [OK]

Hint: Continuous window optimization -> sliding window [OK]

Common Mistakes:

• Thinking greedy picking largest single minute suffices
• Ignoring continuity of window
• Trying DP over subsets unnecessarily

2. You are given an array of integers and a fixed window size k. For each contiguous subarray of size k, you need to find the maximum element efficiently. Which of the following approaches guarantees an optimal O(n) time complexity solution?

easy

A. Use a brute force nested loop to check all elements in each window.

B. Use a max-heap (priority queue) to store elements of the current window and extract the max.

C. Use dynamic programming to precompute maximums for overlapping intervals.

D. Maintain a deque that stores indices of elements in decreasing order, removing indices outside the current window.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding maximums for all windows of size k in an array of size n, aiming for an efficient solution.

2. Step 2: Evaluate each approach's time complexity and correctness

   Brute force (nested loops) is O(n*k), max-heap approach is O(n log k), and DP approach is not straightforward here. The deque approach maintains indices in decreasing order and removes outdated indices, achieving O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Deque approach is known as the optimal sliding window maximum solution [OK]

Hint: Monotonic deque achieves O(n) by removing outdated and smaller elements [OK]

Common Mistakes:

• Thinking max-heap is optimal despite log k overhead
• Assuming DP applies directly without preprocessing
• Believing brute force is acceptable for large n

3. What is the time complexity of the optimal two-pointer sliding window solution for counting binary subarrays with a given sum, and why?

medium

A. O(n^2) because the inner while loop can run up to n times for each right pointer.

B. O(n) because each element is visited at most twice by the left and right pointers.

C. O(n log n) due to sorting or binary search steps involved.

D. O(n) but with O(n) auxiliary space for prefix sums or hash maps.

Solution

1. Step 1: Analyze outer and inner loops

   The right pointer moves from 0 to n-1 once; the left pointer only moves forward when shrinking window, also at most n times.

2. Step 2: Confirm total operations

   Each element is added once and removed once from current_sum, so total operations are proportional to 2n = O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two-pointer approach visits each element at most twice [OK]

Hint: Two pointers each move forward at most n times [OK]

Common Mistakes:

• Assuming inner while loop runs n times per right pointer iteration
• Confusing with prefix sum + hashmap space complexity
• Thinking sorting or binary search is involved

4. What is the time complexity of the sliding window approach for the Minimum Size Subarray Sum problem, and why might some candidates incorrectly think it is O(n²)?

medium

A. O(n log n) due to sorting or binary search inside the loop

B. O(n²) because of nested loops implied by two pointers

C. O(n) because each element is visited at most twice by left and right pointers

D. O(n) but with O(n) auxiliary space for prefix sums

Solution

1. Step 1: Identify pointer movements

   Right pointer moves forward once per iteration; left pointer moves forward only when shrinking window, each element visited at most twice.

2. Step 2: Analyze total operations

   Since both pointers only move forward, total operations are proportional to 2n = O(n), no nested repeated scanning.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two-pointer sliding window is classic O(n) approach [OK]

Hint: Two pointers each move forward once -> O(n) [OK]

Common Mistakes:

• Assuming nested loops cause O(n²)
• Confusing prefix sums with sliding window
• Thinking auxiliary space affects time complexity

5. Suppose the problem changes: now you want to find the maximum average subarray of size at most k (i.e., any size from 1 up to k). Which approach correctly adapts the sliding window technique to solve this efficiently?

hard

A. Use nested loops to check all subarrays of size 1 to k, recomputing sums each time

B. Use a sliding window of size k and track max average for all smaller windows by shrinking the window dynamically

C. Use prefix sums to compute sums of all subarrays up to size k in O(n) time

D. Use a sliding window for each size from 1 to k separately, then take the maximum average found

Solution

1. Step 1: Understand problem change

   Now subarray size can vary from 1 to k, so fixed-size sliding window alone is insufficient.

2. Step 2: Evaluate approaches

   Use a sliding window for each size from 1 to k separately, then take the maximum average found runs sliding window for each size from 1 to k, each in O(n), total O(n*k), which is efficient and correct. Using a sliding window of size k and tracking max average for all smaller windows by shrinking the window dynamically is incorrect because shrinking window dynamically breaks fixed-size window assumptions. Using prefix sums to compute sums of all subarrays up to size k in O(n) time is incorrect as prefix sums alone do not reduce complexity below O(n*k). Using nested loops to check all subarrays of size 1 to k, recomputing sums each time is naive and inefficient.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sliding window repeated for each size is correct and efficient [OK]

Hint: Sliding window works per fixed size; vary size by repeating windows [OK]

Common Mistakes:

• Trying to shrink window dynamically breaking fixed size
• Assuming prefix sums alone solve all size ranges efficiently