Split Array into Consecutive Subsequences

Split Array into Consecutive Subsequences - Problem

You are given an integer array nums that is sorted in non-decreasing order. Determine if it is possible to split nums into one or more subsequences such that both of the following conditions are true:

Each subsequence is a consecutive increasing sequence (i.e. each integer is exactly one more than the previous integer).
All subsequences have a length of 3 or more.

Return true if you can split nums according to the above conditions, or false otherwise.

A subsequence of an array is a new array that is formed from the original array by deleting some (can be none) of the elements without disturbing the relative positions of the remaining elements.

Input & Output

Example 1 — Basic Case

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

› Output: true

💡 Note: Can split into [1,2,3] and [3,4,5], both consecutive sequences of length ≥ 3

Example 2 — Cannot Split

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

› Output: true

💡 Note: Can split into [1,2,3] and [3,4,5] and [4,5] - wait, [4,5] has length 2, so actually can split into [1,2,3,4,5] and [3,4,5]

Example 3 — Impossible Case

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

› Output: false

💡 Note: Cannot form valid consecutive subsequences - one 4 would be left alone or in length-2 sequence

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Sorted array [1,2,3,3,4,5]

Process

Use greedy strategy to form consecutive sequences

Output

Return true if all elements can be grouped into valid sequences

Key Takeaway

🎯 Key Insight: Always extend existing subsequences before starting new ones to minimize waste

Asked in

G Google 15 F Facebook 12 A Amazon 8 M Microsoft 6

The key insight is to use a greedy approach with two hash maps: one tracks available numbers, the other tracks subsequence tails. Always prefer extending existing sequences over starting new ones. Best approach is Greedy: Time O(n), Space O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Two-Pass Frequency Count	O(n²)	O(n)	Count frequencies first, then greedily build consecutive sequences
Brute Force - Try All Combinations	O(2^n)	O(n)	Try every possible way to split the array into consecutive subsequences
Greedy with Two Hash Maps	O(n)	O(n)	Track available numbers and subsequence tails to make optimal choices

Two-Pass Frequency Count — Algorithm Steps

Count frequency of each number
For each unique number, try to form consecutive sequences of length 3
Decrease counts as we use numbers in sequences

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Count how many times each number appears

Build Sequences

For each number, greedily build longest consecutive sequence

Validate Length

Check if all sequences have length ≥ 3

Code -

solution.c — C

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

struct NumCount {
    int num;
    int count;
};

int compare(const void* a, const void* b) {
    return ((struct NumCount*)a)->num - ((struct NumCount*)b)->num;
}

bool solution(int* nums, int numsSize) {
    if (numsSize == 0) return true;
    
    // Simple frequency counting with sorted array
    struct NumCount counts[2000];
    int uniqueCount = 0;
    
    // Count frequencies
    for (int i = 0; i < numsSize; i++) {
        int found = 0;
        for (int j = 0; j < uniqueCount; j++) {
            if (counts[j].num == nums[i]) {
                counts[j].count++;
                found = 1;
                break;
            }
        }
        if (!found) {
            counts[uniqueCount].num = nums[i];
            counts[uniqueCount].count = 1;
            uniqueCount++;
        }
    }
    
    qsort(counts, uniqueCount, sizeof(struct NumCount), compare);
    
    for (int i = 0; i < uniqueCount; i++) {
        while (counts[i].count > 0) {
            int current = counts[i].num;
            int seqLength = 0;
            
            // Find consecutive numbers and use them
            for (int j = i; j < uniqueCount && counts[j].num == current && counts[j].count > 0; j++) {
                counts[j].count--;
                current++;
                seqLength++;
            }
            
            if (seqLength < 3) {
                return false;
            }
        }
    }
    
    return true;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int count = 0;
    char* token = strtok(line, "[],\n ");
    while (token != NULL && count < 1000) {
        nums[count++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    bool result = solution(nums, count);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each number, we may scan remaining numbers to form sequences

⚠ Quadratic Growth

Space Complexity

O(n)

Hash map to store frequency counts

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

847 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

Two-Pass Frequency Count — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler