Since the array is sorted, we can greedily build the minimum number of increasing subsequences by always extending the shortest available subsequence. We use a min-heap to track the lengths of all current subsequences. For each number, we try to extend the shortest subsequence; if not possible, we start a new one. At the end, all subsequences must have length at least k.

Approach

Use a min-heap to store the lengths of all current subsequences.
For each number in nums:
- If the heap size is less than the count of the current number, start new subsequences for the extra occurrences.
- Otherwise, extend the shortest available subsequences.
After processing all numbers, check if all subsequences have length at least k.
Return True if possible, else False.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    bool canDivideIntoSubsequences(vector<int>& nums, int k) {\n        int max_freq = 1, cnt = 1;\n        for (int i = 1; i < nums.size(); ++i) {\n            if (nums[i] == nums[i-1]) cnt++;\n            else cnt = 1;\n            max_freq = max(max_freq, cnt);\n        }\n        return nums.size() >= max_freq * k;\n    }\n};","lang":"cpp"},{"language":"Go","code":"func canDivideIntoSubsequences(nums []int, k int) bool {\n    maxFreq, cnt := 1, 1\n    for i := 1; i < len(nums); i++ {\n        if nums[i] == nums[i-1] {\n            cnt++\n        } else {\n            cnt = 1\n        }\n        if cnt > maxFreq {\n            maxFreq = cnt\n        }\n    }\n    return len(nums) >= maxFreq*k\n}","lang":"go"},{"language":"Java","code":"class Solution {\n    public boolean canDivideIntoSubsequences(int[] nums, int k) {\n        int maxFreq = 1, cnt = 1;\n        for (int i = 1; i < nums.length; ++i) {\n            if (nums[i] == nums[i-1]) cnt++;\n            else cnt = 1;\n            maxFreq = Math.max(maxFreq, cnt);\n        }\n        return nums.length >= maxFreq * k;\n    }\n}","lang":"java"},{"language":"Kotlin","code":"class Solution {\n    fun canDivideIntoSubsequences(nums: IntArray, k: Int): Boolean {\n        var maxFreq = 1\n        var cnt = 1\n        for (i in 1 until nums.size) {\n            if (nums[i] == nums[i-1]) cnt++\n            else cnt = 1\n            maxFreq = maxOf(maxFreq, cnt)\n        }\n        return nums.size >= maxFreq * k\n    }\n}","lang":"kotlin"},{"language":"Python","code":"class Solution:\n    def canDivideIntoSubsequences(self, nums: list[int], k: int) -> bool:\n        max_freq = cnt = 1\n        for i in range(1, len(nums)):\n            if nums[i] == nums[i-1]:\n                cnt += 1\n            else:\n                cnt = 1\n            max_freq = max(max_freq, cnt)\n        return len(nums) >= max_freq * k","lang":"python"},{"language":"Rust","code":"impl Solution {\n    pub fn can_divide_into_subsequences(nums: Vec<i32>, k: i32) -> bool {\n        let mut max_freq = 1;\n        let mut cnt = 1;\n        for i in 1..nums.len() {\n            if nums[i] == nums[i-1] {\n                cnt += 1;\n            } else {\n                cnt = 1;\n            }\n            max_freq = max_freq.max(cnt);\n        }\n        nums.len() as i32 >= max_freq * k\n    }\n}","lang":"rust"},{"language":"TypeScript","code":"class Solution {\n    canDivideIntoSubsequences(nums: number[], k: number): boolean {\n        let maxFreq = 1, cnt = 1;\n        for (let i = 1; i < nums.length; ++i) {\n            if (nums[i] === nums[i-1]) cnt++;\n            else cnt = 1;\n            maxFreq = Math.max(maxFreq, cnt);\n        }\n        return nums.length >= maxFreq * k;\n    }\n}","lang":"typescript"}]

Complexity

⏰ Time complexity: O(n), where n is the length of nums. We scan the array once.
🧺 Space complexity: O(1), only a constant amount of extra space is used.

8:[

Related Tags