What pattern does Hand of Straights use?

The Pattern: Heap / Priority Queue (Greedy Sequential Grouping) The Heuristic: Always process the smallest available element first to greedily form consecutive groups, using a min-heap to efficiently track and update the next candidate for grouping.

Hand of Straights - LeetCode Solution

Q: What is the time complexity of Hand of Straights?

O(n log n). Building the frequency map takes O(n). Heapifying the unique cards takes O(k) where k is the number of unique cards. Each card is pushed and popped at most once, and each group formation involves up to groupSize heap operations, resulting in O(n log n) overall.

Problem

Given an array of integers hand and an integer groupSize, return true if it is possible to rearrange the hand into groups of groupSize consecutive cards, and false otherwise.

1 ≤ hand.length ≤ 10⁴
0 ≤ hand[i] ≤ 10⁹
1 ≤ groupSize ≤ hand.length

Example

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3

Output: true

The hand can be rearranged into groups [1,2,3], [2,3,4], and [6,7,8]. The algorithm first counts the frequency of each card, then uses a min-heap to always start forming groups from the smallest available card. For the first group, it picks 1, then checks for 2 and 3 consecutively, decrementing their counts. It continues this process until all cards are grouped or a consecutive card is missing, in which case it returns false.

Approach

Straightforward Solution

A brute-force approach might try all permutations or attempt to form groups arbitrarily, which is computationally infeasible due to factorial complexity and lack of structure.

Core Observation

The problem requires partitioning the multiset of cards into consecutive groups of fixed size. The fundamental truth is that to form consecutive groups, one must always start from the smallest available card to maintain order and avoid skipping cards that would break consecutiveness.

Path to Optimal

The key recognition signals are 'consecutive groups', 'fixed group size', and 'rearrangement possible'. These indicate a greedy approach combined with a min-heap to always pick the smallest card available. By always forming groups starting from the smallest card, the problem breaks down into a sequence of independent group formations. The min-heap efficiently tracks the smallest card, and the frequency map tracks availability. This approach avoids backtracking and ensures correctness.

Optimal Approach

Count the frequency of each card and build a min-heap of unique cards. While the heap is not empty, pick the smallest card and attempt to form a consecutive group of size groupSize by decrementing counts. If any card in the sequence is missing or out of order, return false. If all cards are grouped successfully, return true. This greedy approach leverages the heap to maintain order and the frequency map to track usage.

Time

O(n log n)

Building the frequency map takes O(n). Heapifying the unique cards takes O(k) where k is the number of unique cards. Each card is pushed and popped at most once, and each group formation involves up to groupSize heap operations, resulting in O(n log n) overall.

Space

O(n)

The frequency map and min-heap store up to n elements in the worst case, which is proportional to the input size. This auxiliary space is necessary to track card counts and ordering.

Solution

1import heapq
2
3class Solution:
  def isNStraightHand(self, hand: list[int], groupSize: int) -> bool:
      if len(hand) % groupSize:
          return False
      
      count = {}
      for n in hand:
          count[n] = 1 + count.get(n, 0)
      
      min_heap = list(count.keys())
      heapq.heapify(min_heap)
14
      while min_heap:
          first = min_heap[0]
          for i in range(first, first + groupSize):
              if i not in count:
                  return False
              count[i] -= 1
              if count[i] == 0:
                  if i != min_heap[0]:
                      return False
                  heapq.heappop(min_heap)
      
      return True

Step-by-Step Solution

1

Validate Hand Length Divisibility by Group Size

5if len(hand) % groupSize:
6    return False

Objective

To quickly reject hands that cannot be evenly divided into groups of the specified size.

Key Insight

If the total number of cards is not divisible by groupSize, it is impossible to partition the hand into equal-sized groups, so the function can return false immediately. This early check prevents unnecessary computation.

Interview Quick-Check

Core Logic

Checking divisibility of hand length by groupSize is a necessary condition for forming equal-sized groups.

