Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1121.html
1121. Divide Array Into Increasing Sequences
Level
Hard
Description
Given a nondecreasing 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 <= nums.length <= 10^5
1 <= K <= nums.length
1 <= nums[i] <= 10^5
Solution
In each increasing subsequence, there are no duplicates. Therefore, if a number occurs more than once, then each occurrence of the number must be in a different increasing subsequence. Since the array is nondecreasing, all elements that are equal are adjacent to each other, the number of occurrences of each element can be counted easily by looping over the array once.
If the maximum occurrence of an element is m
, which means the element that occurs most in the array appears for m
times, then there are at least m
increasing subsequences. If m * K > nums.length
, then it is impossible to divide the array into several disjoint increasing subsequences of length at least K
, so return false
. If m * K <= nums.length
, then it is always possible to divide the array into several disjoint increasing subsequences of length at least K
, so return true
.

class Solution { public boolean canDivideIntoSubsequences(int[] nums, int K) { if (nums == null  nums.length == 0) return false; int prevNum = nums[0], count = 1; int length = nums.length; for (int i = 1; i < length; i++) { int num = nums[i]; if (num == prevNum) count++; else { prevNum = num; count = 1; } if (count * K > length) return false; } return true; } }

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 }