< Back

2260. Minimum Consecutive Cards to Pick Up

Another problem that can be solved with hashing to keep track of the last time we've seen a value.
Hashing will allow us to determine the minimum length between to occurrences of the same card. This
question is essentially asking for the minimum length subarray that contains a duplicate amongst an
array that possibly contains duplicates.

To solve this problem, first we confirm that there is a duplicate, otherwise we return -1. We do this
by creating a set from the input list or cards, and comparing the sets length against the lenght of
the input list. If the set is equal to the length of the input list, we know that all values are
unique - there are no duplicates. Return -1.

Next, we create a seen dictionary to keep track of the last time we've seen a particular card. We
maintain an answer variable to minimize across the iteration of the list. Enumerating the list,
we track the index and the value of the card. If the card has appeared before, we calculate the
answer, taking the minimum value between the current answer and the difference of the current index
and the last seen index. We update the seen dictionary, storing the current index of the last time
we've seen this card value.

If the card hasn't been seen before, we add it to the seen dictionary.

The solution is as follows:

  from collections import defaultdict

  class Solution:
      def minimumCardPickup(self, cards: List[int]) -> int:
          seen = defaultdict(int)
          ans = float("inf")

          for i, card in enumerate(cards):
              if card in seen:
                  ans = min(ans, i - seen[card] + 1)

              seen[card] = i

          return ans if ans < float("inf") else -1

_ Time Complexity:

  O(n) - We iterate through the input list once.

_ Space Complexity:

  O(n) - We store at most n values in the seen dictionary.