"""
Split Array Into Consecutive Subsequence

Given an array nums sorted in ascending order, return true if and only if you can split it into 1 or more subsequences such that each subsequence consists of consecutive integers and has length at least 3.

 

Example 1:

Input: [1,2,3,3,4,5]
Output: True
Explanation:
You can split them into two consecutive subsequences : 
1, 2, 3
3, 4, 5

Example 2:

Input: [1,2,3,3,4,4,5,5]
Output: True
Explanation:
You can split them into two consecutive subsequences : 
1, 2, 3, 4, 5
3, 4, 5

Example 3:

Input: [1,2,3,4,4,5]
Output: False
 

Constraints:

1 <= nums.length <= 10000
"""

"""
Greedy
Intuition

Call a chain a sequence of 3 or more consecutive numbers.

Considering numbers x from left to right, if x can be added to a current chain, it's at least as good to add x to that chain first, rather than to start a new chain.

Why? If we started with numbers x and greater from the beginning, the shorter chains starting from x could be concatenated with the chains ending before x, possibly helping us if there was a "chain" from x that was only length 1 or 2.

Algorithm

Say we have a count of each number, and let tails[x] be the number of chains ending right before x.

Now let's process each number. If there's a chain ending before x, then add it to that chain. Otherwise, if we can start a new chain, do so.

It's worth noting that our solution can be amended to take only O(1) additional space, since we could do our counts similar to Approach #1, and we only need to know the last 3 counts at a time.

Time: O(N)
Space: O(N)
"""
class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        count = collections.Counter(nums)
        tails = collections.Counter()
        for x in nums:
            if count[x] == 0: # if all used
                continue
            elif tails[x] > 0: # adding to a new chain 
                tails[x] -= 1 # one ending at current has ended
                tails[x+1] += 1 # next number ending increase by 1
            elif count[x+1] > 0 and count[x+2] > 0: # if starting a new chain
                count[x+1] -= 1
                count[x+2] -= 1
                tails[x+3] += 1
            else: # if cannot start a new chain and no existing chain to add to
                return False
            count[x] -= 1
        return True

class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        left = collections.Counter(nums)
        end = collections.Counter()
        for i in nums:
            if not left[i]: 
                continue
            left[i] -= 1
            if end[i - 1] > 0: # if we have a chain that ended at the number just before i
                end[i - 1] -= 1
                end[i] += 1
            elif left[i + 1] and left[i + 2]: # start a new chain
                left[i + 1] -= 1
                left[i + 2] -= 1
                end[i + 2] += 1
            else:
                return False
        return True

# https://leetcode.com/discuss/interview-question/311895/Google-or-Phone-screen-or-Split-Array-into-Consecutive-Subsequences
