<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>

// https://www.youtube.com/watch?v=Ty8EZlxVNC8

class Solution {
public:
    bool isPossible(vector<int>& nums) {
        int n = nums.size();

        unordered_map<int, int> mp;

        for (int i = 0; i < n; i++) {
            mp[nums[i]]++;
        }

        // algorithm

        unordered_map<int, int> vacancy;

        for(int i = 0; i < n; i++){
            if(mp.count(nums[i]) == 0){
                continue;
            }

            if(vacancy.count(nums[i])){
                // use it
                vacancy[nums[i]]--;
                if(vacancy[nums[i]] == 0){
                    vacancy.erase(nums[i]);
                }

                mp[nums[i]]--;
                if(mp[nums[i]] == 0){
                    mp.erase(nums[i]);
                }

                // insert new vacancy
                vacancy[nums[i] + 1]++;
            } else{
                // create new group
                int first = nums[i], second = nums[i] + 1, third = nums[i] + 2;
                mp[first]--;
                if(mp[first] == 0){
                    mp.erase(first);
                }

                if(mp.count(second) == 0 or mp.count(third) == 0){
                    return false;
                }

                mp[second]--;
                mp[third]--;
                if(mp[second] == 0){
                    mp.erase(second);
                }
                if(mp[third] == 0){
                    mp.erase(third);
                }

                // insert new vacancy
                vacancy[third + 1]++;
            }
        }

        return true;




        // for (int i = 0; i < n; i++) {
        //     auto it = vacancy.find(nums[i]);
        //     if (it != vacancy.end()) {
        //         if (it->second == 1) {
        //             vacancy.erase(nums[i]);
        //         } else {
        //             vacancy[nums[i]]--;
        //         }
        //         // add this to that group and create vacancy for next element
        //         vacancy[nums[i] + 1]++;
        //         if(mp[nums[i]] > 1){
        //             mp[nums[i]]--;
        //         } else{
        //             mp.erase(nums[i]);
        //         }
        //     } else {
        //         // create new group but iff nums[i]+1 and nums[i]+2 elemetns are
        //         // there
        //         int first = nums[i], second = nums[i] + 1, third = nums[i] + 2;

        //         auto it1 = mp.find(first);
        //         auto it2 = mp.find(second);
        //         auto it3 = mp.find(third);

        //         if (it1 == mp.end() or it2 == mp.end() or it3 == mp.end()) {
        //             return false; // because no vacancy plus not able to form
        //                           // the group
        //         }

        //         if (it1->second == 1) {
        //             mp.erase(first);
        //         } else {
        //             mp[first]--;
        //         }

        //         if (it2->second >= 1) {
        //             mp[second]--;
        //         }

        //         if (it3->second >= 1) {
        //             mp[third]--;
        //         }

        //         // create new vacancy
        //         vacancy[third + 1]++;
        //     }
        // }
        // return true;
    }
};

/*
    every number will be starting point of new grp

    or part of existing group

    otherwise false


    important algorithm:


    1. count map
    2. vacancy open map: this will be hjolding elements with count of vacancies
   for the groups created

    element: will only create group iffffff it is not part of vacacy and all 2
   elements are availble to us +1 and +2


*/
62100