<p>You are given an integer array <code>nums</code> that is <strong>sorted in non-decreasing order</strong>.</p>

<p>Determine if it is possible to split <code>nums</code> into <strong>one or more subsequences</strong> such that <strong>both</strong> of the following conditions are true:</p>

<ul>
	<li>Each subsequence is a <strong>consecutive increasing sequence</strong> (i.e. each integer is <strong>exactly one</strong> more than the previous integer).</li>
	<li>All subsequences have a length of <code>3</code><strong> or more</strong>.</li>
</ul>

<p>Return <code>true</code><em> if you can split </em><code>nums</code><em> according to the above conditions, or </em><code>false</code><em> otherwise</em>.</p>

<p>A <strong>subsequence</strong> 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., <code>[1,3,5]</code> is a subsequence of <code>[<u>1</u>,2,<u>3</u>,4,<u>5</u>]</code> while <code>[1,3,2]</code> is not).</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,3,4,5]
<strong>Output:</strong> true
<strong>Explanation:</strong> nums can be split into the following subsequences:
[<strong><u>1</u></strong>,<strong><u>2</u></strong>,<strong><u>3</u></strong>,3,4,5] --&gt; 1, 2, 3
[1,2,3,<strong><u>3</u></strong>,<strong><u>4</u></strong>,<strong><u>5</u></strong>] --&gt; 3, 4, 5
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,3,4,4,5,5]
<strong>Output:</strong> true
<strong>Explanation:</strong> nums can be split into the following subsequences:
[<strong><u>1</u></strong>,<strong><u>2</u></strong>,<strong><u>3</u></strong>,3,<strong><u>4</u></strong>,4,<strong><u>5</u></strong>,5] --&gt; 1, 2, 3, 4, 5
[1,2,3,<strong><u>3</u></strong>,4,<strong><u>4</u></strong>,5,<strong><u>5</u></strong>] --&gt; 3, 4, 5
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4,4,5]
<strong>Output:</strong> false
<strong>Explanation:</strong> It is impossible to split nums into consecutive increasing subsequences of length 3 or more.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>4</sup></code></li>
	<li><code>-1000 &lt;= nums[i] &lt;= 1000</code></li>
	<li><code>nums</code> is sorted in <strong>non-decreasing</strong> order.</li>
</ul>

class Solution {
public:
    bool isPossible(vector<int>& nums) {
        // return isPossible1(nums);
        return isPossible2(nums);
    }

    bool isPossible1(vector<int>& nums) {
        unordered_map<int, int> left, end;
        for (int x : nums) left[x]++;
        // The key point of this solution is:
        // If there is a valid subsequence ended with x-1, place current x at the end of subsequence 
        // always better/less risk than create a new subsequence started with x due to has length at least 3.
        // 1) Creating a new valid IS of x, x+1 and x+2, will force x+2 to put in the same IS with x,
        //   which will cost some x+2, which might be used later, when (x+1)s are so many that we have to
        //   create new valid IS starting with x+1, i.e., x+1, x+2, x+3.
        // 2) When there is a valid IS ending with x-1, it is unnecessary to create that x, x+1, x+2 IS so
        //   early, since we can always append them one by one to the valid IS ending with x-1 later, if
        //   x+2 is not used in new valid IS starting with x+1.
        for (int x : nums) {
            if (!left[x]) continue;
            if (end[x - 1])  // append x to the existing valid IS
                left[x]--, end[x - 1]--, end[x]++;
            else if (left[x + 1] && left[x + 2])  // form new valid IS with x+1 and x+2, will make x+2 into same IS with x
                left[x]--, left[x + 1]--, left[x + 2]--, end[x + 2]++;
            else
                return false;  // no way to consume x, so x will belong to no valid IS
        }
        return true;
    }

    bool isPossible2(vector<int>& nums) {
        unordered_map<int, int> left, end;
        for (int x : nums) left[x]++;
        // When we find x-2, x-1 and x, the greedy policy is:
        // To cancel out x-1 and x-2, we should firstly check if there is already 
        // an valid IS ending with x-3, and append them to that valid IS. Because 
        // saving x for later use, e.g., creating new valid IS with remaining x-2 and x-1, 
        // or with x-1, x+1 or with x+1, x+2, is alwasy better, since if it is not used that way,
        // when it iterates to x+2, we can append x to the new valid IS ending with x-1.
        for (int x : nums) {
            while (left[x - 2] && end[x - 3])  // put x-2 to existing valid IS ending with x-3
                left[x - 2]--, end[x - 3]--, end[x - 2]++;
            while (left[x] && left[x - 1] && left[x - 2])  // valid IS ending with x-3 is not enough
                left[x]--, left[x - 1]--, left[x - 2]--, end[x]++;  // cancel out x-2 by creating new valid IS
            if (left[x - 2]) return false;  // x-2 still remains, no way to cancel it out, return false

        }
        for  (int x : nums) {
            if (!left[x]) continue;
            if (!end[x - 1]) return false;
            left[x]--, end[x - 1]--, end[x]++;  // append remaining x to existing valid IS
        }
        return true;
    }
};
62600