LeetCode 2260 - Minimum Consecutive Cards to Pick Up

The problem gives an integer array cards, where each number represents the value written on a card. Two cards are considered matching if they contain the same value.

leetcodemediumarrayhash-tablesliding-window

LeetCode Problem 2260

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Sliding Window

Solution

Problem Understanding

The problem gives an integer array cards, where each number represents the value written on a card. Two cards are considered matching if they contain the same value.

We must find the minimum number of consecutive cards that need to be picked so that the selected group contains at least one matching pair. In other words, we are looking for the shortest contiguous subarray that contains two equal values.

Suppose the same value appears at indices i and j, where i < j. Then the consecutive segment from i to j contains both cards, and its length is:

$j-i+1$

Our task is therefore equivalent to finding the smallest distance between two equal values, measured as j - i + 1.

The constraints are important:

  • The array length can be as large as 10^5
  • Card values can be as large as 10^6

Because the input can be very large, any algorithm slower than linear or near linear time will likely be too slow. In particular, an O(n^2) solution would not scale well for arrays of size 100000.

Several edge cases are important:

  • Arrays with no duplicate values should return -1
  • Arrays where the duplicate cards are adjacent should return 2
  • Arrays containing many repeated values require us to correctly track the closest occurrences
  • Arrays of length 1 can never contain a pair

The problem guarantees valid integer inputs and non-empty arrays.

Approaches

Brute Force Approach

A straightforward approach is to examine every possible subarray and check whether it contains a duplicate value.

For each starting index, we can expand the subarray one element at a time while keeping track of values already seen in that subarray. The moment we encounter a duplicate, we compute the subarray length and update the answer.

This works because every possible consecutive segment is examined, so the minimum valid segment will eventually be found.

However, this approach is too slow. There are O(n^2) possible subarrays, and even with optimizations, repeatedly scanning ranges becomes expensive for n = 100000.

Key Insight

The important observation is that we do not actually need to examine all subarrays.

If two equal cards appear at indices i and j, then the smallest consecutive segment containing both is exactly the range between them.

So instead of checking every subarray, we only need to track the previous occurrence of each card value.

As we iterate through the array:

  • If we see a value for the first time, we record its index
  • If we see the value again, we compute the distance between the current index and the previous index
  • We keep the minimum such distance

A hash map is ideal here because it allows constant time lookup of the most recent occurrence of a value.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Checks many subarrays explicitly
Optimal O(n) O(n) Uses a hash map to track previous indices

Algorithm Walkthrough

  1. Initialize a hash map called last_seen.

This map stores the most recent index where each card value appeared. The key is the card value, and the value is its latest index. 2. Initialize a variable minimum_length with infinity.

This variable tracks the smallest valid subarray length found so far. 3. Iterate through the array using index i and value card.

At each step, we process the current card value. 4. Check whether the current card value already exists in the hash map.

If it does, then we have found a matching pair. 5. Compute the subarray length.

If the previous occurrence was at index previous_index, then the consecutive segment length is:

$i-previous_index+1$

  1. Update the minimum answer.

Compare the newly computed length with the current best answer and keep the smaller value. 2. Update the hash map.

Store the current index as the most recent occurrence of this card value. 3. After processing all elements, return the result.

  • If no duplicate was found, return -1
  • Otherwise, return the minimum length

Why it works

The algorithm works because any valid answer must begin and end with two equal card values. For every repeated value, the smallest possible subarray containing that pair is the range between consecutive occurrences.

By always storing the latest occurrence of each value, we guarantee that every candidate segment considered is the shortest possible for that repeated value. Taking the minimum across all repeated values therefore produces the globally optimal answer.

Python Solution

from typing import List

class Solution:
    def minimumCardPickup(self, cards: List[int]) -> int:
        last_seen = {}
        minimum_length = float("inf")

        for index, card in enumerate(cards):
            if card in last_seen:
                current_length = index - last_seen[card] + 1
                minimum_length = min(minimum_length, current_length)

            last_seen[card] = index

        return minimum_length if minimum_length != float("inf") else -1

The implementation starts by creating a dictionary called last_seen. This dictionary maps each card value to the most recent index where it appeared.

The variable minimum_length is initialized to infinity so that any valid subarray length found later will replace it.

The loop iterates through the array using enumerate, giving both the current index and card value.

Whenever the current card has appeared before, the code calculates the distance between the current index and the previous occurrence. Adding 1 converts the index difference into the actual subarray length.

The answer is updated using min, ensuring we always keep the smallest valid segment found so far.

Finally, the current index is stored in the dictionary so future duplicates can use it as the latest occurrence.

At the end:

  • If no duplicate was ever found, minimum_length remains infinity, so the function returns -1
  • Otherwise, the minimum valid length is returned

Go Solution

import "math"

