Description

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:

1Input: cards = [3,4,2,3,4,7]
2Output: 4
3Explanation: 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:

1Input: cards = [1,0,5,3]
2Output: -1
3Explanation: There is no way to pick up a set of consecutive cards that contain a pair of matching cards.

Constraints:

  • 1 <= cards.length <= 10^5
  • 0 <= cards[i] <= 10^6

Solution

Using Sliding Window and HashMap

This problem could be solved using combination of sliding window and hashmap. We could use sliding window and at the same time store the minimum card to pick up in a variable. If we find duplicate number, we calculate the current distance and if it’s smaller than current minimumCardPickup, we update the minimumCardPickup with new minimum value. Now, in order to keep track of current distance, we have to store previous index position somewhere. We can use HashMap for this. Everytime new value is encountered, we enter it’s position in the map. If the item was already in the map, we know that we have found duplicate and we calculate current distance using currentIndex - map[currentValue]. We also have to make sure that we insert the new position to replace previous position to cover situations like [1, 2, 3, 2, 2, 3, 4]. In this case, if we are iterating from left, we might have found minimumCardPikcup=3 for value 2. However, if we update the map with new index position, we will encounter next consecutive duplicates for 2 using minimumCardPickup=2. We also have to iterate until the end of the array to cover cases where the two consecutive numbers might be same like [1, 2, 3, 1, 6, 6]. In this case, if we exit prematurely, we might get minimum cards to pickup as 4, because in subarray [1, 2, 3, 1], we encounter 1 after 3 elements. However, there is [6, 6] which would give us minimum cards to pick up as 2.

 1class Solution {
 2    public int minimumCardPickup (int[] cards) {
 3        if (cards == null || cards.length == 0) {
 4            return -1;
 5        }
 6        int minimumCardPickup = Integer.MAX_VALUE;
 7        Map<Integer, Integer> positionMap = new HashMap<>();
 8        for (int i = 0; i < cards.length; i++) {
 9            if (!positionMap.containsKey(cards[i])) {
10                positionMap.put(cards[i], i);
11            } else {
12                minimumCardPickup = Math.min(minimumCardPickup, i - positionMap.get(cards[i]) + 1);
13                positionMap.put(cards[i], i);
14            }
15        }
16        return minimumCardPickup == Integer.MAX_VALUE ? -1 : minimumCardPickup;
17    }
18}
  • Time Complexity: O(n)
  • Space Complexity: O(n)

Using HashMap to track Indices in Array

In this case, we can keep track of the last two indices in the HashMap. Essentially it’s very similar to above solution.

 1class Solution {
 2    public int minimumCardPickup2 (int[] cards) {
 3        if (cards == null || cards.length == 0) {
 4            return -1;
 5        }
 6        Map<Integer, List<Integer>> indices = new HashMap<>();
 7
 8        int minimumCardPickup = Integer.MAX_VALUE;
 9        for (int i = 0; i < cards.length; i++) {
10            if (!indices.containsKey(cards[i])) {
11                List<Integer> indexList = new ArrayList<>();
12                indexList.add(i);
13                indices.put(cards[i], indexList);
14            } else {
15                // Here we may have more than two indices for a given card.
16                // To keep only minimum difference indices, we need to find the minimum difference between two indices and store only those indices in this case.
17                List<Integer> indexList = indices.get(cards[i]);
18                if (indexList.size() == 2) {
19                    indexList.remove(0);
20                    indexList.add(i);
21                } else {
22                    indexList.add(i);
23                }
24                minimumCardPickup = Math.min(minimumCardPickup, indexList.get(1) - indexList.get(0) + 1);
25            }
26        }
27        return minimumCardPickup == Integer.MAX_VALUE ? -1 : minimumCardPickup;
28    }
29}
  • Time Complexity: O(n). This solution is doing lot more but amortized time complexity is same as previous one.
  • Space Complexity: O(n). Space Complexity is also worse because for each number, we are storing two indices in map, but amortized space complexity is again same.