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.Problem Overview: You are given a non-decreasing array nums and an integer k. The task is to check whether you can divide the array into one or more subsequences such that every subsequence is strictly increasing and has length at least k.
Approach 1: Greedy Subsequence Construction (Simulation) (Time: O(n log n), Space: O(n))
A straightforward idea is to simulate building increasing subsequences. Since the array is already sorted, iterate through the elements and try to append each value to an existing subsequence that ends with a smaller value. A common implementation uses a min-heap or priority queue that tracks subsequence lengths and their last values. If the current value equals the last value of some subsequences, you must start new subsequences because duplicates cannot appear in a strictly increasing sequence. After processing all numbers, verify that every constructed subsequence has length at least k. This approach models the problem directly but introduces heap operations, making it O(n log n) time with O(n) extra space.
Approach 2: Counting Insight (Optimal) (Time: O(n), Space: O(1))
The sorted property unlocks a key observation. If a number appears f times, those f copies must belong to different subsequences because duplicates cannot be placed in the same strictly increasing sequence. Therefore, the minimum number of subsequences required is the maximum frequency of any value in the array. Let maxFreq be this value. Each subsequence must have length at least k, so the total number of elements must satisfy n ≥ maxFreq × k. If this condition holds, you can distribute elements across the maxFreq subsequences to maintain increasing order. Computing maxFreq requires a single pass over the array, making the solution O(n) time with constant space.
This reasoning relies on simple frequency counting and the non-decreasing order of the array. You only track runs of equal numbers and update the maximum frequency. No explicit subsequence construction is required.
Related concepts appear frequently in array problems and counting techniques, where identifying structural constraints removes the need for simulation.
Recommended for interviews: The counting insight is what interviewers expect. The greedy simulation demonstrates correct reasoning but wastes time maintaining data structures. Recognizing that duplicates force the minimum number of subsequences leads directly to the n ≥ maxFreq × k condition, giving a clean O(n) solution.
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
| Approach | Complexity |
|---|---|
| Quick Thinking | — |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Subsequence Construction (Heap Simulation) | O(n log n) | O(n) | When demonstrating the direct greedy idea of building subsequences step by step |
| Counting Insight (Max Frequency Rule) | O(n) | O(1) | Best for interviews and production; uses the max frequency constraint to check feasibility instantly |
LeetCode 1121 Divide Array Into Increasing Sequences • leetuition • 614 views views
Watch 7 more video solutions →Practice Divide Array Into Increasing Sequences with our built-in code editor and test cases.
Practice on FleetCode