Solution: Divide Array Into Increasing Sequences

Let’s solve the Divide Array Into Increasing Sequences using the Knowing What to Track pattern.

We'll cover the following

Statement

Given a sorted integer array, nums, in non-decreasing order and an integer, k, determine whether it is possible to partition the array into one or more disjoint increasing subsequences, each having a length of at least k. Return true if such a partition exists; otherwise, return false.

Constraints:

  • 1≤1 \leq k ≤\leq nums.length≤103\leq 10^3

  • 1≤1 \leq nums[i] ≤103\leq 10^3

  • The nums array is sorted in non-decreasing order.

Solution

The essence of this solution lies in determining whether the array has enough elements to accommodate the most frequently occurring number across multiple subsequences of at least length k. If the array doesn’t contain any duplicates, the entire array can form an increasing subsequence. Otherwise, duplicate numbers appear consecutively as the array is sorted, allowing us to track their frequency and record the maximum frequency. For a valid division, the total number of elements in nums must be at least k * maxFreq. This is because once we ensure the most frequent number can be evenly distributed across subsequences of at least length k, the remaining numbers will naturally fit into the sequences without issue.

Using the intuition above, we implement the algorithm as follows:

  1. Initialize a variable, currFreq, to track the count of consecutive occurrences of the same number.

  2. Initialize another variable, maxFreq, to store the maximum frequency of any element, i.e., the highest count of any repeated element in nums.

  3. Iterate through nums, starting from the second element:

    1. If the current element is equal to the previous one (nums[i - 1] ==== nums[i]), increment currFreq to count consecutive occurrences of the same number.

    2. Otherwise, reset currFreq to 1, indicating a new number starts.

    3. Update maxFreq to store the maximum count of any repeating number found so far.

  4. Return TRUE if the total number of elements in nums is at least k * maxFreq; otherwise, return FALSE.

Let’s look at the following illustration to get a better understanding of the solution:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.