func minimumCardPickup(cards []int) int {
    lastSeen := make(map[int]int)
    minimumLength := math.MaxInt32

    for index, card := range cards {
        if previousIndex, exists := lastSeen[card]; exists {
            currentLength := index - previousIndex + 1

            if currentLength < minimumLength {
                minimumLength = currentLength
            }
        }

        lastSeen[card] = index
    }

    if minimumLength == math.MaxInt32 {
        return -1
    }

    return minimumLength
}

The Go implementation follows the same logic as the Python version.

A map[int]int is used to store the latest index for each card value. The variable minimumLength is initialized with math.MaxInt32 as a stand-in for infinity.

Go maps return two values during lookup:

value, exists := map[key]

The boolean exists indicates whether the key was already present.

Unlike Python, Go does not have a built-in infinity value for integers, so a very large integer constant is used instead.

The algorithm otherwise behaves identically to the Python solution.

Worked Examples

Example 1

Input:

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

We trace the algorithm step by step.

Index Card Last Seen Before Current Length Minimum Length Last Seen Map
0 3 No - inf {3: 0}
1 4 No - inf {3: 0, 4: 1}
2 2 No - inf {3: 0, 4: 1, 2: 2}
3 3 Yes, at 0 4 4 {3: 3, 4: 1, 2: 2}
4 4 Yes, at 1 4 4 {3: 3, 4: 4, 2: 2}
5 7 No - 4 {3: 3, 4: 4, 2: 2, 7: 5}

Final answer:

4

The optimal subarrays are:

[3,4,2,3]
[4,2,3,4]

Example 2

Input:

cards = [1,0,5,3]
Index Card Last Seen Before Current Length Minimum Length Last Seen Map
0 1 No - inf {1: 0}
1 0 No - inf {1: 0, 0: 1}
2 5 No - inf {1: 0, 0: 1, 5: 2}
3 3 No - inf {1: 0, 0: 1, 5: 2, 3: 3}

No duplicates are ever found, so the answer is:

-1

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is processed once
Space O(n) The hash map may store every distinct card value

The algorithm performs a single pass through the array. Each hash map lookup and insertion is O(1) on average, so the total runtime is linear.

The extra memory usage comes from the hash map. In the worst case, every card value is unique, so the map stores all n elements.

Test Cases

from typing import List

class Solution:
    def minimumCardPickup(self, cards: List[int]) -> int:
        last_seen = {}
        minimum_length = float("inf")

        for index, card in enumerate(cards):
            if card in last_seen:
                current_length = index - last_seen[card] + 1
                minimum_length = min(minimum_length, current_length)

            last_seen[card] = index

        return minimum_length if minimum_length != float("inf") else -1

solution = Solution()

assert solution.minimumCardPickup([3, 4, 2, 3, 4, 7]) == 4  # provided example
assert solution.minimumCardPickup([1, 0, 5, 3]) == -1  # no duplicates
assert solution.minimumCardPickup([1, 1]) == 2  # adjacent duplicate
assert solution.minimumCardPickup([1]) == -1  # single element
assert solution.minimumCardPickup([1, 2, 3, 1]) == 4  # duplicate at ends
assert solution.minimumCardPickup([1, 2, 1, 2, 1]) == 3  # multiple duplicates
assert solution.minimumCardPickup([5, 5, 5, 5]) == 2  # repeated same value
assert solution.minimumCardPickup([1, 2, 3, 4, 5]) == -1  # all unique
assert solution.minimumCardPickup([7, 8, 9, 7, 8]) == 4  # multiple candidate pairs
assert solution.minimumCardPickup([0, 1000000, 0]) == 3  # large card values
Test Why
[3,4,2,3,4,7] Validates the standard example
[1,0,5,3] Confirms -1 when no duplicates exist
[1,1] Tests smallest valid answer
[1] Tests minimum array size
[1,2,3,1] Duplicate appears at both ends
[1,2,1,2,1] Multiple repeated values
[5,5,5,5] Repeated identical values throughout
[1,2,3,4,5] All values distinct
[7,8,9,7,8] Multiple candidate subarrays
[0,1000000,0] Tests constraint boundary values

Edge Cases

One important edge case is an array with no duplicate values. A careless implementation might return an uninitialized value or an extremely large number instead of -1. This implementation avoids that problem by initializing the answer to infinity and explicitly checking whether it changed before returning.

Another important edge case is when duplicate cards are adjacent, such as [5,5]. The shortest possible valid answer is 2, since two consecutive equal cards already form a matching pair. The algorithm correctly computes:

$1-0+1=2$

A third important edge case occurs when a value appears many times, such as [1,2,1,2,1]. A buggy implementation might compare only the first and last occurrence, producing a larger answer than necessary. This implementation continuously updates the latest occurrence in the hash map, ensuring the shortest distance between consecutive duplicates is always considered.

A final edge case involves very large inputs near the constraint limit. Since the algorithm processes each element exactly once and uses constant time hash map operations, it remains efficient even for arrays with 100000 elements.