C++ fast and elegant new idea, 12ms | 100% | time O(k(m+n)) | space O(m+n)
Iteratively (greedily) find the maximal number of x digits that could potentially be extended to k digits (i.e. there are at least k digits left). To determine 
Iteratively (greedily) find the maximal number of x digits that could potentially be extended to k digits (i.e. there are at least k digits left). To determine whether the number can be extended, it suffices to record the index of the last used digit in both numbers (there can be multiple such pairs of indices leading to the same maximal number), and check that there are at least a total of k-x digits left in both numbers. In the following implementation, the indices following the last used digits are recorded in `list_indices`. (Using set instead of vector or list because it can has at most max(m,n) elements, but with repetition it can blow up to 2^x and TLE.)\nTo go from step x to x+1, for each pair of indices in `list_indices`, extend the maximum number by one digit chosen from the ranges starting from those indices. Depending on whether the added digit is from the first or the second number, we get two new pairs of indices (stored in `next_list_indices`). We can throw out those pairs whose corresponding added digits are not maximal.\nIf we index the elements in `list_indices` as (m1,n1), (m2, n2), ... then they can be shown to satisfy m1 > m2 > m3 > ... and n1 < n2 < n3 < ... which shows the size of `list_indices` can be at most max(m,n), so the space complexity is clearly O(m+n). (It helps to plot the indices in a 2D grid.) Further analysis shows that for set insertion we just need to check that the inserted element is not the same as the last inserted element, so we can get rid of a log(m+n) factor for insertion. There are k steps and for each step the total number of indices checked in `getBestIndex` doesn\'t exceed m+n (e.g. if you extend (m1,n1) by one digit from the first number, you get some (m1\',n1) with m1\' <= m2), so the time complexity is O(k(m+n)). With more reasoning you can avoid some of the `getBestIndex` calls under certain conditions, but that doesn\'t lead to improvement on the asymptotic complexity.\n\n```\nclass Solution {\npublic:\n    pair<int,int> getBestIndex(vector<int>& nums, int start, int span) {\n\t// get index and maximum\n        int max_idx = 0;\n        int max_ = nums[start];\n        int i = 1;\n        while (i < span) {\n            auto val = nums[start+i];\n            if (val > max_) {\n                max_idx = i;\n                max_ = val;\n                if (max_ == 9) break;\n            }\n            i++;\n        }\n        return pair<int,int>(max_idx, max_);\n    }\n    \n    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {\n        vector<int> best_seq;\n        set<pair<int,int>> list_indices = {{0,0}};\n        while (k-- > 0) {\n            set<pair<int,int>> next_list_indices;\n            int max_ = -1;\n            for (auto indices : list_indices) {\n                auto n1 = indices.first;\n                auto n2 = indices.second;\n                auto remaining = nums1.size() + nums2.size() - n1 - n2 - k;\n                int idx1, max1 = -1, idx2, max2 = -1;\n                auto remaining1 = min(remaining, nums1.size() - n1);\n                auto remaining2 = min(remaining, nums2.size() - n2);\n                if (remaining1)\n                    tie(idx1, max1) = getBestIndex(nums1, n1, remaining1);\n                if (remaining2)\n                    tie(idx2, max2) = getBestIndex(nums2, n2, remaining2);\n                auto max12 = max(max1, max2);\n                if (max12 < max_) continue;\n                if (max12 > max_) { max_ = max12; next_list_indices.clear(); }\n                if (max1 >= max2) next_list_indices.insert({n1+idx1+1, n2});\n                if (max1 <= max2) next_list_indices.insert({n1, n2+idx2+1});\n            }\n            best_seq.emplace_back(max_);\n            list_indices = move(next_list_indices);\n        }\n        return best_seq;\n    }\n};\n```
[]