✅[C++] Intuition w/reference question | Stack and Merge sort Concept
\nThis question is a combination of multiple topics and also one of the best question i have encountered so far. \nBefore solving this question, you need have k
\nThis question is a combination of multiple topics and also one of the best question i have encountered so far. \nBefore solving this question, you need have knowledge about merge sort technique and also you need to solve its prerequisite question ([1673. Find the Most Competitive Subsequence](https://leetcode.com/problems/find-the-most-competitive-subsequence/))\n\nFirst, Try that question and if you dont get any intuition, don\'t feel bad. Even i took some help. You can read its editorial from [here](https://leetcode.com/problems/find-the-most-competitive-subsequence/discuss/1903056/C%2B%2B-Stack-Solution-intuition-or-Monotonic-Stack)\n\n***Basic Idea*** of this problem is that we have two arrays, so we find the largest \'i\' digit number from nums1 and largest \'k-i\' digit number from nums2. After having these two, we merge them using merge sort algorithm. We use merge sort because it can be proved that largest number will always be sorted in descending order. The only thing to keep in mind while merging is the case where array elements are equal. In that case, we have to loop untill we find a greater element in one of the two arrays and then act accordingly.\n            So after finding a i digit number from nums1 and k-i digit number from nums2, we merge them to form the maximum k digit number from these two arrays.\n\n\n```\nclass Solution {\npublic:\n    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {\n        vector <int>res;\n\n        for(int i = 0; i<=k; i++){\n            vector <int> a = fun(nums1, i);\n            vector <int> b = fun(nums2, k-i);\n\n            vector <int> m;\n            merge(a, b, m);\n\n            if(m.size()==k) res = max(res,m);\n        }\n        return res;\n    }\nprotected:\n    // This function is the code of "Find most consecutive subsequence" problem, which finds the k digit maximum number possible\n    vector <int> fun(vector <int>&nums, int k){\n        if(k>nums.size()) return {};\n        vector <int> res;\n        stack <int> st;\n        int rem = k, n = nums.size();\n        for(int i = 0; i<n; i++){\n            if(st.empty()) st.push(nums[i]), rem--;\n            else{\n                int avail = n-i;\n                while(!st.empty() and st.top()<nums[i] and rem<k and avail>rem) st.pop(), rem++;\n                st.push(nums[i]), rem--;\n            }\n        }\n        while(st.size()>k) st.pop();\n        while(!st.empty()) res.push_back(st.top()), st.pop();\n        reverse(res.begin(), res.end());\n        return res;\n    }\n    void merge(vector <int>&a, vector <int>&b, vector <int>&res){\n        int i = 0, j = 0, k = 0;\n        // This is the only case which we need to take care of. Here, we loop until we find a number greater than another number\n        // in other array. When we do that, we push the element in result array accordingly. Note that i am not using the pointer\n        // i and j to loop, instead i have creater a temporary pointers which finds the position where elements are different.\n        while(i<a.size() and j<b.size()){\n            if(a[i]==b[j]){\n                int ti = i, tj = j;\n                while(ti<a.size() and tj<b.size() and a[ti]==b[tj]) ti++, tj++;\n\n                if(tj==b.size()) res.push_back(a[i]), i++;\n                else\n                if(ti<a.size() and a[ti]>b[tj]) res.push_back(a[i]), i++;\n                else res.push_back(b[j]), j++;\n            }\n            else\n            if(a[i]>b[j]) res.push_back(a[i]), i++;\n            else res.push_back(b[j]), j++;\n        }\n        while(i<a.size()) res.push_back(a[i]), i++;\n        while(j<b.size()) res.push_back(b[j]), j++;\n    }\n};\n```
['Stack', 'C', 'C++']