Greedy | Intuitive | Detailed Explanation
Intuition\n\nThis question is basically a combo of monotonic stack and merging two arrays.\n\nSo, to create a maximum number of k size array, we will iterate ov
# Intuition\n\nThis question is basically a combo of monotonic stack and merging two arrays.\n\nSo, to create a maximum number of k size array, we will iterate over the first array to take the size of largest possible number and correspondingly we will take the (k-i) size of largest possible number from the second array.\nAfter storing the largest arrays in n1 and n2 we are merging them using merge function and then taking maximum of all.\n\n```\n    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {\n        int n = nums1.size(), m = nums2.size();\n        string mx = "";\n        for(int i = 0; i <= k && i <= n; i++){\n            if((k-i) > m) continue; //If we are taking i size of largest array from nums1 then are we capable of building k-i size of largest array from num2 .\n            vector<int> n1 = maxnum(nums1, i);\n            vector<int> n2 = maxnum(nums2, k-i);\n            string s = merge(n1, n2, k);\n            mx = max(mx, s);\n        }\n        vector<int> res;\n        for(int i = 0; i < mx.size(); i++) res.push_back(mx[i] - \'0\');\n        return res;\n    }\n```\n\nThis is the code to calculate the largest possible number of kth size from array nums. This is based on monotonic stack.\n\nSimilar question(Same logic): https://leetcode.com/submissions/detail/950762503/\n\n```\n    vector<int> maxnum(vector<int> nums, int k){\n        stack<int> st;\n        int n = nums.size();\n        for(int i = 0; i < n; i++){\n            while(!st.empty() && nums[st.top()] < nums[i] && n - i + st.size() > k) st.pop();\n            if(st.size() < k) st.push(i);\n        }\n        vector<int> ans;\n        while(!st.empty()) ans.push_back(nums[st.top()]), st.pop();\n        reverse(ans.begin(), ans.end());\n        return ans;\n    }\n\n\n\n``` \n\nSo, here we are merging both the arrays.\nIf element of n2 is greater then we will simply take its value in the ans array and vice versa (similar to merging of merge sort).\n\n**Most Important**\nWhen we will encounter equal values in n1 and n2 then we will simply increment both the indices.\n\n`nums1 = [5,0,2,1,0,1,0,3,9,1,2,8,0,9,8,1,4,7,3],\nnums2 = [7,6,7,1,0,1,0,5,6,0,5,0],\nk = 31`\n\nYou can dry run on this test case.\n\n```\n    string merge(vector<int>& n1, vector<int>& n2, int k){\n        vector<int> ans(k, 0);\n         int i = 0, j = 0, x = 0;\n            while(i < n1.size() && j < n2.size()){\n                if(n2[j] > n1[i]) ans[x++] = n2[j], j++;\n                else if(n2[j] == n1[i]){\n                    int indi=i, indj=j;\n                    while(indi < n1.size() && indj < n2.size() && n1[indi] == n2[indj]) indi++, indj++;\n                    if(indj == n2.size()) ans[x++] = n1[i], i++;\n                    else{\n                        if(indi < n1.size() && n1[indi] > n2[indj]) ans[x++] = n1[i], i++;\n                        else ans[x++] = n2[j], j++;\n                    }\n                }\n\n                else ans[x++] = n1[i], i++; \n            }\n            while(i < n1.size()) ans[x++] = n1[i], i++;\n            while(j < n2.size()) ans[x++] = n2[j], j++;\n            string s = "";\n            for(auto it: ans) s += to_string(it);\n            return s;\n    }\n```\n\n\n\n# Complete Code\n```\nclass Solution {\npublic:\n\n    vector<int> maxnum(vector<int> nums, int k){\n        stack<int> st;\n        int n = nums.size();\n        for(int i = 0; i < n; i++){\n            while(!st.empty() && nums[st.top()] < nums[i] && n - i + st.size() > k) st.pop();\n            if(st.size() < k) st.push(i);\n        }\n        vector<int> ans;\n        while(!st.empty()) ans.push_back(nums[st.top()]), st.pop();\n        reverse(ans.begin(), ans.end());\n        return ans;\n    }\n\n    string merge(vector<int>& n1, vector<int>& n2, int k){\n        vector<int> ans(k, 0);\n         int i = 0, j = 0, x = 0;\n            while(i < n1.size() && j < n2.size()){\n                if(n2[j] > n1[i]) ans[x++] = n2[j], j++;\n                else if(n2[j] == n1[i]){\n                    int indi=i, indj=j;\n                    while(indi < n1.size() && indj < n2.size() && n1[indi] == n2[indj]) indi++, indj++;\n                    if(indj == n2.size()) ans[x++] = n1[i], i++;\n                    else{\n                        if(indi < n1.size() && n1[indi] > n2[indj]) ans[x++] = n1[i], i++;\n                        else ans[x++] = n2[j], j++;\n                    }\n                }\n\n                else ans[x++] = n1[i], i++; \n            }\n            while(i < n1.size()) ans[x++] = n1[i], i++;\n            while(j < n2.size()) ans[x++] = n2[j], j++;\n            string s = "";\n            for(auto it: ans) s += to_string(it);\n            return s;\n    }\n\n    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {\n        int n = nums1.size(), m = nums2.size();\n        string mx = "";\n        for(int i = 0; i <= k && i <= n; i++){\n            if((k-i) > m) continue; //If we are taking i size of largest array from nums1 then are we capable of building k-i size of largest array from num2 .\n            vector<int> n1 = maxnum(nums1, i);\n            vector<int> n2 = maxnum(nums2, k-i);\n            string s = merge(n1, n2, k);\n            mx = max(mx, s);\n        }\n        vector<int> res;\n        for(int i = 0; i < mx.size(); i++) res.push_back(mx[i] - \'0\');\n        return res;\n    }\n};\n\n```
['Greedy', 'Monotonic Stack', 'C++']