life is too short for a diary

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 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.

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.

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(n2).

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.

hash map picture


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

comments powered by Disqus