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 <= 1051 <= nums[i] <= 105nums is sorted in non-decreasing order.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.
Java
C++
Go
| Approach | Complexity |
|---|---|
| Quick Thinking | — |
| Default Approach | — |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,155 views views
Watch 9 more video solutions →Practice Divide Array Into Increasing Sequences with our built-in code editor and test cases.
Practice on FleetCode