Divide Array Into Increasing Sequences - Practice Coding Problems

Divide Array Into Increasing Sequences - Problem

Array Counting Hard

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.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. Two subsequences are disjoint if they do not share any elements.

An increasing subsequence means each element is strictly greater than the previous one.

Input & Output

Example 1 — Valid Partition

$ Input: nums = [1,2,3,3,4,5], k = 3

› Output: true

💡 Note: Array can be divided into [1,2,4] and [3,5], but [3,5] has length 2 < 3. However, we can form [1,3,4] and [2,5], which still fails. Actually, we can form one sequence [1,2,3,4,5] of length 5 ≥ 3.

Example 2 — Too Small Array

$ Input: nums = [1,2], k = 3

› Output: false

💡 Note: Array length is 2, but we need subsequences of length at least 3, so it's impossible.

Example 3 — Frequency Too High

$ Input: nums = [1,1,1,2], k = 2

› Output: false

💡 Note: Number 1 appears 3 times, but with k=2, we can have at most ⌈4/2⌉ = 2 occurrences of any number.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁵ ≤ nums[i] ≤ 10⁵
nums is sorted in non-decreasing order
1 ≤ k ≤ nums.length

Visualization

Tap to expand

Understanding the Visualization

Input

Sorted array and minimum subsequence length k

Process

Count frequencies and validate partitioning constraints

Output

True if valid partition exists, false otherwise

Key Takeaway

🎯 Key Insight: Use frequency counting to check if any element appears too often, then verify with greedy subsequence building

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that if any number appears more than ⌈n/k⌉ times, partitioning is impossible. Best approach uses frequency counting with greedy validation. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Count with Validation	O(n)	O(n)	Count occurrences of each number and check if valid partitioning is possible
Brute Force Backtracking	O(2^n)	O(n)	Try all possible ways to partition the array into increasing subsequences

Frequency Count with Validation — Algorithm Steps

Count frequency of each element
Check if max frequency ≤ ⌈n/k⌉
Use greedy allocation to verify

Visualization

Tap to expand

Step-by-Step Walkthrough

Count

Count frequency of each number

Validate

Check if max frequency ≤ ⌈n/k⌉

Verify

Use greedy approach to build sequences

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

bool solution(int* nums, int numsSize, int k) {
    if (numsSize < k) return false;
    
    // Count frequencies using sorted array
    qsort(nums, numsSize, sizeof(int), compare);
    
    int uniqueNums[1000];
    int freq[1000];
    int uniqueCount = 0;
    
    int i = 0;
    while (i < numsSize) {
        int current = nums[i];
        int count = 0;
        while (i < numsSize && nums[i] == current) {
            count++;
            i++;
        }
        uniqueNums[uniqueCount] = current;
        freq[uniqueCount] = count;
        uniqueCount++;
    }
    
    // Check if any number appears too frequently
    int maxAllowedFreq = (numsSize + k - 1) / k;
    for (i = 0; i < uniqueCount; i++) {
        if (freq[i] > maxAllowedFreq) {
            return false;
        }
    }
    
    // Greedy verification
    int available[1000];
    for (i = 0; i < uniqueCount; i++) {
        available[i] = freq[i];
    }
    
    while (true) {
        int totalRemaining = 0;
        for (i = 0; i < uniqueCount; i++) {
            totalRemaining += available[i];
        }
        if (totalRemaining == 0) break;
        
        int currentSeqSize = 0;
        int lastNum = -1000000;
        for (i = 0; i < uniqueCount; i++) {
            if (available[i] > 0 && uniqueNums[i] > lastNum) {
                lastNum = uniqueNums[i];
                available[i]--;
                currentSeqSize++;
                if (currentSeqSize >= k) {
                    break;
                }
            }
        }
        
        if (currentSeqSize < k) {
            return false;
        }
    }
    
    return true;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* ptr = strchr(line, '[') + 1;
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    bool result = solution(nums, numsSize, k);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to count frequencies and validate

✓ Linear Growth

Space Complexity

O(n)

Hash map to store frequency counts

⚡ Linearithmic Space

15.6K Views

Medium Frequency

~25 min Avg. Time

423 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Frequency Count with Validation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler