LeetCode 1121 - Divide Array Into Increasing Sequences

The problem asks us to determine if a sorted integer array nums can be divided into one or more disjoint increasing subsequences, where each subsequence has a length of at least k.

leetcodehardarraycounting

LeetCode Problem 1121

Difficulty: 🔴 Hard
Topics: Array, Counting

Solution

Problem Understanding

The problem asks us to determine if a sorted integer array nums can be divided into one or more disjoint increasing subsequences, where each subsequence has a length of at least k. The array is sorted in non-decreasing order, which means duplicates are allowed and elements do not decrease as we move from left to right. The output is a boolean: true if such a division is possible, false otherwise.

In other words, we need to group all elements in the array into sequences that strictly increase in value or allow repeated values to continue the sequence, with each sequence containing at least k elements. The input constraints are quite large: up to 10^5 elements in the array, and values also up to 10^5. This suggests that any brute-force solution attempting all possible subsequences would be infeasible.

Important edge cases include arrays where all elements are the same, arrays shorter than k, and arrays with gaps in the numbers that prevent forming sequences of length k.

Approaches

A brute-force approach would attempt to generate all possible subsequences of length at least k and check whether a valid partition exists. This method is clearly exponential in time complexity because the number of subsequences grows combinatorially with the array length. While this approach is correct in principle, it is too slow for the problem constraints.

The key insight for an optimal solution is to recognize that the frequency of each number constrains how we can form sequences. Because the array is sorted, we can process numbers in order and attempt to append each number to an existing sequence or start a new sequence. The critical observation is that if at any point the number of sequences that need to be extended exceeds the count of the current number, it is impossible to form valid sequences. We can leverage a frequency map to count occurrences and a greedy approach to manage ongoing sequences.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Generates all possible subsequences and checks validity, infeasible for large n
Optimal O(n) O(n) Uses frequency counting and greedy assignment to extend or start sequences

Algorithm Walkthrough

  1. Count the frequency of each number in nums using a hash map. This gives the total number of times each value is available for sequences.
  2. Maintain a hash map for the number of subsequences ending at a particular number. This helps us track ongoing sequences that require the next consecutive number to continue.
  3. Iterate through each unique number in the array in ascending order. For each number, determine how many sequences need it to extend.
  4. If the frequency of the current number is less than the number of sequences that require it, return false. This means some sequences cannot reach the required length.
  5. Otherwise, extend existing sequences first and use any remaining occurrences to start new sequences of length at least k. Keep track of these new sequences.
  6. After processing all numbers, if all sequences satisfy the minimum length requirement, return true.

The greedy approach works because extending existing sequences first ensures we do not leave small sequences stranded, and starting new sequences with leftover elements guarantees all elements are used optimally.

Python Solution

from collections import Counter, defaultdict
from typing import List

class Solution:
    def canDivideIntoSubsequences(self, nums: List[int], k: int) -> bool:
        freq = Counter(nums)
        end_count = defaultdict(int)

        for num in sorted(freq):
            if freq[num] < end_count[num]:
                return False  # Not enough nums to extend all sequences
            
            leftover = freq[num] - end_count[num]
            if leftover > 0:
                for i in range(1, k):
                    if freq[num + i] < leftover:
                        return False
                    freq[num + i] -= leftover
                end_count[num + k - 1] += leftover
        
        return True

In this implementation, we first count how many times each number appears. end_count tracks how many sequences currently need this number as the next element. For each number, if there are leftover elements after extending sequences, we attempt to create new sequences of length k and decrement the frequency of subsequent numbers accordingly. If at any point there are not enough numbers to form new sequences, we return false.

Go Solution

package main

func canDivideIntoSubsequences(nums []int, k int) bool {
    freq := make(map[int]int)
    endCount := make(map[int]int)

    for _, num := range nums {
        freq[num]++
    }

    uniqueNums := make([]int, 0, len(freq))
    for num := range freq {
        uniqueNums = append(uniqueNums, num)
    }
    sort.Ints(uniqueNums)

    for _, num := range uniqueNums {
        if freq[num] < endCount[num] {
            return false
        }

        leftover := freq[num] - endCount[num]
        if leftover > 0 {
            for i := 1; i < k; i++ {
                if freq[num+i] < leftover {
                    return false
                }
                freq[num+i] -= leftover
            }
            endCount[num+k-1] += leftover
        }
    }
    return true
}

In Go, we explicitly build a slice of unique numbers and sort it to process them in order. Maps handle frequency counting and tracking sequences. Go requires careful management of map default values, but otherwise the logic mirrors the Python version.

Worked Examples

Example 1: nums = [1,2,2,3,3,4,4], k = 3

num freq end_count leftover Notes
1 1 0 1 Start new sequence 1-2-3
2 2 0 2 Extend sequence from 1, start another 2-3-4
3 2 1 1 Extend sequences, leftover starts a new sequence
4 2 1 1 Extend sequences, leftover completes sequences

All sequences satisfy k ≥ 3, return true.

Example 2: nums = [5,6,6,7,8], k = 3

num freq end_count leftover Notes
5 1 0 1 Start new sequence 5-6-7
6 2 0 2 Cannot extend 2 sequences, 1 left over fails

Return false.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Iterate through nums once and manage frequency/end_count maps, sorting unique numbers is O(n) in worst case
Space O(n) Store frequency and end_count maps for all numbers

The complexity is linear because each number is processed once, and extending sequences involves constant-time operations for each number. Space scales with the number of unique numbers.

Test Cases

# Provided examples
assert Solution().canDivideIntoSubsequences([1,2,2,3,3,4,4], 3) == True  # Example 1
assert Solution().canDivideIntoSubsequences([5,6,6,7,8], 3) == False      # Example 2

# Edge and boundary cases
assert Solution().canDivideIntoSubsequences([1,1,1,1], 2) == True          # All identical elements, can form 2 sequences
assert Solution().canDivideIntoSubsequences([1,2,3,4], 5) == False         # Array shorter than k
assert Solution().canDivideIntoSubsequences([1], 1) == True                # Single element, k=1
assert Solution().canDivideIntoSubsequences([1,2,3,4,5,6], 2) == True      # Continuous increasing numbers
assert Solution().canDivideIntoSubsequences([1,1,2,2,3,3,4,4], 4) == True  # Multiple sequences of length exactly k
Test Why
[1,2,2,3,3,4,4], 3 Valid division into increasing subsequences
[5,6,6,7,8], 3 Impossible due to insufficient numbers to extend sequences
[1,1,1,1], 2 Handling identical elements correctly
[1,2,3,4], 5 Array shorter than k, cannot form any valid sequence
[1], 1 Minimum input, trivial valid case
[1,2,3,4,5,6], 2 Continuous numbers, multiple sequences possible
[1,1,2,2,3,3,4,4], 4 Exact-length sequences possible

Edge Cases

One important edge case is when the array length is less than k. In this scenario, no valid subsequence can exist, and the algorithm correctly returns false immediately as the loop cannot satisfy k.

Another edge case occurs when all elements are identical. Here, the algorithm must correctly determine if these repeated numbers can form sequences of length at least k. The implementation handles this using the leftover calculation, ensuring sequences start only when sufficient numbers exist.

A third edge case is when gaps exist