Divide Array Into Increasing Sequences

hard array counting hash map

Problem

Given a sorted (non-decreasing) array nums and an integer k, decide whether nums can be partitioned into one or more disjoint strictly increasing subsequences, each of length at least k. Return true if such a partition exists.

Inputnums = [1, 2, 2, 3, 3, 4, 4], k = 3

Outputtrue

The most frequent value appears 2 times, so we need 2 subsequences. With 7 elements, 2 × 3 = 6 ≤ 7, so it fits: e.g. [1,2,3,4] and [2,3,4].

nums (sorted, comma-separated)

def can_divide_into_subsequences(nums, k):
    n = len(nums)
    max_freq = 1
    cur = 1
    for i in range(1, n):
        if nums[i] == nums[i - 1]:
            cur += 1
            max_freq = max(max_freq, cur)
        else:
            cur = 1
    return max_freq * k <= n

function canDivideIntoSubsequences(nums, k) {
  const n = nums.length;
  let maxFreq = 1, cur = 1;
  for (let i = 1; i < n; i++) {
    if (nums[i] === nums[i - 1]) {
      cur++;
      maxFreq = Math.max(maxFreq, cur);
    } else {
      cur = 1;
    }
  }
  return maxFreq * k <= n;
}

class Solution {
    public boolean canDivideIntoSubsequences(int[] nums, int k) {
        int n = nums.length;
        int maxFreq = 1, cur = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] == nums[i - 1]) {
                cur++;
                maxFreq = Math.max(maxFreq, cur);
            } else {
                cur = 1;
            }
        }
        return (long) maxFreq * k <= n;
    }
}

bool canDivideIntoSubsequences(vector<int>& nums, int k) {
    int n = (int)nums.size();
    int maxFreq = 1, cur = 1;
    for (int i = 1; i < n; i++) {
        if (nums[i] == nums[i - 1]) {
            cur++;
            maxFreq = max(maxFreq, cur);
        } else {
            cur = 1;
        }
    }
    return (long long)maxFreq * k <= n;
}

Explanation

This looks like it needs complicated bookkeeping, but it collapses to a single number: the count of the most frequent value. Find that, and you instantly know the answer.

Here is the key insight. Each subsequence must be strictly increasing, so no subsequence can contain the same value twice. If some value appears maxFreq times, those copies must land in maxFreq different subsequences. So we need at least maxFreq subsequences, and every one must have length at least k.

That means we need room for maxFreq × k elements. If the array has n elements and maxFreq * k <= n, a valid split always exists; otherwise it cannot. Because the array is already sorted, equal values sit next to each other, so we find maxFreq by scanning once and tracking the longest run of equal neighbors.

Example: nums = [1, 2, 2, 3, 3, 4, 4], k = 3. The most frequent value appears 2 times, so maxFreq = 2. We need 2 × 3 = 6 elements and we have 7, so 6 <= 7 is true.

One valid arrangement is [1,2,3,4] and [2,3,4]. The check never builds those lists; it just confirms there is enough space.

Time: O(n) Space: O(1)