1121. Divide Array Into Increasing Sequences

Given a non-decreasing array of positive integers nums and an integer K, find out if this array can be divided into one or more disjoint increasing subsequences of length at least K.

 

Example 1:

Input: nums = [1,2,2,3,3,4,4], K = 3
Output: true
Explanation: 
The array can be divided into the two subsequences [1,2,3,4] and [2,3,4] with lengths at least 3 each.

Example 2:

Input: nums = [5,6,6,7,8], K = 3
Output: false
Explanation: 
There is no way to divide the array using the conditions required.

 

Note:

  1. 1 <= nums.length <= 10^5
  2. 1 <= K <= nums.length
  3. 1 <= nums[i] <= 10^5

Rust Solution

struct Solution;

impl Solution {
    fn can_divide_into_subsequences(nums: Vec<i32>, k: i32) -> bool {
        let n = nums.len();
        let mut cur = 1;
        let mut groups = 1;
        for i in 1..n {
            if nums[i] == nums[i - 1] {
                cur += 1;
            } else {
                cur = 1;
            }
            groups = groups.max(cur);
        }
        n >= k as usize * groups
    }
}

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

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