Split Array into Consecutive Subsequences

Intuition

Process numbers in ascending order and keep two counters: freq[v] for how many copies of v are still unused, and need[v] for how many already-formed subsequences are waiting for value v to extend. When we reach a value v, the greedy rule is to first spend it extending a subsequence that needs it, because appending to an existing run is never worse than opening a new one. If nothing needs v, we try to start a brand-new run v, v+1, v+2, which requires those next two values to be available. If neither option is possible, a valid partition cannot exist. Consuming everything successfully means every run reached length three or more.

Algorithm walkthrough

1. 1Count the frequency of every value into a freq map and start need empty.
2. 2Iterate through the numbers in order; skip any value whose freq has already been fully consumed.
3. 3If need[v] is positive, attach v to a waiting run: decrement need[v] and increment need[v+1].
4. 4Otherwise, if freq[v+1] and freq[v+2] are both available, open a new run by consuming those two and setting need[v+3] up by one.
5. 5If neither branch applies, return false immediately.
6. 6Decrement freq[v] after placing it, and return true once all numbers are placed.

Implementation

class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        freq = Counter(nums)
        need = Counter()
        for num in nums:
            if freq[num] == 0:
                continue
            if need[num] > 0:
                need[num] -= 1
                need[num + 1] += 1
            elif freq[num + 1] > 0 and freq[num + 2] > 0:
                freq[num + 1] -= 1
                freq[num + 2] -= 1
                need[num + 3] += 1
            else:
                return False
            freq[num] -= 1
        return True