Common Pitfalls & Bugs

Forgetting this check can lead to wasted computation on impossible cases.

2

Build Frequency Map of Cards

8count = {}
9for n in hand:
10    count[n] = 1 + count.get(n, 0)
11

Objective

To count the occurrences of each card in the hand for tracking availability during grouping.

Key Insight

A frequency map allows constant-time access to the count of each card, which is essential for decrementing counts as cards are grouped. This data structure transforms the problem from dealing with raw arrays to managing counts, enabling efficient grouping logic.

Interview Quick-Check

Core Logic

The frequency map tracks how many times each card appears, enabling the algorithm to know when a card is exhausted.

Complexity

Building the frequency map takes O(n) time, where n is the number of cards.

3

Initialize Min-Heap with Unique Cards

12min_heap = list(count.keys())
13heapq.heapify(min_heap)

Objective

To maintain the smallest available card at the top for greedy group formation.

Key Insight

Using a min-heap on the unique cards ensures that the algorithm always processes the smallest card first, which is critical for forming consecutive groups in ascending order. Heap operations provide efficient insertion and removal, maintaining order dynamically as cards are exhausted.

Interview Quick-Check

Core Logic

The min-heap allows efficient retrieval and removal of the smallest card, which is the starting point for each group.

Complexity

Heapifying the unique cards takes O(k) time, where k is the number of unique cards.

4

Greedily Form Consecutive Groups Using the Min-Heap

15while min_heap:
  first = min_heap[0]
  for i in range(first, first + groupSize):
      if i not in count:
          return False
      count[i] -= 1
      if count[i] == 0:
          if i != min_heap[0]:
              return False
          heapq.heappop(min_heap)
25

Objective

To iteratively form groups of consecutive cards starting from the smallest available card until all cards are grouped or a failure is detected.

Key Insight

By always starting from the smallest card in the heap, the algorithm ensures groups are formed in ascending order without skipping cards. For each group, it checks for the presence of consecutive cards and decrements their counts. If a card's count reaches zero, it must be the smallest card in the heap to be popped, ensuring no cards are skipped or left ungrouped. Any violation of these conditions means grouping is impossible.

Interview Quick-Check

Core Logic

The algorithm forms groups by decrementing counts of consecutive cards starting from the smallest card, popping cards from the heap only when their count reaches zero and they are at the heap's top.

State & Boundaries

The loop continues until the heap is empty, meaning all cards have been successfully grouped.

Common Pitfalls & Bugs

Failing to check that the card to be popped is at the heap's top can lead to incorrect grouping and missed cards.

Complexity

Each card is pushed and popped at most once, and each group formation involves up to groupSize heap operations, resulting in O(n log n) time.

5

Return True After Successful Grouping

26	`return True`

Objective

To confirm that all cards have been grouped successfully and return true.

Key Insight

If the algorithm completes the while loop without returning false, it means all cards have been partitioned into valid consecutive groups of the specified size. Returning true signals success.

Interview Quick-Check

Core Logic

Returning true after the loop confirms that no grouping violations were found and all cards were used.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 22 Critical

if i != min_heap[0]:

Verify that the exhausted card is at the top of the heap before removal.

This check is critical because popping a card out of order would break the ascending grouping logic, potentially leaving cards ungrouped or causing incorrect groupings.

Line 13 Critical

heapq.heapify(min_heap)

Transform the list of unique cards into a min-heap.

Heapifying the unique cards is critical because it enables O(log n) access to the smallest card, which is necessary for the greedy grouping strategy to maintain ascending order.

Line 16 Critical

first = min_heap[0]

Peek at the smallest card currently available in the heap.

Accessing the smallest card without popping allows the algorithm to verify consecutive cards in order before modifying the heap, preserving correctness.

Line 18 Critical

if i not in count:

Check if the current consecutive card exists in the frequency map.

Detecting a missing card immediately invalidates the grouping, preventing wasted computation and ensuring correctness.

