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).
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; }}Video 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.