BinarySearch 0583 List Splitting to Consecutive Subsequences

Problem statement

https://binarysearch.com/problems/List-Splitting-to-Consecutive-Subsequences/

Solution

Equal to Leetcode 0659 Split Array into Consecutive Subsequences.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, nums):
        heap = []

        for num in nums:
            while heap and num > heap[0][0]:
                a, b = heappop(heap)
                if b < 3: return False
            
            if not heap or heap[0][0] != num:
                heappush(heap, (num + 1, 1))
            elif heap[0][0] == num:
                a, b = heappop(heap)
                heappush(heap, (a+1, b+1))      
                
        return True not in [b < 3 for a,b in heap]