Hand of Straights

Explanation & Solution

Description

Given an array of integers hand where hand[i] is the value of the i-th card, and an integer groupSize, return true if and only if the hand can be rearranged into groups of groupSize consecutive cards.

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

Output: true

Explanation: The hand can be rearranged as [1,2,3], [2,3,4], [6,7,8].

Constraints

1 <= hand.length <= 10^4
0 <= hand[i] <= 10^9
1 <= groupSize <= hand.length

Approach

Greedy Techniques pattern

1. Quick Length Check

If hand.length is not divisible by groupSize, it is impossible to form complete groups — return false immediately

2. Sort the Hand

Sort the array in ascending order so we can always try to build groups starting from the smallest available card

3. Count Card Frequencies

Build a Map that stores the count of each card value
This allows O(1) lookup and decrement when forming groups

4. Greedily Form Groups

Iterate through the sorted hand
For each card that still has a remaining count (count > 0), attempt to form a group of groupSize consecutive cards starting from that card
For each value card, card+1, card+2, ..., card+groupSize-1, check that its count is greater than 0
If any value in the sequence is missing, return false
Otherwise, decrement each value's count by 1

5. All Groups Formed

If we successfully process every card without running into a missing consecutive value, return true

Key Insight

Sorting and always starting from the smallest unused card ensures we never skip a card that must begin a group — if a card is the smallest remaining, it must be the start of some group
Time complexity is O(n log n) due to sorting, plus O(n * groupSize) for group formation, giving overall O(n log n) when groupSize is small relative to n

Solution Code

Maximum Subarray

Queue Reconstruction by Height