Hand of Straights | Simple Thought Process | Google | Leetcode 846 | codestorywithMIK

[@CodeMode9313]

Since the while loop runs 𝑛 / 𝑔 𝑟 𝑜 𝑢 𝑝 𝑆 𝑖 𝑧 𝑒 n/groupSize times and each iteration of the for loop involves groupSize operations, each taking 𝑂 ( log ⁡ 𝑛 ) O(logn), the total time complexity of this part is: 𝑂 ( 𝑛 groupSize × groupSize × log ⁡ 𝑛 ) = 𝑂 ( 𝑛 log ⁡ 𝑛 ) O( groupSize n ​ ×groupSize×logn)=O(nlogn)

[@codestorywithMIK]

My bad. Thank you for the correction ❤️

[@gui-codes]

thanks

[@CodeMode9313]

@@codestorywithMIK its ok no issue

[@DevOpskagyaan]

Thanks man

[@prakharrohra8365]

O(n^2*logn)

[@amitchoraria5737]

I dont know if its correct but i see one more optimization that is no freq can be greater than the number of groups that can be formed. So while creating the map itself we can prune few test cases where the freq goes beyond num of groups that is hand.size()/groupSize

[@codestorywithMIK]

Ah yes. That’s a good observation 👍🏻❤️

[@darkwarrior6767]

Those comparisons will take more time than the time it saved

[@nishantsingh1834]

I think the second loop in which we are checking that a group can be made or not, has a time comp of n*logn and not n*groupsize , as inner loop will move till groupsize and outer will move till n/ groupsize and we are deleting some elements in map which will take logn so overall complexity becomes n*logn

[@nishantsingh1834]

As n*groupsize in worst case can lead to n2 as groupsize can be n

[@PradeepKumarIIITD]

Mik bhai solution daal ke hi sote ho.. loved your explaination ab to 50k ho gaye... face reveal ho jayee..

[@arthashastra_analyze]

Hello sir I have seen many of your videos your explanation is amazing 🙏💯💯

[@AkashKumarTiwary-u4b]

Woke up and solved this one, feels good ki optimal solution likha tha 😢

[@abhinay.k]

thank your sir

[@abhishektripathi3904]

