Greedy Solution | Time Complexity O(N^2) | Space Complexity O(N) | With Comments
Basic idea is to find best answer from nums1 with size i  and from nums2 with size k-i. Then we merge the two arrays, the merge function has been optimized to b
Basic idea is to find best answer from nums1 with size `i`  and from `nums2` with size `k-i`. Then we merge the two arrays, the merge function has been optimized to be `O(N)` . Overall Complexity is `O(N^2)`\n\n```\nclass Solution {\npublic:\n    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {\n        vector<int> answer(k);\n        int n1 = nums1.size();\n        int n2 = nums2.size();\n        for(int i = 0; i <= k; i++) {\n            int j = k - i;\n            if (i <= n1 && j <= n2) {\n                vector<int> ans1 = maxSingleNumber(nums1, i); // best of size i - O(n)\n                vector<int> ans2 = maxSingleNumber(nums2, j); // best of size k - i - O(n)\n                vector<int> ans = merge(ans1, ans2); // merging both - O(n)\n               \n                answer = max(ans, answer); // maximize answer - O(n)\n            }\n        }\n        return answer;\n    }\n    \n    vector<int> merge(vector<int>& nums1, vector<int>& nums2) {\n        vector<int> ans; \n        \n        int i = 0;\n        int j = 0;\n        int k = 0; \n\n        int n1 = nums1.size();\n        int n2 = nums2.size();\n        \n        // Eventhough there are two nested loops, I believe this is linear as the second loop can only run once per element\n        while(i<n1 && j<n2) {\n            if (nums1[i] > nums2[j])\n                ans.push_back(nums1[i++]);\n            else if (nums1[i] < nums2[j])\n                ans.push_back(nums2[j++]);\n            else { // Both are equal, we need to pick the one that is better in the future\n                int i1 = i + 1;\n                int j1 = j + 1;\n                int larger = 0; \n                \n                while(i1<n1 && j1 < n2 && !larger) {\n                    if(nums1[i1] == nums2[j1]) {\n                        if (nums1[i1] < nums1[i]) // This number is less than the current stopping position, so we would pick that instead \n                            break;\n                        i1++;\n                        j1++;\n                    }\n                    else if (nums1[i1] > nums2[j1]) // nums1 is better to pick \n                        larger = -1;\n                    else\n                        larger = 1;  // nums2 is better to pick \n                }\n                \n                if (i1 == n1)\n                    larger = 1;\n                if (j1 == n2)\n                    larger = -1;\n                \n                if (larger == -1)\n                    ans.push_back(nums1[i++]);\n                else \n                    ans.push_back(nums2[j++]);\n            }\n        }\n            \n        // Push Remaining elements\n        while(i<n1)\n            ans.push_back(nums1[i++]);\n        \n        while(j<n2)\n            ans.push_back(nums2[j++]);\n        \n        return ans;\n            \n                \n    }\n    \n    vector<int> maxSingleNumber(vector<int>& nums1, int k) {\n        \n        vector<int> stack; \n        int n = nums1.size();\n        for(int i = 0; i < n; i++) {\n            // Pop elements from the stack if current element is greater than head of the stack\n            // We can pop only if remaining elements in nums1 + remaining elements in stack \n            // after popping is greater than or equal to k\n            while(!stack.empty() && (stack.back() < nums1[i] && (stack.size() -1) + (n-i) >=k ))\n                stack.pop_back();\n            \n            // Push if less than k elements\n            if (stack.size() < k)\n                stack.push_back(nums1[i]);\n        }\n        return stack;\n    }\n    \n};\n```
[]