Hand of Straights - Leetcode 846 - Python

[@skepat9426]

Better if we sort the keys of the hmap O(nlogn) and then iterate over the sorted keys, much easier.

[@학교-m5c]

count = Counter(hand) orderedCount = {k: v for k, v in count.items()} while orderedCount: minElem = next(iter(orderedCount)) for card in range(minElem, minElem + groupSize): if card not in orderedCount: return False orderedCount[card] -= 1 if orderedCount[card] == 0: orderedCount.pop(card) return True

[@VijenderSingh-wr6fm]

yea i did the same , its really easy

[@RandomShowerThoughts]

did that as well initially, however, you need to ensure that you delete the values

[@wellzhang5234]

@@학교-m5c how can you make sure it's ordered?

[@victoriac7257]

Yours is almost the most clear one. your channel deserve more likes!

[@swaroopacharjee2767]

Excellent solution. I just wanted to add my own solution. 1. Sort the array in ascending order. 2. Then pick an element, and check if all the elements in the range [element, element + 1, ... , element + groupSize] is present in the array or not. 3. If there is a single value which doesn't exist, you can return False. 4. If all the elements exist, then delete those elements, and pick the next element. Continue this process till the array is empty or you don't encounter a False situation. Code: class Solution: def isNStraightHand(self, hand: List[int], groupSize: int) -> bool: hand.sort() while len(hand) != 0: temp = hand[0] for i in range(temp, temp + groupSize): if i in hand: hand.pop(hand.index(i)) else: print(i, hand) return False else: return True

[@abdullahioladosu6385]

Nice! Thanks for sharing.

[@madhavappaneni]

Good start but this solution takes O(n^2) time

[@bobfish2636]

On the explanation of why we can use a minheap instead of a treemap, you said that we would always be popping the minimum value. But what if we had [1, 1, 2, 2, 3, 3]? We'd pop 1, then look for 2, but 1 would still be our next minimum value. However, couldn't we make two hands of 1, 2, 3 and 1, 2, 3?

[@karimmohamed5355]

You only pop the min heap after the count has reached 0, so you'd pop 1, look for 2 and then look for 3 all without popping. On the next cycle though, you'll be popping on every iteration from 1 till 3.

[@RandomShowerThoughts]

let's go, I was able to get the intuition myself!

[@BishalECE-uy5rn]

I also do think that the snippet i!= minH[0] is not necessary as we can check in the ``for loop`` if the count of that element is 0 or not at that moment if it is 0 we can return false there itself.

[@tenkara101]

Correct, I read the algo and tried implementing it on my own. I "missed" adding that conditional while thinking my logic out loud, popped it into LC online judge and it worked right away.

[@tianzejiang7669]

agree, and that part confused me a lot until I removed it

[@rogerchou7762]

Hey guys, Since it takes O(nlogn) to pop the min value from the heap. What about sort the input array first, and then iterate it?

[@AshutoshKumar-es8xy]

No it takes logn for one pop

[@DavidDLee]

Sure, but if you sort an array with repetitions, you still need to somehow figure out how not to iterate through them multiple times. For example, if hand = [1,2,2,2,2,2,3,3,3,3,3, ... and you are on the first '2', how do you efficiently skip to 3 and then back to the 2nd 2? It's doable, but only with the help of more code, and is not shorter or more simple.

[@tunepa4418]

@@DavidDLee I was able to solve this by just sorting and iterate. def isNStraightHand(self, hands: List[int], groupSize: int) -> bool: if len(hands) % groupSize != 0: return False hands.sort() hands_count = collections.Counter(hands) for hand in hands: if hands_count[hand] == 0: continue hands_count[hand] -= 1 next_hand = hand + 1 count = 1 while next_hand in hands_count and hands_count[next_hand] > 0 and count < groupSize: hands_count[next_hand] -= 1 next_hand = next_hand + 1 count += 1 if count != groupSize: return False return True

[@shalsteven]

​@@tunepa4418time complexity O(n logn) for sorting + O(n) for looping?

[@chaitanya812]

instead of min heap why don't we use ordered_map in that we won't need any heap ds :)

