<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) {
        /*
        - when I come across a number I need to check 
        if it's already part of a subsequence
        - for this I can mantain a map that holds the 
        number of times each element appears
        - when I add an element to a subsequence 
        I can simply deduct the count
        - when the count hits 0, I would know 
        that the current element is already part of a subsequence
        
        - Now if I encounter an element that is 
        already part of a subsequence, I can ignore it, but suppose
        it is not already part of a subsequence (let's call this     
        element ele), then I need to consider the following two
        possibilities:
            1) can it be made part of existing subsequence?
                - to implement this, I need to keep track of where 
                a subsequence ended, if it ended on a element 
                just smaller than current element (ele - 1) I 
                can simply extend the subsequence
                - I can keep track of subsequence endings by simply 
                mantaining another map that keeps the number of 
                subsequence that end on a given element
            2) if not, can I make a new subsequence starting 
               from current element?
                - for this I simply need to check if ele+1 and ele+2 
                are available, I can check availabilit from left map
           
        */
        unordered_map<int, int> left, end;

        //creating the frequency map
        for (int i : nums)
            left[i]++;
        for (int i = 0; i < nums.size(); i++) {
            int ele = nums[i];
            //if ele already part of subsequence I can ignore it, this can happen when I have already started a new
            //subsequence at ele-2 [recall, to create a new subsequence I need 3 element, in this case: ele-2, ele-1, ele]
            if (left[ele] == 0)
                continue;
            //now I will try to add ele to subsequence, so I can just reduce the left count of ele
            //In the case that I am not able to add ele to any subsequence, I will simply be returning false, so it won't make
            //a difference
            left[ele]--;
            
            if (end[ele - 1] > 0) {
                //This is when there already exists a subsequence to which I can add ele 
                //when I add ele to subsequence, the subseq will now be ending at ele and not at ele-1, so I update end
                end[ele - 1]--;
                end[ele]++;
            } else if (left[ele + 1] > 0 && left[ele + 2] > 0) {
                //If no subseq to which I can add ele exists, I would have to make new subseq, so I just check if it's possible
                left[ele + 1]--;
                left[ele + 2]--;
                //if it's possible I would make a new subseq ending at ele+2: [ele, ele+1, ele+2], so I update end accordingly
                end[ele + 2]++;
            } else {
                //if I can neither add ele to a subseq, nor make a new one, the answer is going to be false
                return false;
            }
        }
        //if I reach here, this means that every ele has been added to a subseq so I can just return true
        return true;
    }
};
62000