Line 23 Critical

return False

Return false if the exhausted card is not at the heap's top.

This condition detects invalid grouping sequences and prevents incorrect heap modifications.

Line 5 Core

if len(hand) % groupSize:

Check if the hand length is divisible by groupSize.

This is a necessary condition for forming groups of equal size; if not divisible, grouping is impossible and the function returns false immediately.

Line 10 Core

count[n] = 1 + count.get(n, 0)

Increment the count for the current card in the frequency map.

Accurately tracking card counts is critical to know when cards are exhausted during grouping.

Line 17 Core

for i in range(first, first + groupSize):

Iterate over the consecutive cards needed to form a group starting from the smallest card.

This loop attempts to form a group of size groupSize by checking each consecutive card's availability.

Line 19 Core

return False

Return false if a required card is missing.

Early termination upon missing cards ensures the algorithm does not continue futile grouping attempts.

Line 20 Core

count[i] -= 1

Decrement the count of the current card as it is used in the group.

Updating counts reflects card usage, preventing reuse beyond availability.

Line 21 Core

if count[i] == 0:

Check if the current card's count has reached zero after decrementing.

When a card is exhausted, it must be removed from the heap to avoid future processing.

Line 24 Core

heapq.heappop(min_heap)

Remove the exhausted card from the heap.

Popping the card updates the heap state, ensuring only available cards remain for future groups.

Line 6 Core

return False

Return false if hand length is not divisible by groupSize.

Early termination avoids unnecessary computation on impossible inputs, improving efficiency.

Line 8 Core

count = {}

Initialize an empty dictionary to count card frequencies.

The frequency map is essential for tracking how many times each card appears, enabling efficient grouping logic.

Line 15 Core

while min_heap:

Continue processing while there are cards left in the heap.

The loop ensures all cards are grouped or a failure is detected, driving the main grouping logic.

Line 26 Core

return True

Return true after successfully grouping all cards.

Completing the loop without failure means all cards were partitioned into valid consecutive groups, so the function returns true.

Line 12 Standard

min_heap = list(count.keys())

Create a list of unique cards from the frequency map keys.

Extracting unique cards prepares the data structure for heap operations, enabling ordered processing.

Line 9 Standard

for n in hand:

Iterate over each card in the hand.

This loop populates the frequency map by counting occurrences of each card.

Test Your Understanding

Why must the algorithm always start forming groups from the smallest available card in the min-heap?

Starting from the smallest card ensures that groups are formed in ascending order without skipping any cards, which guarantees that all cards can be partitioned into consecutive sequences. Skipping smaller cards could leave them ungrouped or break the consecutiveness requirement.

Don't just read it. Drill it.

Reconstruct Hand of Straights from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Hand of Straights drill

or drill a free problem

1	`import heapq`
2
3	`class Solution:`
4	`def isNStraightHand(self, hand: list[int], groupSize: int) -> bool:`
5	`if len(hand) % groupSize:`
6	`return False`
7
8	`count = {}`
9	`for n in hand:`
10	`count[n] = 1 + count.get(n, 0)`
11
12	`min_heap = list(count.keys())`
13	`heapq.heapify(min_heap)`
14
15	`while min_heap:`
16	`first = min_heap[0]`
17	`for i in range(first, first + groupSize):`
18	`if i not in count:`
19	`return False`
20	`count[i] -= 1`
21	`if count[i] == 0:`
22	`if i != min_heap[0]:`
23	`return False`
24	`heapq.heappop(min_heap)`
25
26	`return True`

8	`count = {}`
9	`for n in hand:`
10	`count[n] = 1 + count.get(n, 0)`
11

Problem

Example

Approach

Solution

Step-by-Step Solution

Validate Hand Length Divisibility by Group Size

Build Frequency Map of Cards

Initialize Min-Heap with Unique Cards

Greedily Form Consecutive Groups Using the Min-Heap

Return True After Successful Grouping

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.