# 1121. Divide Array Into Increasing Sequences

## Description

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.

Example 1:

Input: nums = [1,2,2,3,3,4,4], k = 3
Output: true
Explanation: The array can be divided into 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.


Constraints:

• 1 <= k <= nums.length <= 105
• 1 <= nums[i] <= 105
• nums is sorted in non-decreasing order.

## Solutions

Solution 1: Quick Thinking

We assume that the array can be divided into $m$ strictly increasing subsequences of length at least $k$. If the number of the most frequent number in the array is $cnt$, then these $cnt$ numbers must be in different subsequences, so $m \geq cnt$. Also, since the length of $m$ subsequences is at least $k$, the fewer the number of subsequences, the better, so $m = cnt$. Therefore, $cnt \times k \leq n$ must be satisfied. Hence, we only need to count the number of the most frequent number $cnt$ in the array, and then judge whether $cnt \times k \leq n$. If it is, return true, otherwise return false.

The time complexity is $O(n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the array $nums$.

• class Solution {
public boolean canDivideIntoSubsequences(int[] nums, int k) {
Map<Integer, Integer> cnt = new HashMap<>();
int mx = 0;
for (int x : nums) {
mx = Math.max(mx, cnt.merge(x, 1, Integer::sum));
}
return mx * k <= nums.length;
}
}

• class Solution {
public:
bool canDivideIntoSubsequences(vector<int>& nums, int k) {
int cnt = 0;
int a = 0;
for (int& b : nums) {
cnt = a == b ? cnt + 1 : 1;
if (cnt * k > nums.size()) {
return false;
}
a = b;
}
return true;
}
};

• class Solution:
def canDivideIntoSubsequences(self, nums: List[int], k: int) -> bool:
mx = max(len(list(x)) for _, x in groupby(nums))
return mx * k <= len(nums)


• func canDivideIntoSubsequences(nums []int, k int) bool {
cnt, a := 0, 0
for _, b := range nums {
cnt++
if a != b {
cnt = 1
}
if cnt*k > len(nums) {
return false
}
a = b
}
return true
}