Hand of Straights
Hand of Straights is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Greedy Patterns pattern, in the Sorting Based subpattern.
Problem statement
You are given hand, where each integer represents one card value, and groupSize, the required number of cards in each group. Partition every card in hand into groups of exactly groupSize cards.
A group is valid only when its card values are consecutive integers, with no gaps. Cards with the same value are distinct occurrences, so duplicate values may be used in different groups. Return true if such a partition is possible; otherwise, return false.
The order of cards in hand does not matter, and every card must belong to exactly one group.
Example 1:
Input: hand = [11,12,13,21,22,23], groupSize = 3 Output: true Explanation: The cards can be partitioned into [11, 12, 13] and [21, 22, 23], two groups of three consecutive values.
Example 2:
Input: hand = [14,15,17,18,19,20], groupSize = 3 Output: false Explanation: Although the hand has six cards, the smallest possible group would require 16 after 14 and 15, but no such card is available.
Example 3:
Input: hand = [20,21,22,23,21,22,23,24], groupSize = 4 Output: true Explanation: One valid partition is [20, 21, 22, 23] and [21, 22, 23, 24].
Constraints:
- 1 <= hand.length <= 10^4 - 0 <= hand[i] <= 10^9 - 1 <= groupSize <= hand.length - All values in hand are integers
Topics and companies
Topics: Array, Greedy, Hash Table, Sorting.
How to practise Hand of Straights on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n log n), where n is hand.size(). time and O(n) for the ordered frequency map. space.
Open Hand of Straights in the code editor, or read the Hand of Straights editorial for a worked solution with its approach and complexity analysis.
Where Hand of Straights sits in the DSA pattern sheet
- Greedy Patterns pattern guide
- Sorting Based subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Hand of Straights
Other problems that use the same Sorting Based and Greedy Patterns techniques:
- Assign Cookies — Easy, same subpattern
- Candy — Hard, same subpattern
- Lemonade Change — Easy, same subpattern
- Merge Triplets to Form Target Triplet — Medium, same subpattern
- Queue Reconstruction by Height — Medium, same subpattern
- Sort an Array — Medium, same subpattern