Hand of Straights - Leetcode 846 - Python

  Рет қаралды 61,252

NeetCode

NeetCode

Күн бұрын

Пікірлер: 89
@victoriac7257
@victoriac7257 3 жыл бұрын
Yours is almost the most clear one. your channel deserve more likes!
@skepat9426
@skepat9426 2 жыл бұрын
Better if we sort the keys of the hmap O(nlogn) and then iterate over the sorted keys, much easier.
@학교-m5c
@학교-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
@VijenderSingh-wr6fm 7 ай бұрын
yea i did the same , its really easy
@RandomShowerThoughts
@RandomShowerThoughts 4 ай бұрын
did that as well initially, however, you need to ensure that you delete the values
@wellzhang5234
@wellzhang5234 3 ай бұрын
@@학교-m5c how can you make sure it's ordered?
@swaroopacharjee2767
@swaroopacharjee2767 2 жыл бұрын
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
@abdullahioladosu6385 2 жыл бұрын
Nice! Thanks for sharing.
@madhavappaneni
@madhavappaneni 2 жыл бұрын
Good start but this solution takes O(n^2) time
@superheroherohero
@superheroherohero 2 жыл бұрын
Thank you, love your videos, your illustration and explanation are so clear though i'm using Java.
@RandomShowerThoughts
@RandomShowerThoughts 4 ай бұрын
let's go, I was able to get the intuition myself!
@BishalECE-uy5rn
@BishalECE-uy5rn 2 жыл бұрын
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
@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
@tianzejiang7669 11 ай бұрын
agree, and that part confused me a lot until I removed it
@stith_pragya
@stith_pragya 9 ай бұрын
Thank You So Much for this wonderful video.................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
@MP-ny3ep
@MP-ny3ep 8 ай бұрын
Brilliant explanation. Thank you so much!!!
@rogerchou7762
@rogerchou7762 2 жыл бұрын
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
@AshutoshKumar-es8xy 2 жыл бұрын
No it takes logn for one pop
@DavidDLee
@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
@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
@shalsteven 9 ай бұрын
​@@tunepa4418time complexity O(n logn) for sorting + O(n) for looping?
@nikhil199029
@nikhil199029 9 ай бұрын
do we actually need line number 20? if (i!=minH[0])?
@wellzhang5234
@wellzhang5234 3 ай бұрын
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
@mokied 3 ай бұрын
@@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.
@chaitanya812
@chaitanya812 Жыл бұрын
instead of min heap why don't we use ordered_map in that we won't need any heap ds :)
@nikhilgoyal007
@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
@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.
@nw3052
@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
@zweitekonto9654 8 ай бұрын
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.
@brajeshjaishwal
@brajeshjaishwal 3 ай бұрын
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
@bobfish2636
@bobfish2636 3 жыл бұрын
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
@karimmohamed5355 7 ай бұрын
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.
@sauravchandra10
@sauravchandra10 8 ай бұрын
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
@Munchen888 8 ай бұрын
I won't watch your solution. Only I'am asking. You use a pointer standing on key where hashmap[key] > 0 ?
@sauravchandra10
@sauravchandra10 8 ай бұрын
@@Munchen888 yes
@illu1na
@illu1na Жыл бұрын
why is it not nmlogn where m is groupsize? its iterating groupsize for every min value
@bchen1403
@bchen1403 2 жыл бұрын
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
@markolainovic 2 жыл бұрын
I don't get this - it can happen that i is in count and still not be minH[0]?
@killpointx
@killpointx 8 ай бұрын
nice approach!
@manishvaijanapurkar834
@manishvaijanapurkar834 2 жыл бұрын
Would heap work with [1,1,2,2,3,3] gs=3 ?
@DavidDLee
@DavidDLee Жыл бұрын
Yes
@Area-fd8ht
@Area-fd8ht Жыл бұрын
​@@DavidDLeewhere are u from?
@algorithmo134
@algorithmo134 3 жыл бұрын
Binary search tree with cameras next!
@asdfasyakitori8514
@asdfasyakitori8514 Жыл бұрын
Great video
@thirteenyo
@thirteenyo 2 жыл бұрын
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
@jingshiliu7888 2 жыл бұрын
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.
@Study2_217
@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
@Area-fd8ht Жыл бұрын
❤❤❤❤
@mastermax7777
@mastermax7777 Жыл бұрын
using a std::map instead of unordered_map and priority_queue might be simpler
@Study2_217
@Study2_217 Жыл бұрын
@@mastermax7777 noted
@ultimophantom8395
@ultimophantom8395 8 ай бұрын
THXX
@Study2_217
@Study2_217 8 ай бұрын
@@ultimophantom8395 you're welcome!
@Richa_cute
@Richa_cute 8 ай бұрын
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.
@clintondannolfo714
@clintondannolfo714 2 жыл бұрын
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
@markolainovic 2 жыл бұрын
What is k?
@DavidDLee
@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
@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.
@jasonthai9647
@jasonthai9647 2 жыл бұрын
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
@AshutoshKumar-es8xy 2 жыл бұрын
No it is logn , when you remove/add an element , the heap calls heapify function to rebalance the ordering of the binary tree.
@metarus208
@metarus208 2 жыл бұрын
@@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
@AshutoshKumar-es8xy 2 жыл бұрын
@@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.
@ashstories6489
@ashstories6489 Жыл бұрын
thanks man
@sanchitdeepsingh9663
@sanchitdeepsingh9663 10 ай бұрын
thanks sir
@shrn
@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
@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
@sun-ship
@sun-ship 10 ай бұрын
why the line if i!= minH[0]: return False.... i returned False after the if statement above it and works well...
@ancai5498
@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; }
@tejeshreddy6252
@tejeshreddy6252 2 жыл бұрын
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
@promethesured 2 жыл бұрын
i think its because sorting itself is nlogn which is the most expensive part. where do you get n / k**2 from?
@anu1097
@anu1097 7 ай бұрын
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.
@hwang1607
@hwang1607 10 ай бұрын
how is this a greedy problem?
@techmemes3266
@techmemes3266 2 жыл бұрын
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
@azurereaver 2 жыл бұрын
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'.
@ygwg6145
@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.
@jakka30
@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
@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.
@akshatkarnwal4497
@akshatkarnwal4497 7 ай бұрын
does not it has a complexity of 0(n2) ??
@raviteja987
@raviteja987 2 жыл бұрын
Line 10 doesn’t guarantee a min heap.
@TRoss-ru6sg
@TRoss-ru6sg 2 жыл бұрын
Line 11 does.
@UdayKiran-mw4cr
@UdayKiran-mw4cr 9 ай бұрын
The time complexity is O(N*K) .
@houmankamali5617
@houmankamali5617 2 жыл бұрын
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?
@serhiishekenia2749
@serhiishekenia2749 9 ай бұрын
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; } }
@BetterCallHardik
@BetterCallHardik 8 ай бұрын
potd guysssss ; btw map could be easier
@bluesteel1
@bluesteel1 Жыл бұрын
How is this greedy tho ? More apt to classify it as a heap problem no ?
@bobjenzen8735
@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
@huberttiddlywinks1445 Жыл бұрын
arr = sorted([x for x in freq]) is O(n logn)
@bobjenzen8735
@bobjenzen8735 Жыл бұрын
@@huberttiddlywinks1445 ur right i brainfarted. embarassing
@joydeepdas8632
@joydeepdas8632 9 ай бұрын
Sorry But I find It to be a low Quality Question...Not the Medium Question Standard I am used to
70% of Programmers can't solve this LeetCode Easy Question
7:32
Chain Game Strong ⛓️
00:21
Anwar Jibawi
Рет қаралды 41 МЛН
AI Is Making You An Illiterate Programmer
27:22
ThePrimeTime
Рет қаралды 250 М.
Design Twitter - Leetcode 355 - Python
22:47
NeetCode
Рет қаралды 98 М.
Partition Labels - Leetcode 763 - Python
14:29
NeetCode
Рет қаралды 46 М.
Longest Repeating Character Replacement - Leetcode 424 - Python
20:44
LRU Cache - Twitch Interview Question - Leetcode 146
17:49
NeetCode
Рет қаралды 327 М.
Chain Game Strong ⛓️
00:21
Anwar Jibawi
Рет қаралды 41 МЛН