1296. Divide Array in Sets of K Consecutive Numbers

Given an array of integers nums and a positive integer k, find whether it's possible to divide this array into sets of k consecutive numbers
Return True if it is possible. Otherwise, return False.

 

Example 1:

Input: nums = [1,2,3,3,4,4,5,6], k = 4
Output: true
Explanation: Array can be divided into [1,2,3,4] and [3,4,5,6].

Example 2:

Input: nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3
Output: true
Explanation: Array can be divided into [1,2,3] , [2,3,4] , [3,4,5] and [9,10,11].

Example 3:

Input: nums = [3,3,2,2,1,1], k = 3
Output: true

Example 4:

Input: nums = [1,2,3,4], k = 3
Output: false
Explanation: Each array should be divided in subarrays of size 3.

 

Constraints:

  • 1 <= k <= nums.length <= 105
  • 1 <= nums[i] <= 109

 

Note: This question is the same as 846: https://leetcode.com/problems/hand-of-straights/

Rust Solution

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

impl Solution {
    fn is_possible_divide(nums: Vec<i32>, k: i32) -> bool {
        let n = nums.len();
        let k = k as usize;
        if n % k != 0 {
            return false;
        }
        let mut btm: BTreeMap<i32, usize> = BTreeMap::new();
        for x in nums {
            *btm.entry(x).or_default() += 1;
        }
        let mut queue: VecDeque<(i32, usize)> = VecDeque::new();
        for (val, size) in btm {
            queue.push_back((val, size));
            if queue.len() == k {
                let (first_val, first_size) = queue.pop_front().unwrap();
                for i in 1..k {
                    let (next_val, next_size) = queue.pop_front().unwrap();
                    if next_val != first_val + i as i32 {
                        return false;
                    }
                    if next_size < first_size {
                        return false;
                    }
                    if next_size > first_size {
                        queue.push_back((next_val, next_size - first_size));
                    }
                }
            }
        }
        queue.is_empty()
    }
}

#[test]
fn test() {
    let nums = vec![1, 2, 3, 3, 4, 4, 5, 6];
    let k = 4;
    let res = true;
    assert_eq!(Solution::is_possible_divide(nums, k), res);
    let nums = vec![3, 2, 1, 2, 3, 4, 3, 4, 5, 9, 10, 11];
    let k = 3;
    let res = true;
    assert_eq!(Solution::is_possible_divide(nums, k), res);
    let nums = vec![3, 3, 2, 2, 1, 1];
    let k = 3;
    let res = true;
    assert_eq!(Solution::is_possible_divide(nums, k), res);
    let nums = vec![1, 2, 3, 4];
    let k = 3;
    let res = false;
    assert_eq!(Solution::is_possible_divide(nums, k), res);
}

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