⚡Flashcard Drill➔
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

  1. If the hand length is not divisible by groupSize, it is impossible.
  2. Count the frequency of each card value with a Counter.
  3. Process values in increasing order; the smallest remaining value must be the start of a group, so consume c copies of c, c+1, ..., c+groupSize-1.
  4. 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 = 2 must 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.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems