# 1121. Divide Array Into Increasing Sequences

• Time: $O(n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public: bool canDivideIntoSubsequences(vector& nums, int k) { // Find the number with the maxFreq, we need at least maxFreq * k elements // E.g. nums = [1, 2, 2, 3, 4], we have maxFreq = 2 (two 2s), so we have to // Split nums into two subseqs say k = 3, the minimum length of nums is 2 x // 3 = 6, which is impossible if nums.size() = 5 const int n = nums.size(); int freq = 1; int maxFreq = 1; for (int i = 1; i < n; ++i) { freq = nums[i - 1] < nums[i] ? 1 : ++freq; maxFreq = max(maxFreq, freq); } return n >= maxFreq * k; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public boolean canDivideIntoSubsequences(int[] nums, int k) { // Find the number with the maxFreq, we need at least maxFreq * k elements // E.g. nums = [1, 2, 2, 3, 4], we have maxFreq = 2 (two 2s), so we have to // Split nums into two subseqs say k = 3, the minimum length of nums is 2 x // 3 = 6, which is impossible if nums.size() = 5 final int n = nums.length; int freq = 1; int maxFreq = 1; for (int i = 1; i < n; ++i) { freq = nums[i - 1] < nums[i] ? 1 : ++freq; maxFreq = Math.max(maxFreq, freq); } return n >= maxFreq * k; } } 
 1 2 3 4 5 6 7 class Solution: def canDivideIntoSubsequences(self, nums: List[int], k: int) -> bool: # Find the number with the maxFreq, we need at least maxFreq * k elements # E.g. nums = [1, 2, 2, 3, 4], we have maxFreq = 2 (two 2s), so we have to # Split nums into two subseqs say k = 3, the minimum length of nums is 2 x # 3 = 6, which is impossible if len(nums) = 5 return len(nums) >= k * max(Counter(nums).values())