Showing posts with label Split Array into Consecutive Subsequences - Leetcode Python. Show all posts
Showing posts with label Split Array into Consecutive Subsequences - Leetcode Python. Show all posts

Split Array into Consecutive Subsequences - Leetcode Python

 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
Solution :
class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        count = collections.Counter(nums)
        tails = collections.Counter()
        for x in nums:
            if count[x] == 0:
                continue
            elif tails[x] > 0:
                tails[x] -= 1
                tails[x+1] +=1
                count[x] -= 1
            elif count[x] > 0 and count[x+1] > 0 and count[x+2] > 0:
                count[x] -= 1
                count[x+1] -=1
                count[x+2] -=1
                tails[x+3] +=1
            else:
                return False
            
        return True
TC: O(n) SC:O(n)
        

Featured Post

H1B Visa Stamping at US Consulate

  H1B Visa Stamping at US Consulate If you are outside of the US, you need to apply for US Visa at a US Consulate or a US Embassy and get H1...