Hand of Straights

What I Tried

• The main thing I messed up when solving this problem was that the groupings of the elements had to be contiguous. By doing so, I did not leave room for cases where you could actually reorder the elements.
• So, I didn’t think of that and instead watched the Neetcode video. In the video, the following clicked.
  • You can use a heap as a means to keep track of the starting point for which to increment upwards, and use the frequency map as a means to decrement, removing an element from the hashmap if and only if its counter hits 0.
  • It is not possible to start from a heap element that has a counter of 0, since we remove all such elements from the heap. If that happens, reject. Otherwise, accept.
• Alternatively, you could have sorted and removed elements one by one, which leads to the same runtime.

Runtime

• $O(NlogN)+O(N)+O(N)=O(NlogN)$
  • heapify and building the frequency map costs $O(N)$ each
  • There are $logN$ operations for each element in the frequency map.

Code

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        d = defaultdict(int)
        for card in hand:
            d[card] += 1
        
        heap = list(set(hand))
        heapify(heap)
 
        while heap:
            for i in range(heap[0], heap[0] + groupSize):
                if d[i] == 0:
                    return False
                d[i] -= 1
                if d[i] == 0:
                    heappop(heap)
        
        return True

Notes

---

References

https://leetcode.com/problems/hand-of-straights/