[@nikhil199029]

do we actually need line number 20? if (i!=minH[0])?

[@wellzhang5234]

actually we don't. it will be caught as False anyway in the next group when we can't find a card in hand.

[@mokied]

@@wellzhang5234seem to be working but if you don't delete the key from the counter (like in the solution) I'm not sure it will always give correct answer.

[@MP-ny3ep]

Brilliant explanation. Thank you so much!!!

[@superheroherohero]

Thank you, love your videos, your illustration and explanation are so clear though i'm using Java.

[@nw3052]

The O(1) space solution that I came up with which is slower on leetcode (68ms vs 49ms) than this is we just sort the original hand array, and while its length is > 0 greedily construct groups and remove the used elements from the array.

[@zweitekonto9654]

I also had the same approach. But although slow, its still in the order of n^2, and given the contraints, I wonder how did it pass.

[@nikhilgoyal007]

In theory a middle value can go to 0 if it is a gap between two groups (not in the group but between the grps).

[@nikhilgoyal007]

realized if there is a lower frequency item in the middle, it will not be reached until enough prior ones are removed. so if the middle one 1) is reached and 2) removed, that does mean there will be a hole.

[@stith_pragya]

Thank You So Much for this wonderful video.................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@bchen1403]

I don't think if i != minH[0] is necessary since you do check if i is in count when you go through your expected group. Thanks for the great work! You've been very helpful and generous.

[@markolainovic]

I don't get this - it can happen that i is in count and still not be minH[0]?

[@brajeshjaishwal]

Solution using sorted array (keys of sorted array as a min heap), time complexity to me it is n*n as we have 2 loops, in first loop we are traversing through keys (while loop) and in second loop we are looking up items in for loop (first -> first + groupSize). class Solution: def isNStraightHand(self, hand: List[int], groupSize: int) -> bool: hand.sort() counter = defaultdict(int) if len(hand) % groupSize != 0: ## not possible to divide into groups return False for item in hand: ## keep counter for each element counter[item] += 1 keys = list(counter.keys()) while len(keys): first = keys[0] keyIndex = 0 for item in range(first, first + groupSize): if item not in counter: return False else: counter[item] -= 1 if counter[item] == 0: keys.pop(keyIndex) if keyIndex > 0: return False else: keyIndex += 1 return True

[@hwang1607]

how is this a greedy problem?

[@sauravchandra10]

We can make do with a single map without using min heap. The idea is to iterate over the hash map in a sorted order. The code: class Solution: def isNStraightHand(self, hand: List[int], groupSize: int) -> bool: if len(hand) % groupSize != 0: return False hand.sort() count = OrderedDict() for card in hand: if card not in count: count[card] = 0 count[card] += 1 while len(count)>0: minEl = next(iter(count)) for j in range(minEl, minEl+groupSize): if j not in count: return False count[j] -= 1 if count[j] == 0: del count[j] return True

[@Munchen888]

I won't watch your solution. Only I'am asking. You use a pointer standing on key where hashmap[key] > 0 ?

[@sauravchandra10]

@@Munchen888 yes

[@algorithmo134]

Binary search tree with cameras next!

[@clintondannolfo714]

A few notes: 1. I think the time complexity of this is actually O(n * k) not just O(n log n) since the constraints for the problem say 1

[@markolainovic]

What is k?

[@DavidDLee]

Not sure what k is (maybe len(count.keys()) ?), but I think you are mistaken on both 1 and 2. N is the number of cards and every card in the input reaches count[i] == 0 exactly once, which implies O(n) If you decrement count only for first, then you will not be able to identify holes.

[@pacomarmolejo3492]

