Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1121.html

1121. Divide Array Into Increasing Sequences

Level

Hard

Description

Given a non-decreasing array of positive integers nums and an integer K, find out if this array can be divided into one or more disjoint increasing subsequences of length at least K.

Example 1:

Input: nums = [1,2,2,3,3,4,4], K = 3

Output: true

Explanation:

The array can be divided into the 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.

Note:

  1. 1 <= nums.length <= 10^5
  2. 1 <= K <= nums.length
  3. 1 <= nums[i] <= 10^5

Solution

In each increasing subsequence, there are no duplicates. Therefore, if a number occurs more than once, then each occurrence of the number must be in a different increasing subsequence. Since the array is non-decreasing, all elements that are equal are adjacent to each other, the number of occurrences of each element can be counted easily by looping over the array once.

If the maximum occurrence of an element is m, which means the element that occurs most in the array appears for m times, then there are at least m increasing subsequences. If m * K > nums.length, then it is impossible to divide the array into several disjoint increasing subsequences of length at least K, so return false. If m * K <= nums.length, then it is always possible to divide the array into several disjoint increasing subsequences of length at least K, so return true.

  • class Solution {
    public boolean canDivideIntoSubsequences(int[] nums, int K) {
        if (nums == null || nums.length == 0)
            return false;
        int prevNum = nums[0], count = 1;
        int length = nums.length;
        for (int i = 1; i < length; i++) {
            int num = nums[i];
            if (num == prevNum)
                count++;
            else {
                prevNum = num;
                count = 1;
            }
            if (count * K > length)
                return false;
        }
        return true;
    }
}

  • 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;
    }
};

  • 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)


  • 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
}

All Problems

All Solutions