Problem Description

You are given an array of integers sorted in ascending order. Your task is to check if you can split the array into one or more subsequences such that each subsequence consists of consecutive integers and has length at least 3. If you can do this return true, otherwise return false.

For example:

If your input was [1,2,3,3,4,4,5,5] you could split this into two consecutive subsequences: [1,2,3,4,5] and [3,4,5], so you would return true.

In contrast, if your input was [1,2,3,4,4,5], you could not split this into two or more consecutive subsequences of length at least 3, so you would return false.

Approach

The solution uses the "Greedy" algorithm approach. This means that at each step, it makes the choice that seems best at the moment.

The algorithm creates two vectors : starts and ends. The starts vector holds the start indices of the sub-sequences and the ends vector holds the end indices of the sub-sequence.

The algorithm first calculates the number of times each number appears in the nums array. It then iterates over the nums array and checks if the current number is the same as the previous number. If it is the same, it goes to the next iteration because it means the current number is part of a current sub-sequence.

If the current number is not the same as the previous number, it is a potential start of a new sub-sequence. The algorithm will attempt to create as many new sub sequences starting from the current number as possible.

It not only counts the sub sequences that can be started at the current number, it also counts the sub sequences that can be ended at the current number.

At the end, it will compare the length of the sub-sequences to check if they are of length greater than or equal to 3 and return true or false accordingly.

Python Solution

1
2 python
3from collections import Counter
4class Solution:
5    def isPossible(self, nums):
6        remaining = Counter(nums)
7        ends = Counter()
8        for num in nums:
9            if not remaining[num]:
10                continue
11            remaining[num] -= 1
12            if ends[num - 1] > 0:
13                ends[num - 1] -= 1
14                ends[num] += 1
15            elif remaining[num + 1] and remaining[num + 2]:
16                remaining[num + 1] -= 1
17                remaining[num + 2] -= 1
18                ends[num + 2] += 1
19            else:
20                return False
21        return True

Java Solution

1
2 java
3class Solution {
4    public boolean isPossible(int[] nums) {
5        Map<Integer, Integer> count = new HashMap<>(), tails = new HashMap<>();
6        for (int x : nums) count.put(x, count.getOrDefault(x, 0) + 1);
7        for (int x : nums) {
8            if (!count.containsKey(x)) continue;
9            count.put(x, count.get(x) - 1);
10            if (count.get(x) == 0) count.remove(x);
11            if (tails.containsKey(x - 1) && tails.get(x - 1) > 0) {
12                tails.put(x - 1, tails.get(x - 1) - 1);
13                if (tails.get(x - 1) == 0) tails.remove(x - 1);
14                tails.put(x, tails.getOrDefault(x, 0) + 1);
15            } else if (count.containsKey(x + 1) && count.containsKey(x + 2)) {
16                count.put(x + 1, count.get(x + 1) - 1);
17                if (count.get(x + 1) == 0) count.remove(x + 1);
18                count.put(x + 2, count.get(x + 2) - 1);
19                if (count.get(x + 2) == 0) count.remove(x + 2);
20                tails.put(x + 2, tails.getOrDefault(x + 2, 0) + 1);
21            } else {
22                return false;
23            }
24        }
25        return true;
26    }
27}

JavaScript Solution

1
2 javascript
3var isPossible = function(nums) {
4    let freq = new Map(), freqSub = new Map()
5    for(let n of nums) freq.set(n, (freq.get(n) || 0) + 1)
6    for(let n of nums) 
7        if(!freq.get(n)) continue
8        else if(freqSub.get(n-1) || 0) {
9            freqSub.set(n-1, freqSub.get(n-1)-1)
10            freqSub.set(n, (freqSub.get(n) || 0) + 1)
11        } else if((freq.get(n+1) || 0) && (freq.get(n+2) || 0)) {
12            freq.set(n+1, freq.get(n+1)-1)
13            freq.set(n+2, freq.get(n+2)-1)
14            freqSub.set(n+2, (freqSub.get(n+2) || 0) + 1)
15        } else return false
16        freq.set(n, freq.get(n)-1)
17    return true
18};

C# Solution

1
2 csharp
3public class Solution {
4    public bool IsPossible(int[] nums) {
5        Dictionary<int, int> freq = new Dictionary<int, int>();
6        Dictionary<int, int> appendFreq = new Dictionary<int, int>();
7        foreach (int num in nums) {
8            if (!freq.ContainsKey(num)) {
9                freq.Add(num, 0);
10            }
11            freq[num]++;
12        }
13        foreach (int num in nums) {
14            if (freq[num]==0) {
15                continue;
16            } 
17            freq[num]--;
18            if (appendFreq.ContainsKey(num-1) && appendFreq[num-1]>0) {
19                appendFreq[num-1]--;
20                if (!appendFreq.ContainsKey(num)){
21                    appendFreq[num]=0;
22                }
23                appendFreq[num]++;
24            } else if (freq.ContainsKey(num+1) && freq[num+1]>0 &&
25                       freq.ContainsKey(num+2) && freq[num+2]>0) {
26                freq[num+1]--;
27                freq[num+2]--;
28                if (!appendFreq.ContainsKey(num+2)) {
29                    appendFreq[num+2]=0;
30                }
31                appendFreq[num+2]++;
32            } else {
33                return false;
34            }
35        }
36        return true;
37    }
38}

C++ Solution

1
2 cpp
3class Solution {
4public:
5    bool isPossible(vector<int>& nums) {
6        unordered_map<int, int> count;
7        unordered_map<int, int> ends;
8        for (int i : nums)
9            count[i]++;
10        for (int i : nums) {
11            if (!count[i])
12                continue;
13            count[i]--;
14            if (ends.count(i - 1) > 0 && ends[i - 1] > 0) {
15                ends[i - 1]--;
16                ends[i]++;
17            } else if (count.count(i + 1) > 0 && count[i + 1] > 0 &&
18                       count.count(i + 2) > 0 && count[i + 2] > 0) {
19                count[i + 1]--;
20                count[i + 2]--;
21                ends[i + 2]++;
22            } else
23                return false;
24        }
25        return true;
26    }
27};

This problem can be challenging for most programmers given its complex nature. However, with the correct approach and understanding of data structures, one can provide solutions in multiple languages, ensuring its comprehension among a wide range of coding enthusiasts.

As we can see, the solution follows the same logic in all programming languages. First, we create two counters: one to count the frequency of each number and another one to keep track of possible ends of subsequences. We then iterate through the nums list or array, checking if we can either append the number to an existing subsequence or start a new one. If none of this is possible and there are still numbers left, then we return false.

The Python solution makes use of Python's in-built Counter class from the collections module, which provides a way to count the frequency of elements in a list.

The Java solution uses a similar logic but being a statically-typed language, it uses the Map interface in combination with the HashMap class. Here, the containsKey and get methods are used to check for the existence of a particular value and its corresponding count in the count map.

The JavaScript solution also follows the same approach using JavaScript's built-in Map object to store the counts and update them accordingly.

The C# solution uses the Dictionary class, which is a collection of keys and values. It also provides methods to access, add, and update the keys and values.

Finally, The C++ solution uses the unordered_map from Standard Template Library(STL) to keep count frequencies and update them.

Please note that these solutions have a complexity of O(n) because we do a single pass through the array. Therefore, these are highly efficient and effective solutions to the problem.