Skip to main content
Talentd

Hand of Straights - Solution & Explanation

MediumArrayHash TableGreedySorting26 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

Alice has some number of cards and she wants to rearrange the cards into groups so that each group is of size groupSize, and consists of groupSize consecutive cards.

Given an integer array hand where hand[i] is the value written on the ith card and an integer groupSize, return true if she can rearrange the cards, or false otherwise.

 

Example 1:

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]

Example 2:

Input: hand = [1,2,3,4,5], groupSize = 4
Output: false
Explanation: Alice's hand can not be rearranged into groups of 4.

 

Constraints:

  • 1 <= hand.length <= 104
  • 0 <= hand[i] <= 109
  • 1 <= groupSize <= hand.length

 

Note: This question is the same as 1296: https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/

Approach Overview

Problem Overview: You receive an array of card values and a group size. The task is to determine whether the cards can be rearranged into groups where each group contains groupSize consecutive integers. Every card must be used exactly once.

Approach 1: Sorting and Greedy (O(n log n) time, O(n) space)

This approach starts by sorting the cards so the smallest available value is always processed first. Maintain a frequency map using a hash table that stores how many times each card appears. Iterate through the sorted array. When you encounter a card that still has remaining count, try to build a consecutive sequence starting from that value: x, x+1, x+2 ... x+groupSize-1. For each number in this range, check the frequency map and decrement counts as cards are used. If any required card is missing, forming valid groups becomes impossible.

The greedy insight is simple: always start sequences from the smallest available card. If you skip it and try to start later, the smaller card could never fit into a valid consecutive group. Sorting guarantees that groups are built in the correct order, while the frequency map ensures constant-time lookups. This method combines sorting with a greedy strategy and works well in interviews because it is easy to reason about and implement.

Approach 2: Using Multiset / Sorted List (O(n log n) time, O(n) space)

A more structured alternative uses a multiset or ordered map (such as multiset in C++ or a balanced tree structure). Insert all cards into the ordered structure so the smallest value can always be retrieved efficiently. Repeatedly take the smallest card and attempt to build a consecutive sequence of length groupSize. For each next value in the sequence, check if it exists in the multiset. If it does, remove one instance; if it doesn't, the grouping fails.

The ordered structure automatically keeps elements sorted, eliminating the need for a separate sort step but still giving O(log n) insertion and deletion. This makes the overall complexity O(n log n). This approach is common in C++ implementations where multiset operations are convenient and expressive.

Recommended for interviews: The sorting + greedy approach is usually the expected answer. It demonstrates clear reasoning about ordering constraints and efficient use of a frequency map. The multiset approach is also valid but slightly heavier due to tree operations. Showing the greedy reasoning—starting from the smallest unused card and forming consecutive sequences—signals strong problem-solving skills.

Approach 1: Approach 1: Sorting and Greedy

We can sort the array first and then use a greedy approach to construct consecutive groups of the given group size:

  • Sort the cards.
  • Use a frequency counter (like a dictionary or hashmap) to track the occurrences of each card.
  • For each card in the sorted order, if the frequency of the card is greater than 0, attempt to form a consecutive sequence starting with this card.
  • Reduce the frequency of each card in the sequence by one.
  • If it is not possible to form such a sequence, return false.
  • If all sequences are formed successfully, return true.

This Python code first uses a Counter to count occurrences of each card. It then attempts to form groups starting from the smallest card available, reducing counts appropriately.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(N log N) due to sorting, where N is the number of cards. Space Complexity: O(N) for storing the counts.

Try this approach in the editor →

Approach 2: Approach 2: Using Multiset/Sorted List

This approach uses a multiset (or similar structure) to represent the occurrence of each card. It uses a similar greedy process as Approach 1 but leverages enhanced data structures for efficient access:

  • Use a data structure that allows you to efficiently find, insert, and delete elements while maintaining sorted order.
  • Iterate over the cards using this structure, forming groups as you go.
  • Use efficient deletion/insertion operations to manage the counts of cards.

This C++ solution uses a map (similar to a multiset here) to maintain count of each card and iterates with greedy logic to form groups by decreasing the count of cards as it goes.

Code

C++C

C++

C

Complexity

Time Complexity: O(N log N) due to map operations. Space Complexity: O(N) for the map to store counts.

