Hand of Straights solution and explanation
Google
9 more videos on this problem
Hand of Straights - Leetcode 846 - PythonNeetCode · 15:54 · 94K views
Hand of Straights | Simple Thought Process | Google | Leetcode 846 | codestorywithMIKcodestorywithMIK · 18:32 · 24K views
LeetCode 846. Hand of Straights (Algorithm Explained)Nick White · 9:50 · 18K views
LeetCode Hand of Straights Explained - JavaNick White · 6:58 · 13K views
846. Hand of Straights | 1296. Divide Array in Sets of K Consecutive Numbers | Sorting | MapAryan Mittal · 20:41 · 8K views
Leetcode 846 | Hand of Straights | PriorityQueue (Solution with Detailed Explanation, Sort and Pick)The Tech Granth · 9:19 · 5K views
846. Hand of Straights | Leetcode POTD 6 June 2024 | Java | Heap | Striver's A to Z DSA SheetAlgorithmHQ · 18:51 · 4K views
Hand Of Straights | #LeetCode 846 | Detail Explanation | C++ /JavaThe FinTech Club · 9:07 · 4K views
846. Hand of Straights | string manipulation | leetcode daily challenge | DSA | HindiShashCode · 26:03 · 3K views
846. Hand of Straights Leetcode Editorial 🚀 | Problem of the Day Leetcode Solution | Abhinav AwasthiAbhinav Awasthi · 21:21 · 1K views
The problem
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 <= 1040 <= hand[i] <= 1091 <= 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.
from collections import Counter
def isPossibleDivide(hand, groupSize):
if len(hand) % groupSize != 0:
return False
hand_count = Counter(hand)
for card in sorted(hand_count):
if hand_count[card] > 0:
for i in range(groupSize):
if hand_count[card + i] < hand_count[card]:
return False
hand_count[card + i] -= hand_count[card]
return Trueimport java.util.*;
public class HandOfStraights {
public boolean isPossibleDivide(int[] hand, int groupSize) {
if (hand.length % groupSize != 0) return false;
Map<Integer, Integer> count = new HashMap<>();
for (int card : hand) {
count.put(card, count.getOrDefault(card, 0) + 1);
}
PriorityQueue<Integer> minHeap = new PriorityQueue<>(count.keySet());
while (!minHeap.isEmpty()) {
int first = minHeap.poll();
for (int i = 0; i < groupSize; i++) {
if (count.getOrDefault(first + i, 0) == 0) return false;
count.put(first + i, count.get(first + i) - 1);
if (count.get(first + i) == 0) {
count.remove(first + i);
}
}
}
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.
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: 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.
#include <vector>
#include <map>
using namespace std;
class Solution {
public:
bool isPossibleDivide(vector<int>& hand, int groupSize) {
map<int, int> count;
for (int card : hand) {
count[card]++;
}
for (auto it = count.begin(); it != count.end(); ++it) {
int card = it->first;
int freq = it->second;
if (freq > 0) {
for (int i = 0; i < groupSize; i++) {
if (count[card + i] < freq) return false;
count[card + i] -= freq;
}
}
}
return true;
}
};#include <stdio.h>
#include <stdlib.h>
int cmpfunc(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
int isPossibleDivide(int* hand, int handSize, int groupSize) {
if (handSize % groupSize != 0) return 0;
qsort(hand, handSize, sizeof(int), cmpfunc);
int* count = (int*)calloc(handSize, sizeof(int));
for (int i = 0; i < handSize; i++) {
count[hand[i]]++;
}
for (int i = 0; i < handSize; i++) {
if (count[hand[i]] > 0) {
for (int j = 0; j < groupSize; j++) {
if (count[hand[i] + j] < count[hand[i]]) {
free(count);
return 0;
}
count[hand[i] + j] -= count[hand[i]];
}
}
}
free(count);
return 1;
}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.
Time Complexity: O(N log N) due to map operations. Space Complexity: O(N) for the map to store counts.
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.
function isNStraightHand(hand: number[], groupSize: number): boolean {
if (hand.length % groupSize !== 0) {
return false;
}
const cnt = new Map<number, number>();
for (const x of hand) {
cnt.set(x, (cnt.get(x) || 0) + 1);
}
hand.sort((a, b) => a - b);
for (const x of hand) {
if (cnt.get(x)! > 0) {
for (let y = x; y < x + groupSize; y++) {
if ((cnt.get(y) || 0) === 0) {
return false;
}
cnt.set(y, cnt.get(y)! - 1);
}
}
}
return true;
}func isNStraightHand(hand []int, groupSize int) bool {
if len(hand)%groupSize != 0 {
return false
}
sort.Ints(hand)
cnt := map[int]int{}
for _, x := range hand {
cnt[x]++
}
for _, x := range hand {
if cnt[x] > 0 {
for y := x; y < x+groupSize; y++ {
if cnt[y] == 0 {
return false
}
cnt[y]--
}
}
}
return true
}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.
function isNStraightHand(hand: number[], groupSize: number): boolean {
if (hand.length % groupSize !== 0) {
return false;
}
const tm = new TreeMap<number, number>();
for (const x of hand) {
tm.set(x, (tm.get(x) || 0) + 1);
}
while (tm.size()) {
const x = tm.first()![0];
for (let y = x; y < x + groupSize; ++y) {
if (!tm.has(y)) {
return false;
}
if (tm.get(y)! === 1) {
tm.delete(y);
} else {
tm.set(y, tm.get(y)! - 1);
}
}
}
return true;
}
type Compare<T> = (lhs: T, rhs: T) => number;
class RBTreeNode<T = number> {
data: T;
count: number;
left: RBTreeNode<T> | null;
right: RBTreeNode<T> | null;
parent: RBTreeNode<T> | null;
color: number;
constructor(data: T) {
this.data = data;
this.left = this.right = this.parent = null;
this.color = 0;
this.count = 1;
}
sibling(): RBTreeNode<T> | null {
if (!this.parent) return null; // sibling null if no parent
return this.isOnLeft() ? this.parent.right : this.parent.left;
}
isOnLeft(): boolean {
return this === this.parent!.left;
}
hasRedChild(): boolean {
return (
Boolean(this.left && this.left.color === 0) ||
Boolean(this.right && this.right.color === 0)
);
}
}
class RBTree<T> {
root: RBTreeNode<T> | null;
lt: (l: T, r: T) => boolean;
constructor(compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0)) {
this.root = null;
this.lt = (l: T, r: T) => compare(l, r) < 0;
}
rotateLeft(pt: RBTreeNode<T>): void {
const right = pt.right!;
pt.right = right.left;
if (pt.right) pt.right.parent = pt;
right.parent = pt.parent;
if (!pt.parent) this.root = right;
else if (pt === pt.parent.left) pt.parent.left = right;
else pt.parent.right = right;
right.left = pt;
pt.parent = right;
}
rotateRight(pt: RBTreeNode<T>): void {
const left = pt.left!;
pt.left = left.right;
if (pt.left) pt.left.parent = pt;
left.parent = pt.parent;
if (!pt.parent) this.root = left;
else if (pt === pt.parent.left) pt.parent.left = left;
else pt.parent.right = left;
left.right = pt;
pt.parent = left;
}
swapColor(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
const tmp = p1.color;
p1.color = p2.color;
p2.color = tmp;
}
swapData(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
const tmp = p1.data;
p1.data = p2.data;
p2.data = tmp;
}
fixAfterInsert(pt: RBTreeNode<T>): void {
let parent = null;
let grandParent = null;
while (pt !== this.root && pt.color !== 1 && pt.parent?.color === 0) {
parent = pt.parent;
grandParent = pt.parent.parent;
/* Case : A
Parent of pt is left child of Grand-parent of pt */
if (parent === grandParent?.left) {
const uncle = grandParent.right;
/* Case : 1
The uncle of pt is also red
Only Recoloring required */
if (uncle && uncle.color === 0) {
grandParent.color = 0;
parent.color = 1;
uncle.color = 1;
pt = grandParent;
} else {
/* Case : 2
pt is right child of its parent
Left-rotation required */
if (pt === parent.right) {
this.rotateLeft(parent);
pt = parent;
parent = pt.parent;
}
/* Case : 3
pt is left child of its parent
Right-rotation required */
this.rotateRight(grandParent);
this.swapColor(parent!, grandParent);
pt = parent!;
}
} else {
/* Case : B
Parent of pt is right child of Grand-parent of pt */
const uncle = grandParent!.left;
/* Case : 1
The uncle of pt is also red
Only Recoloring required */
if (uncle != null && uncle.color === 0) {
grandParent!.color = 0;
parent.color = 1;
uncle.color = 1;
pt = grandParent!;
} else {
/* Case : 2
pt is left child of its parent
Right-rotation required */
if (pt === parent.left) {
this.rotateRight(parent);
pt = parent;
parent = pt.parent;
}
/* Case : 3
pt is right child of its parent
Left-rotation required */
this.rotateLeft(grandParent!);
this.swapColor(parent!, grandParent!);
pt = parent!;
}
}
}
this.root!.color = 1;
}
delete(val: T): boolean {
const node = this.find(val);
if (!node) return false;
node.count--;
if (!node.count) this.deleteNode(node);
return true;
}
deleteAll(val: T): boolean {
const node = this.find(val);
if (!node) return false;
this.deleteNode(node);
return true;
}
deleteNode(v: RBTreeNode<T>): void {
const u = BSTreplace(v);
// True when u and v are both black
const uvBlack = (u === null || u.color === 1) && v.color === 1;
const parent = v.parent!;
if (!u) {
// u is null therefore v is leaf
if (v === this.root) this.root = null;
// v is root, making root null
else {
if (uvBlack) {
// u and v both black
// v is leaf, fix double black at v
this.fixDoubleBlack(v);
} else {
// u or v is red
if (v.sibling()) {
// sibling is not null, make it red"
v.sibling()!.color = 0;
}
}
// delete v from the tree
if (v.isOnLeft()) parent.left = null;
else parent.right = null;
}
return;
}
if (!v.left || !v.right) {
// v has 1 child
if (v === this.root) {
// v is root, assign the value of u to v, and delete u
v.data = u.data;
v.left = v.right = null;
} else {
// Detach v from tree and move u up
if (v.isOnLeft()) parent.left = u;
else parent.right = u;
u.parent = parent;
if (uvBlack) this.fixDoubleBlack(u);
// u and v both black, fix double black at u
else u.color = 1; // u or v red, color u black
}
return;
}
// v has 2 children, swap data with successor and recurse
this.swapData(u, v);
this.deleteNode(u);
// find node that replaces a deleted node in BST
function BSTreplace(x: RBTreeNode<T>): RBTreeNode<T> | null {
// when node have 2 children
if (x.left && x.right) return successor(x.right);
// when leaf
if (!x.left && !x.right) return null;
// when single child
return x.left ?? x.right;
}
// find node that do not have a left child
// in the subtree of the given node
function successor(x: RBTreeNode<T>): RBTreeNode<T> {
let temp = x;
while (temp.left) temp = temp.left;
return temp;
}
}
fixDoubleBlack(x: RBTreeNode<T>): void {
if (x === this.root) return; // Reached root
const sibling = x.sibling();
const parent = x.parent!;
if (!sibling) {
// No sibiling, double black pushed up
this.fixDoubleBlack(parent);
} else {
if (sibling.color === 0) {
// Sibling red
parent.color = 0;
sibling.color = 1;
if (sibling.isOnLeft()) this.rotateRight(parent);
// left case
else this.rotateLeft(parent); // right case
this.fixDoubleBlack(x);
} else {
// Sibling black
if (sibling.hasRedChild()) {
// at least 1 red children
if (sibling.left && sibling.left.color === 0) {
if (sibling.isOnLeft()) {
// left left
sibling.left.color = sibling.color;
sibling.color = parent.color;
this.rotateRight(parent);
} else {
// right left
sibling.left.color = parent.color;
this.rotateRight(sibling);
this.rotateLeft(parent);
}
} else {
if (sibling.isOnLeft()) {
// left right
sibling.right!.color = parent.color;
this.rotateLeft(sibling);
this.rotateRight(parent);
} else {
// right right
sibling.right!.color = sibling.color;
sibling.color = parent.color;
this.rotateLeft(parent);
}
}
parent.color = 1;
} else {
// 2 black children
sibling.color = 0;
if (parent.color === 1) this.fixDoubleBlack(parent);
else parent.color = 1;
}
}
}
}
insert(data: T): boolean {
// search for a position to insert
let parent = this.root;
while (parent) {
if (this.lt(data, parent.data)) {
if (!parent.left) break;
else parent = parent.left;
} else if (this.lt(parent.data, data)) {
if (!parent.right) break;
else parent = parent.right;
} else break;
}
// insert node into parent
const node = new RBTreeNode(data);
if (!parent) this.root = node;
else if (this.lt(node.data, parent.data)) parent.left = node;
else if (this.lt(parent.data, node.data)) parent.right = node;
else {
parent.count++;
return false;
}
node.parent = parent;
this.fixAfterInsert(node);
return true;
}
search(predicate: (val: T) => boolean, direction: 'left' | 'right'): T | undefined {
let p = this.root;
let result = null;
while (p) {
if (predicate(p.data)) {
result = p;
p = p[direction];
} else {
p = p[direction === 'left' ? 'right' : 'left'];
}
}
return result?.data;
}
find(data: T): RBTreeNode<T> | null {
let p = this.root;
while (p) {
if (this.lt(data, p.data)) {
p = p.left;
} else if (this.lt(p.data, data)) {
p = p.right;
} else break;
}
return p ?? null;
}
count(data: T): number {
const node = this.find(data);
return node ? node.count : 0;
}
*inOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
if (!root) return;
for (const v of this.inOrder(root.left!)) yield v;
yield root.data;
for (const v of this.inOrder(root.right!)) yield v;
}
*reverseInOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
if (!root) return;
for (const v of this.reverseInOrder(root.right!)) yield v;
yield root.data;
for (const v of this.reverseInOrder(root.left!)) yield v;
}
}
class TreeMap<K = number, V = unknown> {
_size: number;
tree: RBTree<K>;
map: Map<K, V> = new Map();
compare: Compare<K>;
constructor(
collection: Array<[K, V]> | Compare<K> = [],
compare: Compare<K> = (l: K, r: K) => (l < r ? -1 : l > r ? 1 : 0),
) {
if (typeof collection === 'function') {
compare = collection;
collection = [];
}
this._size = 0;
this.compare = compare;
this.tree = new RBTree(compare);
for (const [key, val] of collection) this.set(key, val);
}
size(): number {
return this._size;
}
has(key: K): boolean {
return !!this.tree.find(key);
}
get(key: K): V | undefined {
return this.map.get(key);
}
set(key: K, val: V): boolean {
const successful = this.tree.insert(key);
this._size += successful ? 1 : 0;
this.map.set(key, val);
return successful;
}
delete(key: K): boolean {
const deleted = this.tree.deleteAll(key);
this._size -= deleted ? 1 : 0;
return deleted;
}
ceil(target: K): [K, V] | undefined {
return this.toKeyValue(this.tree.search(key => this.compare(key, target) >= 0, 'left'));
}
floor(target: K): [K, V] | undefined {
return this.toKeyValue(this.tree.search(key => this.compare(key, target) <= 0, 'right'));
}
higher(target: K): [K, V] | undefined {
return this.toKeyValue(this.tree.search(key => this.compare(key, target) > 0, 'left'));
}
lower(target: K): [K, V] | undefined {
return this.toKeyValue(this.tree.search(key => this.compare(key, target) < 0, 'right'));
}
first(): [K, V] | undefined {
return this.toKeyValue(this.tree.inOrder().next().value);
}
last(): [K, V] | undefined {
return this.toKeyValue(this.tree.reverseInOrder().next().value);
}
shift(): [K, V] | undefined {
const first = this.first();
if (first === undefined) return undefined;
this.delete(first[0]);
return first;
}
pop(): [K, V] | undefined {
const last = this.last();
if (last === undefined) return undefined;
this.delete(last[0]);
return last;
}
toKeyValue(key: K): [K, V];
toKeyValue(key: undefined): undefined;
toKeyValue(key: K | undefined): [K, V] | undefined;
toKeyValue(key: K | undefined): [K, V] | undefined {
return key != null ? [key, this.map.get(key)!] : undefined;
}
*[Symbol.iterator](): Generator<[K, V], void, void> {
for (const key of this.keys()) yield this.toKeyValue(key);
}
*keys(): Generator<K, void, void> {
for (const key of this.tree.inOrder()) yield key;
}
*values(): Generator<V, undefined, void> {
for (const key of this.keys()) yield this.map.get(key)!;
return undefined;
}
*rkeys(): Generator<K, undefined, void> {
for (const key of this.tree.reverseInOrder()) yield key;
return undefined;
}
*rvalues(): Generator<V, undefined, void> {
for (const key of this.rkeys()) yield this.map.get(key)!;
return undefined;
}
}func isNStraightHand(hand []int, groupSize int) bool {
if len(hand)%groupSize != 0 {
return false
}
tm := treemap.NewWithIntComparator()
for _, x := range hand {
if v, ok := tm.Get(x); ok {
tm.Put(x, v.(int)+1)
} else {
tm.Put(x, 1)
}
}
for !tm.Empty() {
x, _ := tm.Min()
for y := x.(int); y < x.(int)+groupSize; y++ {
if v, ok := tm.Get(y); ok {
if v.(int) == 1 {
tm.Remove(y)
} else {
tm.Put(y, v.(int)-1)
}
} else {
return false
}
}
}
return true
}Complexity comparison
| Approach | Complexity |
|---|---|
| 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 | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting + Greedy with Frequency Map | O(n log n) | O(n) | Best general solution; easy to reason about and common in interviews |
| Multiset / Sorted List | O(n log n) | O(n) | Useful in languages with built-in ordered sets like C++ multiset |
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.