Divide Array Into Increasing Sequences
Can we partition a sorted array into ≥k-length strictly increasing subsequences? Max frequency check.
Problem#
Given a non-decreasing integer array nums and integer k, determine whether nums can be partitioned into one or more strictly increasing subsequences each of length at least k.
Examples#
nums = [1,2,2,3,3,4,4], k = 3→true(e.g.,[1,2,3,4]and[2,3,4]).nums = [5,6,6,7,8], k = 3→false.
Constraints#
1 <= nums.length <= 10^5,numssorted,1 <= k <= nums.length.
Hints#
Hint
maxFreq * k <= n. Approach#
Since the array is sorted, equal elements must go into distinct subsequences (each subsequence is strictly increasing). So the number of subsequences needed is at least maxFreq. Each subsequence has length at least k, so we need maxFreq * k <= n.
Solution#
class Solution {public: bool canDivideIntoSubsequences(vector<int>& nums, int k) { int n = nums.size(); int maxFreq = 1, cur = 1; for (int i = 1; i < n; ++i) { cur = (nums[i] == nums[i - 1]) ? cur + 1 : 1; maxFreq = max(maxFreq, cur); } return static_cast<long long>(maxFreq) * k <= n; }};func canDivideIntoSubsequences(nums []int, k int) bool { n := len(nums) maxFreq, cur := 1, 1 for i := 1; i < n; i++ { if nums[i] == nums[i-1] { cur++ } else { cur = 1 } if cur > maxFreq { maxFreq = cur } } return int64(maxFreq)*int64(k) <= int64(n)}from typing import List
class Solution: def canDivideIntoSubsequences(self, nums: List[int], k: int) -> bool: n = len(nums) max_freq = 1 cur = 1 for i in range(1, n): if nums[i] == nums[i - 1]: cur += 1 else: cur = 1 if cur > max_freq: max_freq = cur return max_freq * k <= nvar canDivideIntoSubsequences = function(nums, k) { const n = nums.length; let maxFreq = 1, cur = 1; for (let i = 1; i < n; i++) { cur = nums[i] === nums[i - 1] ? cur + 1 : 1; if (cur > maxFreq) maxFreq = cur; } return maxFreq * k <= n;};class Solution { public boolean canDivideIntoSubsequences(int[] nums, int k) { int n = nums.length; int maxFreq = 1, cur = 1; for (int i = 1; i < n; i++) { cur = (nums[i] == nums[i - 1]) ? cur + 1 : 1; if (cur > maxFreq) maxFreq = cur; } return (long) maxFreq * k <= n; }}function canDivideIntoSubsequences(nums: number[], k: number): boolean { const n = nums.length; let maxFreq = 1, cur = 1; for (let i = 1; i < n; i++) { cur = nums[i] === nums[i - 1] ? cur + 1 : 1; if (cur > maxFreq) maxFreq = cur; } return maxFreq * k <= n;}Editorial#
Each occurrence of the most-frequent value must seed its own subsequence (no two equal values can sit in the same strictly increasing chain). With sortedness, runs of equal values are contiguous, so maxFreq is a one-pass scan. Sufficiency: given maxFreq chains and n elements, distributing them round-robin produces chains of length at least floor(n / maxFreq) >= k.
Complexity#
- Time: O(N).
- Space: O(1).
Concept revision#
Related#