Minimum Consecutive Cards to Pick Up
MedPrompt
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 <= 1050 <= cards[i] <= 106
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize a variable
minLengthto a very large number (e.g.,Integer.MAX_VALUE). - Get the total number of cards,
n. - Use a
forloop with an indexito iterate from0ton-1. - Inside this loop, use a nested
forloop with an indexjto iterate fromi+1ton-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
minLengthto be the minimum of its current value and the newlength. - After the loops finish, check if
minLengthis still at its initial large value. - If it is, no matching pair was found, so return
-1. - Otherwise, return
minLength.
Walkthrough
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:
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; }}Complexity
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.
Trade-offs
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).
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.
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
cardsarray fromi = 0ton-1and populateindexedCardswith(cards[i], i). - Sort the
indexedCardsstructure. The primary sorting key should be the card value. - Initialize
minLengthtoInteger.MAX_VALUE. - Iterate through the sorted
indexedCardsfrom the second element (i = 1ton-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
minLengthhas not changed from its initial value, return-1. Otherwise, returnminLength.
Walkthrough
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:
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Initialize
minLengthtoInteger.MAX_VALUE. - Create a
HashMapnamedlastIndexMapto store the last seen index of each card value, mappingcard_valuetoindex. - Iterate through the
cardsarray using an indexifrom0ton-1. - For each
card = cards[i], check iflastIndexMapcontains the keycard. - If it does, retrieve its last seen index:
prevIndex = lastIndexMap.get(card). - Calculate the number of consecutive cards:
length = i - prevIndex + 1. - Update
minLengthwith the minimum of its current value and this newlength. - After the check, update the map with the current card's index:
lastIndexMap.put(card, i). - After the loop completes, if
minLengthis stillInteger.MAX_VALUE, return-1. - Otherwise, return the final
minLength.
Walkthrough
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:
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; }}Complexity
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).
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.