Minimum Consecutive Cards to Pick up solution leetcode

Tags: leetcode java python hashmap

An interesting problem on leetcode to find minimum number of ways to pick up consecutive cards. We will start with a brute force algorithm that would exceed in time limit. Later we will improve upon this algorithm using hashmap.

Problem Statement

You are given an integer array cards where cards[i] represents the value of the i^th 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.

Brute force Solution

A simple intuitive solution would be to pick up a card, and then iterate over the remaining cards to find the minimum length.

Java
Python

This will fail as the time limit will exceed while submiting the solution to leetcode. This is because the time complexity of the solution is O(n²).

Using HashMap

Lets take an example with a use case of following input

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

Next we can create a hashmap to keep track of indices of a particular card.

Java
Python

Complexity

Time Complexity is $$\theta(n * m)$$.