I solved it without using map with O(1) extra space My solution:- class Solution { public: bool isNStraightHand(vector& hand, int groupSize) { int n = hand.size(); if(n % groupSize != 0) return false; sort(hand.begin(),hand.end()); int i = 0, j = -1, prevCard = -1, count = 0; while(i < n){ if(hand[i] < 0) i++; //if hand[i] is -ve, it means the card is already in some other group else if(prevCard != -1 && hand[i] - prevCard > 1) return false; //Checking if cards are consecutive or not else if(hand[i] == prevCard){ if(j == -1){ //first duplicate found, store it's index in j, next group will start from this index/element j = i; } i++; } else{ if(count < groupSize){ prevCard = hand[i]; hand[i] = -1 * hand[i]; //convert to -ve to denote that card is picked count++; i++; } if(count == groupSize){ prevCard = -1; count = 0; if(j != -1){ //move back to the duplicate you left back and start forming the new group from there i = j; j = -1;//Assign j back to -1 to store future possible duplicate element's index } } } } return count % groupSize == 0; //count should be either 0 or groupSize } };

[@ryanrenjith3504]

I had the same idea and approach but I just could not translate it to code. Or atleast I was too lazy today to figure out all those loops! But thanks for the final code!

[@TusharRaja3009]

Sir aise questions mein constraints given :--- hands[i]

[@prajnanammohnty950]

taki koi banda 10^9 ka array declare na karde memory limit exceeded error aajayega.

[@TusharRaja3009]

@@prajnanammohnty950 accha thanks

[@DevOpskagyaan]

You are awesome man

[@kapilnitb]

Great explanation

[@adityaraj-zm7zk]

bhaiya in this question why we use hashmap

[@indrajitpal02]

because in c++ std::map stores the values in a sorted fashion and also we can store the frequency of the elements that will provide us an efficient way to count frequency of each card value, . In case you are in python use DefaultDict(), but then you have to sort the array first, because DefaultDict only stores the oder of insertion of the elements and does not sort them, (in python there is not an inbuilt function to insert the elements in a sorted manner) Hope it helps

[@haidarmohammad8510]

MY SOLUTION class Solution { public: bool isNStraightHand(vector& hand, int groupSize) { map mp; for(auto h: hand) mp[h]++; while(mp.size()){ auto fek = mp.begin()->first; for(int i=0; i

[@CodeMode9313]

IMPORTANT !!!!!! Bhaiya time complexity is little wrong in the video i guess...for upper part its obviously nlogn but in the second part its the while loop and inside that while loop we have for loop ......so my while loop will run for N/groupsize as the for loop will remove the groupsize element everytime . Talking abt the for loop ...its complexity is groupsize*logn.....so overall time complexity for the lower half will be ..... nlogn

[@CodeMode9313]

time complexity = ( N / groupSize ) * groupSize * logN = N * logN

[@11csepratikshaargulewar71]

Could you explain why it is groupSize* logn for inner- for loop ?

[@akashsonar6332]

Correct Time complexity : O( logn + (groupSize)^2 ) logn due to sorting of map. groupSize number of we will iterate in map. Additional groupSize due to finding consecutive sequence in the map. Therefore it turns out to be O( logn + (groupSize)^2 )

[@CodeMode9313]

@@11csepratikshaargulewar71 its running for groupsize times and within that u are doing put and remove operations which takes the logn times

[@tommyshelby6277]

please also add the optimal solution, as lee215 discussed

[@nikhilhaspe2734]

|| Java Solution || class Solution { public boolean isNStraightHand(int[] hand, int groupSize) { int handSize = hand.length; if(handSize % groupSize != 0) return false; TreeMap tMap = new TreeMap(); for(int i=0; i 0){ int currentKey = tMap.entrySet().iterator().next().getKey(); for(int i=0; i

[@sarthakchafle]

You can directly use firstKey() to get the smallest element in a TreeMap

[@cosmicthor7330]

bhaeeya kl wala question clear nhi ho rha achchey sey

[@insidious_681]

sir how to traverse in map?

[@codestorywithMIK]

Example : int main() { std::map myMap; myMap[1] = "one"; myMap[2] = "two"; myMap[3] = "three"; // Using iterators for (std::map::iterator it = myMap.begin(); it != myMap.end(); ++it) { std::cout

[@visheshpandey9070]

Solved using Map Approach Beats 95% users Code: class Solution { public: bool isNStraightHand(vector& hand, int groupSize) { sort(hand.begin(),hand.end()); unordered_map mpp; for(auto it:hand) { mpp[it]++; } for(int i=0;i0) { int temp=hand[i]; mpp[hand[i]]--; int j=1; while(j

[@AryanSingh-ve7dq]

BRO CAN YOU MAKE THE O(N) STACK SOLUTION OF JUMP GAME 5 PLEASE?

[@adityaraj-zm7zk]

please provide slide also

[@mewaconite]

This question was tough for me, even though I was able to come up with intutiom to solve...lekin i was not able to correctly use map data structure

[@AbhishekKumar-zs8ry]

I solved it but my code beats only 5% of the users 😐

[@anonymous2982]

same bro!

[@dayashankarlakhotia4943]

public boolean isNStraightHand(int[]hand,int groupSize){ if(hand.length%groupSize!=0)return false; Arrays.sort(hand); for(int i=0;i=0) if(!find(hand,i,groupSize,hand.length)) return false; } return true; } private boolean find(int[]nums,int i,int groupSize,int n){ int f=nums[i]+1; nums[i]=-1; i+=1; int cmt=1; while(i