Hash Table and Sliding Window Problem: “Minimum Consecutive Cards to Pick Up”
Lets start with the Problem of the Day from the “Programming with DPwala” series by Yash Gaherwar.
-“𝐎𝐧𝐞 𝐂𝐨𝐝𝐢𝐧𝐠 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐚 𝐝𝐚𝐲 𝐤𝐞𝐞𝐩𝐬 𝐭𝐡𝐞 𝐏𝐥𝐚𝐜𝐞𝐦𝐞𝐧𝐭 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐚𝐰𝐚𝐲 !!”
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.
Sample Input :- cards = [3,4,2,3,4,7]
Output :- 4
Given 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.
- 1 <= cards.length <= 10⁵
- 0 <= cards[i] <= 10⁶
Approach Required:- “Hash Table and Sliding Window Technique” .
My Approach to solve this Problem :-
- Firstly the question can be easily solved using Sliding window technique.
- In Sliding window approach we will keep on calculating the frequency of every Element in Map and if we encountered any character which having frequency greater than one from their we started shrinking our window till we get that value again and updating our ans variable.
- And at last we simply return ans if we have a matching card else we return -1 if it is impossible to have it (when ans==INT_MAX in our case).
- We can simply do this question in O(N) Time Complexity rather than using Sliding window technique which take O(N*log(N)) time.
- We will using map and mp.find() function to check whether the element is present in our map or not if it is present than we simply calculate the window length and update our ans variable. And all the time we are storing corresponding index of every element.
Approach 1:- Sliding Window Approach.
Complexity Analysis for Approach 1:-
Time Complexity : O(N*log(N))
Space Complexity : O(N)
Approach 2:- Hash Table (using Map in C++) Approach.
Complexity Analysis for Approach 2:-
Time Complexity : O(N)
Space Complexity : O(N)
Hope you might learned the approach required to solve this Problems. I tried to explain the Problem using both Hash Table and Sliding Window Approach.
Hope this “Daily Coding Problem with Yash Gaherwar” initiative will help many to solve at least one Coding Problem daily and remove their fear related to Programming and maintaining consistency.
Join the Programming Community:- “Programming with DPwala”
Link for Joining the Programming Community:- Programming with DPwala
Stay connected with me on Medium and LinkedIn for daily updates..