Try this approach in the editor →

Approach 3: Hash Table + Sorting

We first check whether the length of the array hand is divisible by groupSize. If it is not, this means that the array cannot be partitioned into multiple subarrays of length groupSize, so we return false.

Next, we use a hash table cnt to count the occurrences of each number in the array hand, and then we sort the array hand.

After that, we iterate over the sorted array hand. For each number x, if cnt[x] neq 0, we enumerate every number y from x to x + groupSize - 1. If cnt[y] = 0, it means that we cannot partition the array into multiple subarrays of length groupSize, so we return false. Otherwise, we decrement cnt[y] by 1.

If the iteration completes successfully, it means that the array can be partitioned into multiple valid subarrays, so we return true.

The time complexity is O(n times log n), and the space complexity is O(n), where n is the length of the array hand.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: Ordered Set

Similar to Solution 1, we first check whether the length of the array hand is divisible by groupSize. If it is not, this means that the array cannot be partitioned into multiple subarrays of length groupSize, so we return false.

Next, we use an ordered set sd to count the occurrences of each number in the array hand.

Then, we repeatedly take the smallest value x from the ordered set and enumerate each number y from x to x + groupSize - 1. If all these numbers appear at least once in the ordered set, we decrement their occurrence count by 1. If any count reaches 0, we remove that number from the ordered set. Otherwise, if we encounter a number that does not exist in the ordered set, it means that the array cannot be partitioned into valid subarrays, so we return false. If the iteration completes successfully, it means that the array can be partitioned into multiple valid subarrays, so we return true.

The time complexity is O(n times log n), and the space complexity is O(n), where n is the length of the array hand.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Sorting and Greedy

Time Complexity: O(N log N) due to sorting, where N is the number of cards. Space Complexity: O(N) for storing the counts.

Approach 2: Using Multiset/Sorted List

Time Complexity: O(N log N) due to map operations. Space Complexity: O(N) for the map to store counts.

Hash Table + Sorting—
Ordered Set—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting + Greedy with Frequency MapO(n log n)O(n)Best general solution; easy to reason about and common in interviews
Multiset / Sorted ListO(n log n)O(n)Useful in languages with built-in ordered sets like C++ multiset

Video Solution

Hand of Straights - Leetcode 846 - Python • NeetCode • 94,364 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Hand of Straights easy or hard?
Hand of Straights is considered a medium difficulty problem. The implementation itself is straightforward once the greedy insight is understood, but recognizing that sequences must start from the smallest unused card requires careful reasoning about ordering and frequency tracking.
How to solve Hand of Straights in O(n)?
A strict O(n) solution is generally not feasible because ordering information is required to build consecutive sequences. Sorting the cards or maintaining a balanced ordered structure is necessary to process numbers in ascending order. As a result, the practical optimal solution runs in O(n log n) time.
What is the best approach for Hand of Straights?
The most common solution uses sorting combined with a greedy strategy and a frequency hash map. After sorting the cards, always start building a group from the smallest unused card and check if the next groupSize consecutive values exist. Each lookup and update is O(1) with the hash map, while sorting dominates the complexity, giving O(n log n) time and O(n) space.
What data structure is used in Hand of Straights?
The typical implementation uses a hash map to store the frequency of each card value and a sorted array to process numbers in increasing order. Some implementations also use ordered structures like C++ multiset or TreeMap to maintain sorted access during removals.
What is the time complexity of Hand of Straights?
The optimal approach runs in O(n log n) time because the cards must be sorted before forming consecutive groups. After sorting, each card is processed at most once while building sequences using a frequency map. The space complexity is O(n) for storing card counts.
Hand of Straights Python or Java solution approach?
In Python or Java, developers usually sort the array and maintain a frequency map using a dictionary or HashMap. For each smallest available card, they attempt to create a consecutive sequence of length groupSize while decrementing counts in the map. This keeps the implementation simple while maintaining O(n log n) time complexity.
Is Hand of Straights asked at Google, Amazon, or Meta?
This problem represents a classic greedy + hash map pattern that appears frequently in interviews at companies like Amazon, Google, and Meta. Variations of grouping consecutive numbers or validating sequences are commonly used to test understanding of sorting, frequency counting, and greedy reasoning.

Ready to solve this problem?

Practice Hand of Straights with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays