846. Hand of Straights

Alice has a hand of cards, given as an array of integers.

Now she wants to rearrange the cards into groups so that each group is size W, and consists of W consecutive cards.

Return true if and only if she can.

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

 

Example 1:

Input: hand = [1,2,3,6,2,3,4,7,8], W = 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], W = 4
Output: false
Explanation: Alice's hand can't be rearranged into groups of 4.

 

Constraints:

  • 1 <= hand.length <= 10000
  • 0 <= hand[i] <= 10^9
  • 1 <= W <= hand.length

Rust Solution

struct Solution;
use std::collections::BTreeMap;
use std::collections::VecDeque;
use std::iter::FromIterator;

impl Solution {
    fn is_n_straight_hand(hand: Vec<i32>, w: i32) -> bool {
        let mut btm: BTreeMap<i32, usize> = BTreeMap::new();
        for card in hand {
            *btm.entry(card).or_default() += 1;
        }
        let w = w as usize;
        let mut queue: VecDeque<(i32, usize)> = VecDeque::from_iter(btm);
        while !queue.is_empty() {
            let first = queue.pop_front().unwrap();
            let mut stack: Vec<(i32, usize)> = vec![];
            for i in 1..w {
                if let Some(front) = queue.pop_front() {
                    if front.0 != first.0 + i as i32 || front.1 < first.1 {
                        return false;
                    } else {
                        let left = front.1 - first.1;
                        if left > 0 {
                            stack.push((front.0, left));
                        }
                    }
                } else {
                    return false;
                }
            }
            while let Some(last) = stack.pop() {
                queue.push_front(last);
            }
        }
        true
    }
}

#[test]
fn test() {
    let hand = vec![1, 2, 3, 6, 2, 3, 4, 7, 8];
    let w = 3;
    let res = true;
    assert_eq!(Solution::is_n_straight_hand(hand, w), res);
    let hand = vec![1, 2, 3, 4, 5];
    let w = 4;
    let res = false;
    assert_eq!(Solution::is_n_straight_hand(hand, w), res);
    let hand = vec![5, 1];
    let w = 2;
    let res = false;
    assert_eq!(Solution::is_n_straight_hand(hand, w), res);
}

Having problems with this solution? Click here to submit an issue on github.