<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) {
        unordered_map<int, int> left, end;
        for (int x : nums) left[x]++;
        for (int x : nums) {
            // cout << "x=" << x << endl;
            if (left[x - 1] && left[x - 2]) {
                // cout << left[x - 1] << ", " << left[x - 2] << endl;
                // 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., forming 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
                // we can append x to the new valid IS ending with x-1.
                while (left[x - 2] && end[x - 3])
                    left[x - 2]--, end[x - 3]--, end[x - 2]++;
                if (left[x - 2])
                    left[x]--, left[x - 1]--, left[x - 2]--, end[x]++;
                // cout << left[x - 1] << ", " << left[x - 2] << endl;
            }
        }
        // for  (int x : nums) {
        //     cout << "x: " << x << ", left[x]: " << left[x] << endl;
        // }
        for  (int x : nums) {
            if (!left[x]) continue;
            if (!end[x - 1]) return false;
            left[x]--, end[x - 1]--, end[x]++;
        }
        return true;
    }

    //     for (int x : nums) {
    //         if (left.count(x) && left.count(x - 1) && left.count(x - 2) &&
    //             left[x] > 0 && left[x - 1] > 0 && left[x - 2] > 0)
    //             left[x]--, left[x - 1]--, left[x - 2]--, end[x]++, cout << "Left: " << x << endl;
            
    //     }
    //     for (int x : nums) {
    //         if (left[x] <= 0) continue;
    //         if (end.count(x - 1) && end[x - 1] > 0)
    //             left[x]--, end[x - 1]--, end[x]++;
    //     }
    //     for (auto& p : left) cout << p.first << " -> " << p.second << endl; cout << endl;
    //     for (auto& p : end) cout << p.first << " -> " << p.second << endl;
    //     return accumulate(left.begin(), left.end(), 0, [](int accu, const auto& p){
    //         return accu + p.second;
    //     }) == 0;
    // }
};
65500