Problem Description

You have an integer array nums that is sorted in non-decreasing order (like [1, 2, 2, 3, 3, 4, 4, 5]).

Your task is to determine if you can split all elements of this array into groups (subsequences) where:

1. Each group forms a consecutive increasing sequence: The numbers in each group must be consecutive integers that increase by exactly 1. For example, [3, 4, 5] is valid, but [3, 5, 6] is not (missing 4).

2. Each group must have at least 3 elements: Groups like [1, 2] are too short and not allowed.

The key point is that you're selecting elements from the original array to form these groups, and you can skip elements as long as you maintain the relative order. Every element in nums must be used exactly once in exactly one group.

For example:

• nums = [1, 2, 3, 3, 4, 5] can be split into [1, 2, 3] and [3, 4, 5], so return true
• nums = [1, 2, 3, 3, 4, 4, 5, 5] can be split into [1, 2, 3, 4, 5] and [3, 4, 5], so return true
• nums = [1, 2, 3, 4, 4, 5] cannot be split according to the rules, so return false

The solution uses a greedy approach with heaps. For each number, it either extends an existing sequence that ends at v-1, or starts a new sequence. It tracks the length of sequences ending at each value using min-heaps. At the end, it checks if all sequences have length greater than 2.

Intuition

When we encounter each number in the sorted array, we face a critical decision: should this number extend an existing sequence or start a new one?

The key insight is that we should always prefer to extend an existing sequence rather than starting a new one. Why? Because starting a new sequence creates an additional constraint - we'll need to find at least two more consecutive numbers to complete it. By extending an existing sequence, we're making progress toward satisfying the length requirement.

Consider what happens when we see a number v:

• If there's a sequence ending at v-1, we can extend it by adding v
• If no sequence ends at v-1, we have no choice but to start a new sequence beginning with v

But what if multiple sequences end at v-1? Which one should we extend? Here's the crucial observation: we should extend the shortest sequence first. This is because shorter sequences are at greater risk of not meeting the minimum length requirement of 3. By prioritizing them, we maximize our chances of making all sequences valid.

This naturally leads to using a min-heap (priority queue) data structure. For each value, we maintain a min-heap of sequence lengths ending at that value. When we process a number v:

1. Check if any sequences end at v-1
2. If yes, pop the shortest one (using heappop), increment its length, and push it to the heap for value v
3. If no, start a new sequence of length 1 at value v

After processing all numbers, we simply verify that every sequence has reached a length of at least 3. The beauty of this approach is that it greedily makes the locally optimal choice at each step, which turns out to give us the globally optimal solution.

Learn more about Greedy and Heap (Priority Queue) patterns.

Solution Approach

The implementation uses a greedy algorithm with min-heaps to track and extend sequences optimally.

Data Structure:

• d = defaultdict(list): A dictionary where each key is a number and the value is a min-heap containing lengths of all sequences ending at that number.

Algorithm Steps:

1. Iterate through each number v in the sorted array:

   for v in nums:

2. Check if we can extend an existing sequence:

   if h := d[v - 1]:
       heappush(d[v], heappop(h) + 1)

   • Use the walrus operator := to check if there are sequences ending at v-1
   • If yes, pop the shortest sequence from d[v-1] using heappop(h)
   • Extend this sequence by incrementing its length by 1
   • Push the extended sequence to d[v] using heappush

3. Start a new sequence if no extension is possible:

   else:
       heappush(d[v], 1)

   • If no sequences end at v-1, start a new sequence of length 1 at value v

4. Validate all sequences:

   return all(not v or v and v[0] > 2 for v in d.values())

   • Check each heap in the dictionary
   • not v: Empty heap is valid (no sequences ending at this value)
   • v and v[0] > 2: If heap exists, the minimum length (at index 0) must be greater than 2
   • The all() function ensures every sequence meets the length requirement

Why This Works:

• By always extending the shortest sequence first (using min-heap), we maximize the chance that all sequences reach the minimum required length
• The greedy choice at each step (extend shortest or start new) leads to the optimal global solution
• Since the array is sorted, we process numbers in order, ensuring we can only extend sequences in a valid consecutive manner

Time Complexity: O(n log n) where n is the length of nums, due to heap operations Space Complexity: O(n) for storing the dictionary and heaps

Example Walkthrough

Let's walk through the algorithm with nums = [1, 2, 3, 3, 4, 5] to see how it determines this can be split into valid groups.

Initial state: d = {} (empty dictionary)

Step 1: Process v = 1

• Check if sequences end at v-1 = 0: No sequences at d[0]
• Start new sequence: d[1] = [1] (sequence of length 1 ending at 1)

Step 2: Process v = 2

• Check if sequences end at v-1 = 1: Yes! d[1] = [1]
• Extend shortest sequence: Pop length 1 from d[1], add 1, push to d[2]
• Result: d[1] = [], d[2] = [2] (sequence of length 2 ending at 2)

Step 3: Process v = 3

• Check if sequences end at v-1 = 2: Yes! d[2] = [2]
• Extend shortest sequence: Pop length 2 from d[2], add 1, push to d[3]
• Result: d[2] = [], d[3] = [3] (sequence of length 3 ending at 3)

