c++ | Russian Doll Envelopes || Simple Solution
Why we need to sort?\n\nIn these types of problem when we are dealing with two dimensions, we need to reduce the problem from two-dimensional array into a one-d
Why we need to sort?\n\nIn these types of problem when we are dealing with two dimensions, we need to reduce the problem from two-dimensional array into a one-dimensional array in order to improve time complexity.\n\t\n"**Sort first when things are undecided**", sorting can make the data orderly, reduce the degree of confusion, and often help us to sort out our thinking. the same is true with this question. Now, after doing the correct sorting, we just need to find Longest Increasing Subsequence of that one dimensional array.\n\nNow, you may be wondered what correct sorting actually is?\n   \nIt is the sorting which we do to order to achieve the answer. Like, increasing, non-increasing sorting. Without any further discussion, let\'s dig into Intuition followed by algorithm.\n\nAlgorithm\n\n*    We sort the array in increasing order of width. And if two widths are same, we need to sort height in decreasing order.\n*   Now why we need to sort in decreasing order if two widths are same. By this practice, we\'re assuring that no width will get counted more than one time. Let\'s take an example\n*   envelopes=[[3, 5], [6, 7], [7, 13], [6, 10], [8, 4], [7, 11]]\n\n*   Now, if you see for a while, 6 and 7 is counted twice while we\'re calculating the length of LIS, which will give the wrong ans. As question is asking, if any width/height are less than or equal, then, it is not possible to russian doll these envelopes.\n\n\n*   Now, we know the problem. So, how can we tackle these conditions when two width are same, so that it won\'t affect our answer. We can simple reverse sort the height if two width are equal, to remove duplicacy.\n\n*   Now, you may question, how reverse sorting the height would remove duplicacy? As the name itself says, Longest Increasing Subsequnce, the next coming height would be less than the previous one. Hence, forbidding it to increase length count.\n\n\t* Breify speaking we sort the envelopes based on width in ascending\n\t\t* After this Envelopes look like [[3, 5], [6, 7],[6, 10], [7, 11] ,[7, 13] , [8, 4]]\n\t* Then we sort those element in decreasing order fro which width is same\n\t\t* After this Envelopes look like [[3, 5], [6, 10],[6, 7], [7, 13] ,[7, 11] , [8, 4]]\n\n\t* **Then we Count length of Longest increasing subsequence based on Height only** i.e {5,10,7,13,11,4}\n\t\t* So it comes out to be 3\n   \n   \n**  If you don\'t understand how LIS is calculated here, I strongly refer you to follow the prerequisite.**\n  \nNow, we have sucessfully reduced the problem to LIS! All you need to apply classical LIS on heights, to calculate the ans. This would be the maximum number of envelopes can be russian doll.\n\n\n```\nclass Solution {\npublic:\n    \n    //This compare function going to pass to sort function it should be static function\n\t\n\t// To understand this think that we take two element adjacent to each other a,b both here are vector \n\t\n\t// Based on what you want right return condition \n/* \n\t\tlike  \n\t\t\t1. a<b for ascending ( first element should be less than second )   \n\t\t\t2. a>b for descending ( first element should be greater than second ) \n\n*/\n    static bool cmp(vector<int>& a,vector<int>& b)\n    {\n        if(a[0]==b[0]) //if first val of pair are equal than  for a,b than check for second val of pair\n        {\n            return a[1]>b[1]; // comparing second val of pair in a,b\n        }\n        \n        return a[0]<b[0];\n    }\n    \n    int maxEnvelopes(vector<vector<int>>& envelopes) {\n        \n     \n        \n        sort(envelopes.begin(),envelopes.end(),cmp);\n        \n        vector<int> v;\n        \n        for(auto i: envelopes)\n        {\n            auto it= lower_bound(v.begin(),v.end(),i[1]);\n            \n            if(it== v.end()) // if element greater than i[1] not present than push i[1] here i[1] represent height of envelope\n            {\n                v.push_back(i[1]);\n            }\n            else\n            {\n                *it= i[1]; // if element greater than i[1] not present than replace previous element as it will not impact or LIS \n            }\n        }\n        \n        return v.size();\n        \n    }\n};\n\n\n```
['C', 'Sorting', 'C++']