# 846. Hand of Straights solved in rust

## Link

## Problem

The problem is asking to check if the given hand of cards can be arranged into groups of size W. Each group should contain W consecutive cards.

## Example

```
Input: hand = [1,2,3,6,2,3,4,7,8], W = 3
Output: true
Input: hand = [1,2,3,4,5], W = 4
Output: false
```

## Key

The key to solve this problem is to be `greedy`

and allocate each card after sorting to the first empty possible space.

You can achieve a solution of `(O(n * m))`

where `n`

is the number of cards in the hand and `m`

is the count of the groups.

A more efficient solution is use a binary heap to store the groups.

### The algorithm:

- Sort the hand.
- Use a binary heap to store the groups.
- For each card in the hand, try to allocate it to the existing groups.
- If the card can't be allocated to any existing groups, start a new group.
- Check if all the groups in the heap have equal size to the group size.

## Analysis

The time complexity of this solution is `O(nlogn)`

where `n`

is the number of cards in the hand. Which comes from sorting the hand. The space complexity is `O(n)`

where `n`

is the number of cards in the hand. The space complexity comes from the binary heap that stores the groups.

## Solution

```
use std::{cmp::Reverse, collections::BinaryHeap};
pub struct Solution;
impl Solution {
pub fn is_n_straight_hand(hand: Vec<i32>, group_size: i32) -> bool {
let group_size = group_size as usize;
if hand.len() % group_size != 0 {
return false;
}
let mut hand = hand;
hand.sort_unstable(); // (O(nlogn))
// Use a binary heap to store the last card of the group as well as the size
let mut groups_heap: BinaryHeap<Reverse<(i32, usize)>> = BinaryHeap::new();
// Try to allocate all cards to the existing groups
for card in hand {
// Keep a flag to check if the card was assigned to a group
let mut card_allocated = false;
// Look through the existing groups and check if it's possible to assign it to any existing
while let Some(&Reverse((last, size))) = groups_heap.peek() {
// Check if the group size is not full and the next card is a succession of current
if last + 1 == card && size < group_size {
groups_heap.pop();
groups_heap.push(Reverse((card, size + 1)));
card_allocated = true;
break;
} else if size == group_size {
// if the existing group is already allocated we can just pop it
groups_heap.pop();
} else {
break;
}
}
// In case the card was not assigned to any existing groups, start a new group
if !card_allocated {
groups_heap.push(Reverse((card, 1)));
}
}
// In the heap main remain non fully allocated groups
// Check if all the groups in the heap have equal size to the group size
groups_heap
.into_iter()
.all(|Reverse((_, size))| size == group_size as usize)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
let scenarios = vec![
((vec![1, 2, 3, 6, 2, 3, 4, 7, 8], 3), true),
((vec![1, 2, 3, 4, 5], 4), false),
];
scenarios
.into_iter()
.enumerate()
.for_each(|(idx, ((hand, group_size), expected))| {
let result = Solution::is_n_straight_hand(hand, group_size);
assert_eq!(result, expected);
println!(" ✓ scenario {}", idx + 1)
});
}
}
```