Gives TLE | Longest Increasing Subsequence variant | With explaination
I know this solution gives TLE but for me it seems more intuitive. It may not pass all the cases of this question but you can definitely share it with the inter
# I know this solution gives TLE but for me it seems more intuitive. It may not pass all the cases of this question but you can definitely share it with the interviewer in actual interview.\n\n**Note - Despite two test cases exceeding the time limit, I am sharing the following code as it is more intuitive. You can give this approach in your interview; it sounds more realistic and intuitive.**\n\n# Intuition\nThe problem asks us to find the maximum number of envelopes we can Russian doll, which means we need to find the longest increasing subsequence based on both width and height. To solve this problem efficiently, we can use dynamic programming.\n\n# Approach\n1. Sort the given input array envelopes based on the width of the envelopes in ascending order. Sorting the envelopes based on width ensures that if envelopes[i] can be nested inside envelopes[j], then envelopes[j] will always appear before envelopes[i] in the sorted array.\n2. Create a vector vec of size n, where n is the number of envelopes. Each element of vec will store the length of the longest increasing subsequence that ends at the corresponding envelope.\n3. Iterate through each envelope in envelopes using the outer loop. For each envelope at index i, iterate through all the previous envelopes using the inner loop (from 0 to i-1).\n4. Check if the width and height of envelope envelopes[i] are strictly greater than the width and height of envelope envelopes[j]. If both conditions are satisfied and the length of the subsequence ending at envelopes[j] plus one is greater than the current length of the subsequence ending at envelopes[i], update the length of the subsequence at vec[i] to be one plus the length of the subsequence at vec[j].\n5. After the inner loop, the length of the longest increasing subsequence ending at envelopes[i] will be stored in vec[i].\n6. Iterate through vec and find the maximum length of the subsequence. This represents the maximum number of envelopes that can be Russian dolled.\n7. Return the maximum length.\n\n# Complexity\n- Time complexity:\nThe time complexity of this solution is O(n^2), where n is the number of envelopes. The outer loop runs for n iterations, and the inner loop also runs for a maximum of n iterations.\n\n- Space complexity:\nThe space complexity is O(n) since we are using an additional vector vec of size n to store the lengths of subsequences.\n\n# Code\n```\nclass Solution {\npublic:\n    int maxEnvelopes(vector<vector<int>>& envelopes) {\n        sort(envelopes.begin(),envelopes.end()); // based on width of envelope\n        int n = envelopes.size();\n        vector<int> vec(n,1);\n        for(int  i = 0; i < n; i++)\n        {\n            for(int j = 0 ;  j < i; j++)\n            {\n                if(envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1] && vec[j]+1 > vec[i])\n                {\n                    vec[i] = 1+ vec[j];\n                }\n            }\n        }\n        int ans = 1;\n        for(auto i:vec) ans = max(ans,i);\n        return ans;\n    }\n};\n```
['C++']