Split Array into Consecutive Subsequences - Solution & Explanation

Problem Overview: You receive a sorted integer array and must determine whether it can be split into one or more subsequences of consecutive integers, each with length at least 3. Every element must belong to exactly one subsequence.

Approach 1: Greedy Hash Map (Iterative) (Time: O(n), Space: O(n))

This approach uses two hash maps. The first map freq tracks how many times each number appears. The second map need tracks how many subsequences are currently waiting for a specific next number. Iterate through the array and try to append the current number to an existing subsequence if need[num] > 0. If not possible, attempt to start a new subsequence using num, num+1, num+2 by checking their counts in freq. If neither option works, forming valid subsequences is impossible. The greedy insight: always extend an existing subsequence before creating a new one. This avoids leaving short sequences that cannot reach length 3. This method heavily relies on fast hash table lookups and is the standard optimal solution using a greedy strategy.

Approach 2: Min-Heap Tracking Subsequence Lengths (Time: O(n log n), Space: O(n))

Another strategy maintains active subsequences using a min-heap. Each heap entry represents a subsequence ending at a specific value and stores its length. When processing a number, check if there is a subsequence ending at num - 1. If one exists, extend the shortest such subsequence (pop from heap, increment length, push back with new end). If none exists, start a new subsequence of length 1. After processing all numbers, verify that every subsequence has length at least 3. The heap ensures the shortest subsequence grows first, which prevents invalid short chains. This technique demonstrates how a priority queue can manage competing subsequences efficiently.

Approach 3: Recursive Backtracking (Time: Exponential worst-case, Space: O(n))

A recursive solution tries to build subsequences by deciding where each number should go. Maintain partial subsequences and recursively attempt to extend them or start new ones. Each recursive branch chooses a subsequence whose last element is num - 1 or creates a new sequence. Pruning occurs when a sequence cannot possibly reach length 3. While conceptually simple, the branching factor grows quickly, leading to exponential time in the worst case. This method mainly helps illustrate the problem constraints before discovering the greedy pattern.

Recommended for interviews: The greedy hash map solution is what interviewers expect. It demonstrates recognition of the greedy invariant (extend existing subsequences first) and efficient use of frequency counting with hash maps. Discussing the heap method also shows strong understanding of alternative designs, but the O(n) greedy approach is considered the optimal answer.