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.

Description Solution Video 15:54

846. Hand of Straights

Medium58.5% acceptance6 companies

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 i^th 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 <= 10⁴
0 <= hand[i] <= 10⁹
1 <= groupSize <= hand.length

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

Asked at 6 companies

Visa

Google Amazon Microsoft Meta Bloomberg

Topics

15:54

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,2,3,6,2,3,4,7,8]
3

Input

[1,2,3,4,5]
4

Your code is saved on this device.Solution