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 leastk , orfalse 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

  1. Use a min-heap to store the lengths of all current subsequences.
  2. 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.
  3. After processing all numbers, check if all subsequences have length at least k.
  4. Return True if possible, else False.

Code

 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.