# C++, DP easy to understand, O(n) time O(1) space

• I feel this problem hard. The idea here is DP.

1. If numbers are not continuous, I check each segment. For example, 1,2,3,3,4,5, 9,10,11;
2. Count frequency of each continuous number. Note the value of numbers doesn't matter.
3. DP part. I use parameter "ones" for subsequences with length 1 ending with index i, "twos" for subsequences with length 2 ending with index i, and "tot" for all subsequences ending with index i.
When processing next number, if the frequency of new number mp[i+1] < ones+twos, there is no way to split, return false.
In a greedy way, we need append the new number to short sequences first. So
twos[i+1] = ones[i];
ones[i+1] = mp[i+1]-tot, i.e. the extra new number
If it is possible to split, ones and twos would be 0 by the end of the loop.

The run time is clearly O(n).

``````class Solution {
public:
bool isPossible(vector<int>& nums) {
int n = nums.size(), k = 0;
//if nums are not continuous, check each section
//for example, 1,2,3, 6,7,8;
for (int i = 1; i < n; i++) {
if (nums[i]-nums[i-1] > 1) {
if (!check(nums, k, i-1))
return false;
k = i;
}
}
return check(nums, k, n-1);
}
private:
bool check(vector<int>& nums, int s, int e) {
int n = nums[e]-nums[s]+1;
// count frequency of each number
vector<int> mp(n, 0);
for (int i = s, tmp = nums[s]; i <= e; i++)
mp[nums[i]-tmp]++;
// ones is subsequences with length 1 ending with index i-1
// twos is subsequences with length 2 ending with index i-1
// tot  is all subsequences ending with index i-1
// initially ones[0] ending with index -1, i.e. nonexistent
vector<int> ones(n+1, 0), twos(n+1, 0), tot(n+1, 0);
for (int i = 0; i < n; i++) {
// we need at least ones+twos new number to make consecutive sequence
// for examle, two 2, five 1,2, we need at least seven 3
if (mp[i] < ones[i] + twos[i]) return false;
// Greedy, appending to short sequences first
// so twos = ones, and new ones is the extra new number
twos[i+1] = ones[i];
ones[i+1] = max(0, mp[i]-tot[i]);
tot[i+1] = mp[i];
}
// if no subsequence length <= 2, return true
return ones[n] == 0 && twos[n] == 0;
}
};
``````

Same code but O(1) space

``````class Solution {
public:
bool isPossible(vector<int>& nums) {
int n = nums.size(), k = 0;
for (int i = 1; i < n; i++) {
if (nums[i]-nums[i-1] > 1) {
if (!check(nums, k, i))
return false;
k = i;
}
}
return check(nums, k, n);
}
private:
bool check(vector<int>& nums, int s, int e) {
int ones = 0, twos = 0, tot = 0;
for (int i = s+1, cnt = 1; i <= e; i++) {
if (i < e && nums[i] == nums[i-1])
cnt++;
else {
if (cnt < ones + twos) return false;
twos = ones;
ones = max(0, cnt-tot);
tot = cnt;
cnt = 1;
}
}
return ones == 0 && twos == 0;
}
};
``````

• No need to use dp, we can just check every three numbers to ensure that there is sequence

``````public class Solution {
public boolean isPossible(int[] nums) {
int base = nums[0];
for (int i = 0; i < nums.length; i++){
nums[i] = nums[i] - base;
}
int[] fre = new int[nums[nums.length - 1] + 3];
for (int n : nums) fre[n]++;
for (int i = 2; i <= nums[nums.length - 1] + 2; i++){
int one = Math.max(fre[i - 1] - fre[i - 2], 0);
int two = Math.max(0, fre[i - 2] - (i >= 3 ? fre[i - 3] : 0));
if (fre[i] < one + two || fre[i - 1] < two){
return false;
}
}
return true;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.