Problem statement

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

Solution 1

Not very clear statement of the problem, what is actually asked if we can split all our numbers into several segments such that each segment has at least 3 numbers. One possible ways to solve this problem is to use heaps: let us keep in our heap tuples of the form (biggest number in sequence + 1, length), for example for 4, 5, 6, 7 we will keep tuple (8, 4). So, let us go element by element and look at the smallest element in our heap. If num > heap[0][0] it means, that we can not continue corresponding sequence, so we remove this sequence from our heap and also check if it was small enough or not. Then if heap is empty or we can not add new num to any of our sequences, then we need to create new sequence and put it to heap. Finally, if we can add new num to some sequence, we add it to the shortest one.

Complexity

Time complexity of this approach is O(n log n), space complexity is O(n).

Code

class Solution:
    def isPossible(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]

Solution 2

There is also O(n) solution: note, that what we actually need for every number t is to keep 3 values: number of sequences with length 1 ending with t, number of sequences with length 2 ending with t and number of sequences with length >= 3 ending with t.

Complexity

Complexity now is O(n) both for time and space.

Code

class Solution:
    def isPossible(self, nums):
        dic = defaultdict(Counter)

        for num in nums:
            if num-1 in dic:
                if dic[num-1][1] > 0:
                    dic[num-1][1] -= 1
                    dic[num][2] += 1
                elif dic[num-1][2] > 0:
                    dic[num-1][2] -= 1
                    dic[num][3] += 1
                elif dic[num-1][3] > 0:
                    dic[num-1][3] -= 1
                    dic[num][3] += 1
                else:
                    dic[num][1] += 1
            else:
                dic[num][1] += 1
                
        for _, c in dic.items():
            if c[1] > 0 or c[2] > 0: return False
          
        return True