Hand of Straights
Medium · Greedy · Array · Hash Table · Greedy · Sorting
Problem
You hold a hand of cards, where hand[i] is the value on the i-th card. You want to split all of the cards into groups of exactly groupSize cards, where each group is made of groupSize consecutive values (a straight).
Return true if such a split is possible, and false otherwise.
Examples
Input: hand = [5,1,2,6,3,7], groupSize = 3 Output: true
The groups are [1,2,3] and [5,6,7].
Input: hand = [1,2,4,5], groupSize = 2 Output: true
The groups are [1,2] and [4,5].
Input: hand = [2,3,3,4,6], groupSize = 5 Output: false
The five cards 2, 3, 3, 4, 6 are not five consecutive values.
Constraints
- 1 <= len(hand) <= 10^4
- 0 <= hand[i] <= 10^9
- 1 <= groupSize <= len(hand)
Approaches
- Baseline: remove straights from a sorted list — time O(n²), space O(n)
Follow-up
What if a group could be any length of at least 3? Then the smallest card still starts a run, but its length is no longer known; prefer extending an existing run. See the use cases for that version, and for groups spaced step apart instead of consecutive.
Related problems
Start free on Cariara · Coding problems · System design studio
