Problem#
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 .
Examples#
Example 1:
1
2
3
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:
1
2
3
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 <= 10^5
1 <= nums[i] <= 10^5
nums
is sorted in non-decreasing order.
Solution#
Method 1 – Greedy with Min-Heap#
Intuition#
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#
Cpp
Go
Java
Kotlin
Python
Rust
Typescript
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public :
bool canDivideIntoSubsequences(vector< int >& nums, int k) {
int max_freq = 1 , cnt = 1 ;
for (int i = 1 ; i < nums.size(); ++ i) {
if (nums[i] == nums[i- 1 ]) cnt++ ;
else cnt = 1 ;
max_freq = max(max_freq, cnt);
}
return nums.size() >= max_freq * k;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func canDivideIntoSubsequences (nums []int , k int ) bool {
maxFreq , cnt := 1 , 1
for i := 1 ; i < len(nums ); i ++ {
if nums [i ] == nums [i - 1 ] {
cnt ++
} else {
cnt = 1
}
if cnt > maxFreq {
maxFreq = cnt
}
}
return len(nums ) >= maxFreq * k
}
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public boolean canDivideIntoSubsequences (int [] nums, int k) {
int maxFreq = 1, cnt = 1;
for (int i = 1; i < nums.length ; ++ i) {
if (nums[ i] == nums[ i- 1] ) cnt++ ;
else cnt = 1;
maxFreq = Math.max (maxFreq, cnt);
}
return nums.length >= maxFreq * k;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
fun canDivideIntoSubsequences (nums: IntArray, k: Int): Boolean {
var maxFreq = 1
var cnt = 1
for (i in 1 until nums.size) {
if (nums[i] == nums[i-1 ]) cnt++
else cnt = 1
maxFreq = maxOf(maxFreq, cnt)
}
return nums.size >= maxFreq * k
}
}
1
2
3
4
5
6
7
8
9
10
class Solution :
def canDivideIntoSubsequences (self, nums: list[int], k: int) -> bool:
max_freq = cnt = 1
for i in range(1 , len(nums)):
if nums[i] == nums[i- 1 ]:
cnt += 1
else :
cnt = 1
max_freq = max(max_freq, cnt)
return len(nums) >= max_freq * k
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
impl Solution {
pub fn can_divide_into_subsequences (nums: Vec< i32 > , k: i32 ) -> bool {
let mut max_freq = 1 ;
let mut cnt = 1 ;
for i in 1 .. nums.len() {
if nums[i] == nums[i- 1 ] {
cnt += 1 ;
} else {
cnt = 1 ;
}
max_freq = max_freq.max(cnt);
}
nums.len() as i32 >= max_freq * k
}
}
1
2
3
4
5
6
7
8
9
10
11
class Solution {
canDivideIntoSubsequences (nums : number [], k : number ): boolean {
let maxFreq = 1 , cnt = 1 ;
for (let i = 1 ; i < nums .length ; ++ i ) {
if (nums [i ] === nums [i - 1 ]) cnt ++ ;
else cnt = 1 ;
maxFreq = Math.max (maxFreq , cnt );
}
return nums .length >= maxFreq * k ;
}
}
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.