Divide array into increasing sequences

Array Counting

65.4% acceptance

Mar 31, 2026

133

Given an integer array nums sorted in non-decreasing order and an integer k, return true if this array can be divided into one or more disjoint increasing subsequences of length at least k, or false otherwise.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn can_divide_into_subsequences(nums: Vec<i32>, k: i32) -> bool {
    // Max frequency of any element * k <= nums.len()
    let mut max_freq = 1;
    let mut cur_freq = 1;
    for i in 1..nums.len() {
      if nums[i] == nums[i - 1] {
        cur_freq += 1;
        if cur_freq > max_freq {
          max_freq = cur_freq;
        }
      } else {
        cur_freq = 1;
      }
    }
    max_freq * k as usize <= nums.len()
  }
}