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

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

@user-xf1qg7fp8t

8 ай бұрын

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

27 күн бұрын

yea i did the same , its really easy

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

Brilliant explanation. Thank you so much!!!

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

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

nice approach!

Binary search tree with cameras next!

Great video

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

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

2 жыл бұрын

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 hands_count[next_hand] -= 1 next_hand = next_hand + 1 count += 1 if count != groupSize: return False return True

@shalsteven

3 ай бұрын

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

thanks man

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

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

@DavidDLee

Жыл бұрын

Yes

@Area-fd8ht

Жыл бұрын

​@@DavidDLeewhere are u from?

thanks sir

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

7 ай бұрын

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.

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

6 ай бұрын

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

5 ай бұрын

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

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?

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

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

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

2 жыл бұрын

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

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.

how is this a greedy problem?

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

10 ай бұрын

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

@Study2_217

10 ай бұрын

@@mastermax7777 noted

@ultimophantom8395

Ай бұрын

THXX

@Study2_217

Ай бұрын

@@ultimophantom8395 you're welcome!

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.

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

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.

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.

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

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]?

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 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; }

The time complexity is O(N*K) .

Line 10 doesn’t guarantee a min heap.

@TRoss-ru6sg

Жыл бұрын

Line 11 does.

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

potd guysssss ; btw map could be easier

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

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.

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

2 жыл бұрын

Nice! Thanks for sharing.

@madhavappaneni

2 жыл бұрын

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

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

6 ай бұрын

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

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.

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

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

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

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.

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 if(hand[i] == -1) { continue; } int last = hand[i]; int count = 1; for(int j = i + 1; 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; } }

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

9 ай бұрын

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.

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

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.

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

10 ай бұрын

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

@bobjenzen8735

10 ай бұрын

@@huberttiddlywinks1445 ur right i brainfarted. embarassing

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