<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) 
    {
        int n = nums.size();

        // using a frequency map to store freq of all nums
        // a second map is used to store the next possible number for an already created subsequence,
        // as well as the frequency, indicating how many such joins will be possible for an already created
        // subsequence

        unordered_map<int, int> freq;
        for(int ele: nums)
        ++freq[ele];

        unordered_map<int, int> nextPossible;
        for(int ele: nums)
        {
            if(freq[ele] != 0)
            {
                if(nextPossible.find(ele) != nextPossible.end())
                {
                    --nextPossible[ele];
                    if(nextPossible[ele] == 0)
                    nextPossible.erase(ele);

                    // now ele + 1 becomes the next possible joinable number to subsequence
                    ++nextPossible[ele + 1];
                    --freq[ele];
                }

                // this is checking if we can create a subsequence of length 3 which starts at ele
                // checking this greedily works because:
                // suppose we didn't do this check for ele = 1, which is the lowest number in array.
                // now, if we didn't perform check for this, there is no way where ele = 1 will be checked for
                // again since we are always checking for new subsequences where elements are consecutive.
                // In that case, ele = 1 will always have to be the starting element of a subsequence
                else if(freq[ele + 1] > 0 && freq[ele + 2] > 0)
                {
                    --freq[ele];
                    --freq[ele + 1];
                    --freq[ele + 2];

                    ++nextPossible[ele + 3];
                }
            }
        }

        // if all elements frequency is zero, then there exists atleast one such combo of subsequences, 
        // where all elements will be included, else not possible
        for(auto p: freq)
        {
            if(p.second != 0)
            return false;
        }    

        return true;
    }
};
64700