I think the TC is correct. In the case hand.length == groupSize, at most we would visit the element in hand just once. Don't get fooled by the loops and hashmap, we are simulating that we are visiting each element in the hand. In case we are about the revisit an element in hand that we have visited before, we return False. This precisely guarantees that we are not revisiting a number more than allowed (reason why it is not O(n*k)) For example, if 2 has a frequency of three, and we are about to visit 2 for the fourth time, we return False, as we have visited 2 the three times we are allowed to.

[@manishvaijanapurkar834]

Would heap work with [1,1,2,2,3,3] gs=3 ?

[@DavidDLee]

Yes

[@Area-fd8ht]

​@@DavidDLeewhere are u from?

[@Richa_cute]

I used vectors and got stuck in that one testcase which will not go error-free whatsoever. So here I am, just didn't want to use map.

[@illu1na]

why is it not nmlogn where m is groupsize? its iterating groupsize for every min value

[@sun-ship]

why the line if i!= minH[0]: return False.... i returned False after the if statement above it and works well...

[@Study2_217]

C++ CODE class Solution { public: bool isNStraightHand(vector& hand, int groupSize) { if(hand.size()%groupSize!=0) return false; unordered_map map; priority_queue pq; for(auto x:hand){ map[x]++; } for(auto p:map){ pq.push(p.first); } while(!pq.empty()) { int first = pq.top(); for(int i=0;i

[@Area-fd8ht]

❤❤❤❤

[@mastermax7777]

using a std::map instead of unordered_map and priority_queue might be simpler

[@Study2_217]

@@mastermax7777 noted

[@ultimophantom8395]

THXX

[@Study2_217]

@@ultimophantom8395 you're welcome!

[@shrn]

instead of using a minHeap, we can use sorting of an array with reverse=True and pop from there since it's still n log n

[@shrn]

from collections import Counter class Solution: def isNStraightHand(self, hand: List[int], groupSize: int) -> bool: if len(hand) % groupSize != 0: return False c = Counter(hand) l = sorted(list(c.keys()), reverse=True) while l: val = l.pop() while val in c and c[val] != 0: c[val] -= 1 for next_val in range(val + 1, val + groupSize): if not next_val in c or c[next_val] == 0: return False c[next_val] -= 1 return True Solution using just sorting

[@ygwg6145]

We can solve it in O(n) time using hash-map. Just to pick up a random element first. Then search m-1 element to find the minimum which is an order one operation step two, make a group and deduct the elements from the hash map. Repeat the above steps until all the elements exhausted. If we cannot exhaust the array, then we can inform the group to return false.

[@killpointx]

nice approach!

[@ancai5498]

Here is the cpp version using std::map(TreeMap): bool isNStraightHand(vector& hand, int groupSize) { if (hand.size() % groupSize != 0) { return false; } map m; for (auto i: hand) { m[i]++; } while (!m.empty()) { int key = m.begin()->first; // least element. for (int i = 0; i < groupSize; i++) { if (!m.count(key + i)) { return false; } else { m[key + i]--; if (m[key + i] == 0) { m.erase(key + i); // remove element if reaches 0. } } } } return true; }

[@jakka30]

Wouldn't removing a value from a min heap be log n, because locating the value in the heap would be log n and restructuring the heap would also be log n as well.

[@Dana-wi1cd]

The heap is not a binary search tree, it's just a binary tree. It holds the biggest/minimum value at every root, and it should be complete. These are the only properties for a heap. To search for a value in a heap, you have to search every single node of a tree.

[@anu1097]

why can't we just keep a variable named minimum. Since we need consecutive elements. If count of minimum is zero then we increment it till count is not zero in hashmap.

[@techmemes3266]

Can someone please explain why this test case returns true: hand: [2,1] groupSize: 2 how can it return true if there's only 2 cards? how can 2 cards form 2 groups of 2?

[@azurereaver]

they don't form 2 groups of 2, they form 1 group of 2, which is valid. no where is the number of straights specified, only 'these are the cards you have' and 'this is how long each straight you make must be'.

[@thirteenyo]

Solved with O(nlogn), but just used sorted(), just like NeetCode said: hand = sorted(hand) while hand: cur = hand[0] hand.remove(cur) for i in range(groupSize): if i == 0: cur += 1 continue if cur not in hand: return False hand.remove(cur) cur += 1 return True

[@jingshiliu7888]

Thank you for sharing you solution and I have a few words about it. hand.remove() is O(n) operation and your solution are doing that for up to N times. That makes your solution O(n^2) rather than O(nlogn). Also, "if cur not in hand" is O(n) and you are doing it up to N times, because python need to iterate through the whole list to see if cur is in hand.

[@tejeshreddy6252]

Love your videos thank you for posting these. I have a question: why is the time complexity O(n*logn) for sorted array? Shouldn't it be O(n/k ** 2)?

[@promethesured]

i think its because sorting itself is nlogn which is the most expensive part. where do you get n / k**2 from?

[@asdfasyakitori8514]

Great video

[@UdayKiran-mw4cr]

The time complexity is O(N*K) .

[@akshatkarnwal4497]

does not it has a complexity of 0(n2) ??

[@ashstories6489]

thanks man

[@raviteja987]

Line 10 doesn’t guarantee a min heap.

[@TRoss-ru6sg]

Line 11 does.

[@sanchitdeepsingh9663]

thanks sir

[@serhiishekenia2749]

I manage to write it with single sort class Solution { public boolean isNStraightHand(int[] hand, int groupSize) { if(hand.length % groupSize != 0) { return false; } Arrays.sort(hand); for(int i = 0; i < hand.length; i++) { if(hand[i] == -1) { continue; } int last = hand[i]; int count = 1; for(int j = i + 1; j < hand.length && count < groupSize; j++) { if(hand[j] == last || hand[j] == -1) { continue; } if(hand[j] - last == 1) { last = hand[j]; hand[j] = -1; count++; } else { break; } } if(count != groupSize) { return false; } } return true; } }

[@houmankamali5617]

Does anyone know how to solve this if we were not allowed to rearrange the numbers in the arrays? e.g. [1,2,3] with group size of 3 would be possible, but [3,2,1] would have not been but [3,2,1,2,3,3,4,4,5] still would pass?

[@jasonthai9647]

6:05 I think the runtime complexity of finding the minimum element in a heap is an O(1) operation not O(logn) operation.

[@AshutoshKumar-es8xy]

No it is logn , when you remove/add an element , the heap calls heapify function to rebalance the ordering of the binary tree.

[@metarus208]

@@AshutoshKumar-es8xy It takes O(log n) time to pop and re-heapify the binary tree. It takes O(1) to peek at the min the element of the MinHeap, which is what Jason was asking.

[@AshutoshKumar-es8xy]

@@metarus208 no he didn't mean that , why would we peek the same min many times. If a peek can take place means that we have already paid logn time.

[@hardikjain-brb]

potd guysssss ; btw map could be easier

[@bluesteel1]

How is this greedy tho ? More apt to classify it as a heap problem no ?

[@bobjenzen8735]

python code for an O(n) solution with O(n) memory complexity. The heap is unecessary numcards = len(hand) freq = defaultdict(int) for card in hand: freq[card] += 1 arr = sorted([x for x in freq]) for i in arr: while freq[i]: for j in range(i, i + groupSize): if freq[j]: freq[j] -= 1 numcards -= 1 else: return False return numcards == 0

[@huberttiddlywinks1445]

arr = sorted([x for x in freq]) is O(n logn)

[@bobjenzen8735]

@@huberttiddlywinks1445 ur right i brainfarted. embarassing

[@joydeepdas8632]

Sorry But I find It to be a low Quality Question...Not the Medium Question Standard I am used to