Step 4: Process v = 3 (second occurrence)

• Check if sequences end at v-1 = 2: No sequences at d[2] (empty now)
• Start new sequence: d[3] = [3, 1] → After heappush: d[3] = [1, 3]
• Now we have two sequences ending at 3: one of length 3, one of length 1

Step 5: Process v = 4

• Check if sequences end at v-1 = 3: Yes! d[3] = [1, 3]
• Extend shortest sequence: Pop length 1 (the minimum), add 1, push to d[4]
• Result: d[3] = [3], d[4] = [2] (extended the newer sequence)

Step 6: Process v = 5

• Check if sequences end at v-1 = 4: Yes! d[4] = [2]
• Extend shortest sequence: Pop length 2, add 1, push to d[5]
• Result: d[4] = [], d[5] = [3]

Final validation:

• d[1] = [] (empty, valid)
• d[2] = [] (empty, valid)
• d[3] = [3] (minimum length is 3, valid ✓)
• d[4] = [] (empty, valid)
• d[5] = [3] (minimum length is 3, valid ✓)

All sequences have length ≥ 3, so return true.

The algorithm successfully identified two sequences: [1, 2, 3] (the first three elements) and [3, 4, 5] (elements at indices 3, 4, 5).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n)

The algorithm iterates through the input array nums once, performing the following operations for each element:

• Checking if d[v - 1] exists: O(1) average case for dictionary lookup
• heappop operation: O(log k) where k is the size of the heap at key v - 1
• heappush operation: O(log m) where m is the size of the heap at key v

In the worst case, all elements could end up in the same heap, making the heap operations O(log n). Since we perform these operations for each of the n elements, the overall time complexity is O(n log n).

The final validation step iterates through all dictionary values, checking the minimum element of each heap. Since accessing the minimum of a heap is O(1) and we have at most n distinct keys, this step is O(n).

Therefore, the total time complexity is O(n log n) + O(n) = O(n log n).

Space Complexity: O(n)

The space is used by:

• The dictionary d which stores heaps: In the worst case, we have n distinct values as keys, and the total number of elements across all heaps equals n (since each input element is pushed exactly once)
• The heaps themselves store integers representing sequence lengths

The total space required is O(n) for storing all the elements across the dictionary and its heaps.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Understanding Why Greedy Extension Works

Many developers struggle to understand why always extending the shortest sequence is optimal. The key insight is that by extending the shortest sequences first, we give them the best chance to reach the minimum required length of 3. If we extended longer sequences instead, shorter ones might get "stranded" without enough consecutive numbers to reach length 3.

Example of Wrong Approach:

# WRONG: Extending any available sequence randomly
if subsequence_lengths[current_num - 1]:
    # Just pop any sequence, not necessarily the shortest
    some_length = subsequence_lengths[current_num - 1].pop()  # Wrong!
    subsequence_lengths[current_num].append(some_length + 1)

2. Forgetting to Use a Min-Heap

A critical pitfall is using a regular list instead of a heap, which breaks the algorithm's correctness.

Incorrect Implementation:

# WRONG: Using regular lists instead of heaps
subsequence_lengths = defaultdict(list)
for current_num in nums:
    if subsequence_lengths[current_num - 1]:
        # This doesn't get the minimum!
        length = subsequence_lengths[current_num - 1].pop(0)  # Wrong!
        subsequence_lengths[current_num].append(length + 1)

Correct Fix: Always use heappush and heappop to maintain the min-heap property.

3. Incorrect Final Validation

A subtle but common mistake is checking the wrong condition at the end.

Wrong Validation Examples:

# WRONG: Checking if ANY sequence is valid
return any(not v or min(v) > 2 for v in subsequence_lengths.values())

# WRONG: Checking maximum instead of minimum
return all(not v or max(v) > 2 for v in subsequence_lengths.values())

# WRONG: Off-by-one error in length check
return all(not v or v[0] >= 2 for v in subsequence_lengths.values())  # Should be > 2

Correct Validation:

# Check that ALL sequences have length > 2 (at least 3 elements)
return all(not heap or heap[0] > 2 for heap in subsequence_lengths.values())

4. Misunderstanding Empty Heaps in Final Check

Some developers get confused about why we need to check not heap in the final validation. Empty heaps are valid because they mean no sequences end at that particular number - all sequences that passed through that number have been extended further.

Overly Complicated Check:

# Unnecessary: Filtering out empty heaps
non_empty_heaps = [heap for heap in subsequence_lengths.values() if heap]
return all(heap[0] > 2 for heap in non_empty_heaps)

While this works, the simpler not heap or heap[0] > 2 pattern is cleaner and more idiomatic.

5. Not Handling Edge Cases Properly

Failing to consider arrays where all numbers are the same or have large gaps.

Example Edge Cases to Consider:

• nums = [1, 1, 1, 2, 2, 2, 3, 3, 3] - All numbers appear exactly 3 times
• nums = [1, 2, 3, 6, 7, 8] - Gap between consecutive sequences
• nums = [1] - Single element (should return False)

The algorithm handles these correctly, but understanding why helps avoid modifications that break these cases.