846. Hand of Straights solved in rust

Link

846. Hand of Straights

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:

1. Sort the hand.
2. Use a binary heap to store the groups.
3. For each card in the hand, try to allocate it to the existing groups.
4. If the card can't be allocated to any existing groups, start a new group.
5. 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)
            });
    }
}