659. Split Array into Consecutive Subsequences

https://leetcode.com/problems/split-array-into-consecutive-subsequences/

Python

Heap and sort (Timelimit Exceed)

import heapq


class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        heaps = []

        for num in nums:
            for heap in heaps:
                if -heap[0] == num-1:
                    heapq.heappush(heap, -num)
                    break
            else:
                heap = [-num]
                heaps.append(heap)

            heaps.sort(key=lambda h: len(h))

        return not any([len(h)<3 for h in heaps])

Bottom Up DP with Heap

from heapq import heappush, heappop
from collections import defaultdict


class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        dp = defaultdict(list)

        for num in nums:
            if dp[num-1]:
                head = heappop(dp[num-1])
                heappush(dp[num], head+1)
            else:
                heappush(dp[num], 1)

        for heap in dp.values():
            if not heap:
                continue
            if not all(x >= 3 for x in heap):
                return False
        return True