NeetCode #784LC-846MediumGreedyNC 150NC 250
← Back to All Problems#784 · #846 · Hand of Straights(一手顺子)
📌 Problem Statement & Constraints
Alice has a hand of cards
hand and wants to rearrange them into groups of groupSize consecutive cards. Return true if she can. Constraints: 1 <= hand.length <= 10^4, 0 <= hand[i] <= 10^9, 1 <= groupSize <= hand.length.💡 Core Algorithmic Approaches
- If the hand length is not divisible by
groupSize, it is impossible. - Count the frequency of each card value with a
Counter. - Process values in increasing order; the smallest remaining value must be the start of a group, so consume
ccopies ofc, c+1, ..., c+groupSize-1. - If any needed value is short, return false. Starting from the smallest remaining value is forced, which makes the greedy exact.
💻 Benchmark Python3 Implementation
class Solution:
def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
from collections import Counter
if len(hand) % groupSize:
return False
cnt = Counter(hand)
for x in sorted(cnt):
c = cnt[x]
if c == 0:
continue
for y in range(x, x + groupSize):
if cnt[y] < c:
return False
cnt[y] -= c # consume c groups starting at x
return True⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n): sorting the distinct values dominates.
💾 Space Complexity
O(n): the frequency map.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting the divisibility check: e.g.
hand = [1,2,3],groupSize = 2must return false. - Decrementing by 1 instead of by
c: the smallest value may appear several times, forcing several groups to start there. - Iterating over the dict while mutating it: iterate over a sorted snapshot of the keys instead.
- Using a set of seen values: duplicates matter, so a frequency map is required.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.