DEV Community

SalahElhossiny
SalahElhossiny

Posted on

1 1

Split Array into Consecutive Subsequences

You are given an integer array nums that is sorted in non-decreasing order.

Determine if it is possible to split nums into one or more subsequences such that both of the following conditions are true:

Each subsequence is a consecutive increasing sequence (i.e. each integer is exactly one more than the previous integer).
All subsequences have a length of 3 or more.
Return true if you can split nums according to the above conditions, or false otherwise.

A subsequence of an array is a new array that is formed from the original array by deleting some (can be none) of the elements without disturbing the relative positions of the remaining elements. (i.e., [1,3,5] is a subsequence of [1,2,3,4,5] while [1,3,2] is not).

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

        if len(nums) < 3: return False

        frequency = collections.Counter(nums)
        subsequence = collections.defaultdict(int)

        for i in nums:

            if frequency[i] == 0:
                continue

            frequency[i] -= 1

            # option 1 - add to an existing subsequence
            if subsequence[i-1] > 0:
                subsequence[i-1] -= 1
                subsequence[i] += 1

            # option 2 - create a new subsequence 
            elif frequency[i+1] and frequency[i+2]:
                frequency[i+1] -= 1
                frequency[i+2] -= 1
                subsequence[i+2] += 1

            else:
                return False

        return True

Enter fullscreen mode Exit fullscreen mode

AWS Security LIVE!

Join us for AWS Security LIVE!

Discover the future of cloud security. Tune in live for trends, tips, and solutions from AWS and AWS Partners.

Learn More

Top comments (0)

Billboard image

Create up to 10 Postgres Databases on Neon's free plan.

If you're starting a new project, Neon has got your databases covered. No credit cards. No trials. No getting in your way.

Try Neon for Free →

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay