Skip to content

1121. Divide Array Into Increasing Sequences πŸ”’

Description

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 <= 105
  • 1 <= nums[i] <= 105
  • nums is sorted in non-decreasing order.

Solutions

Solution 1: Quick Thinking

Thinking

The array is non-decreasing. A strictly increasing subsequence cannot repeat a value, so the most frequent value must occupy distinct subsequences. If it appears \(cnt\) times, at least \(cnt\) subsequences of length at least \(k\) are required, i.e. \(cnt\times k\le n\).

Equal values already form contiguous runs, so groupby yields the longest run without a hash table.

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\).

1
2
3
4
class Solution:
    def canDivideIntoSubsequences(self, nums: List[int], k: int) -> bool:
        mx = max(len(list(x)) for _, x in groupby(nums))
        return mx * k <= len(nums)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    public boolean canDivideIntoSubsequences(int[] nums, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int mx = 0;
        for (int x : nums) {
            mx = Math.max(mx, cnt.merge(x, 1, Integer::sum));
        }
        return mx * k <= nums.length;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    bool canDivideIntoSubsequences(vector<int>& nums, int k) {
        int cnt = 0;
        int a = 0;
        for (int& b : nums) {
            cnt = a == b ? cnt + 1 : 1;
            if (cnt * k > nums.size()) {
                return false;
            }
            a = b;
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func canDivideIntoSubsequences(nums []int, k int) bool {
    cnt, a := 0, 0
    for _, b := range nums {
        cnt++
        if a != b {
            cnt = 1
        }
        if cnt*k > len(nums) {
            return false
        }
        a = b
    }
    return true
}

Solution 2

Thinking

Method 1 computes the global maximum frequency first. Method 2 tracks the current run length and returns false as soon as \(cnt\times k>n\). The criterion is the same; the implementation becomes a single linear scan.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public boolean canDivideIntoSubsequences(int[] nums, int k) {
        int cnt = 0;
        int a = 0;
        for (int b : nums) {
            cnt = a == b ? cnt + 1 : 1;
            if (cnt * k > nums.length) {
                return false;
            }
            a = b;
        }
        return true;
    }
}

Comments