Split Array into Consecutive Subsequences

In the game Dou Di Zhu, consecutive cards can form a straight. Sometimes, we can break pairs and combine single cards to make more straights, which may help us win.

So, how do we split the cards to make as many straights as possible? Today, let's look at an interesting algorithm problem—the problem of splitting an array into consecutive subsequences.

This is LeetCode Problem 659: Split Array into Consecutive Subsequences. The problem is simple:

You are given an ascending sorted array nums (it might have duplicate numbers). Please check if nums can be split into several subsequences of at least length 3, where each subsequence is made of consecutive integers.

Here is the function signature:

boolean isPossible(int[] nums);

bool isPossible(vector<int>& nums);

def isPossible(nums: List[int]) -> bool:

func isPossible(nums []int) bool

var isPossible = function(nums) {}

For example, with the input nums = [1,2,3,3,4,4,5,5], the algorithm should return true.

Because nums can be split into [1,2,3,4,5] and [3,4,5], which are both subsequences of consecutive numbers.

But if the input is nums = [1,2,3,4,4,5], the algorithm returns false because you can't split it into two subsequences of at least length 3.

When you see problems about consecutive integers, you should immediately think of sorting. In this problem, the array nums is already sorted.

Now, how do we check if nums can be split into several valid subsequences?

Similar to our earlier article Partitioning a Set with Backtracking, if we want to place each element of nums into a subsequence, the logic is like this: