C++ A horrible but efficient solution
The idea is to build a binary tree based on sorted indices. The binary tree definition is as follows:\n\n\nstruct MyTreeNode{\n\xA0 \xA0 MyTreeNode(int idx, int
The idea is to build a binary tree based on sorted indices. The binary tree definition is as follows:\n\n```\nstruct MyTreeNode{\n\xA0 \xA0 MyTreeNode(int idx, int val): idx(idx), val(val), left(nullptr), right(nullptr){}\n\xA0\n\xA0 \xA0 int idx;\n\xA0 \xA0 int val;\n\xA0 \xA0 \n\xA0 \xA0 MyTreeNode * left;\n\xA0 \xA0 MyTreeNode * right;\n};\n```\n\nTha property val holds the value and idx holds the corresponding inex.\nWe build a binary tree from each of the input arrays as follows. First we pick the largest element in the vector. Suppose it has index i. We create the root node from it. The index i splits the vector into two  (not necessarily equal) parts. The right node of the root is the largest element on the right side, i.e. max(nums[j] ) j>i and the left one is the largest in the left side.  \n\nThe code that builds the binary tree looks as follows:\n\n```\nMyTreeNode * getTree( const vector<int>& nums){\n\xA0 \xA0 \xA0 \xA0 if(nums.empty())\n\xA0 \xA0 \xA0 \xA0 \xA0 \xA0 return nullptr;\n\t\t\t\n\xA0 \xA0 \xA0 \xA0 vector<int> indices(nums.size());\n\xA0 \xA0 \xA0 \xA0 for(int i = 0; i < indices.size(); ++i)\n\xA0 \xA0 \xA0 \xA0 \xA0 \xA0 indices[i] = i;\n\xA0 \xA0 \xA0 \xA0 \n\t\t// after this the vector indices will hold the indices that sort nums in descending order\n\xA0 \xA0 \xA0 \xA0 sort(indices.begin(), indices.end(), [&](const int & a, const int &b){ if(nums[a] == nums[b]) return a <b; else return nums[a] > nums[b]; });\n\xA0 \xA0 \xA0 \xA0 \xA0 \xA0 \n\xA0 \xA0 \xA0 \xA0 MyTreeNode * head = new MyTreeNode(indices[0], nums[indices[0]]); \xA0 \xA0 \xA0\n\xA0 \xA0 \xA0 \xA0 for(int i = 1; i < indices.size(); ++i)\n\xA0 \xA0 \xA0 \xA0 \xA0 \xA0 insert(head, indices[i], nums[indices[i]]);\n\xA0 \xA0 \xA0 \xA0 return head;\n\xA0 \xA0 \xA0 \xA0 \xA0 \xA0 \n\xA0 \xA0 }\n\xA0 \xA0 \n\xA0 \xA0 void insert(MyTreeNode * head, int idx, int val){\n\xA0 \xA0 \xA0 \xA0 if(idx > head->idx) {\n\xA0 \xA0 \xA0 \xA0 \xA0 \xA0 if(head->right)\n\xA0 \xA0 \xA0 \xA0 \xA0 \xA0 \xA0 \xA0 insert(head->right, idx, val);\n\xA0 \xA0 \xA0 \xA0 \xA0 \xA0 else\n\xA0 \xA0 \xA0 \xA0 \xA0 \xA0 \xA0 \xA0 head->right = new MyTreeNode(idx, val);\n\xA0 \xA0 \xA0 \xA0 }\n\xA0 \xA0 \xA0 \xA0 else\n\xA0 \xA0 \xA0 \xA0 {\n\xA0 \xA0 \xA0 \xA0 \xA0 \xA0 if(head->left)\n\xA0 \xA0 \xA0 \xA0 \xA0 \xA0 \xA0 \xA0 insert(head->left, idx, val);\n\xA0 \xA0 \xA0 \xA0 \xA0 \xA0 else\n\xA0 \xA0 \xA0 \xA0 \xA0 \xA0 \xA0 \xA0 head->left = new MyTreeNode(idx, val);\n\xA0 \xA0 \xA0 \xA0 }\n\xA0 \xA0 }\n```\n\nHaving the corresponding tree it easy to find the next candidate element to pick. For each array we keep the last picked index idx1 ord idx2. \n\nWe start from the root of each tree. The candidate node should have idx value greater than the last picked index. So, if for any node *cur* this condition is not satisfyed we move to its right child.  On the other hand, the element can be so much right in the array, that the number of the remaining items is not enough for filling the resulting vector with k elements. If this is the case then we move to the left. As soon as we arrive to a node, we can be sure that it is the largest node that satifies both requirements.\n\nThe code for this navigation reads:\n\n```\nMyTreeNode * \xA0getCandidate(MyTreeNode * node, int idx1, int remaining_items){\n\xA0 \xA0 while(node){\xA0 \xA0 \xA0 \xA0 \xA0 \n\xA0 \xA0 \xA0 \xA0 if(remaining_items \xA0- \xA0node->idx < 0)\n\xA0 \xA0 \xA0 \xA0 \xA0 \xA0 node = node->left;\n\xA0 \xA0 \xA0 \xA0 else if (node->idx <= idx1 )\n\xA0 \xA0 \xA0 \xA0 \xA0 \xA0 node = node->right;\n\xA0 \xA0 \xA0 \xA0 else \n\xA0 \xA0 \xA0 \xA0 \xA0 \xA0 break;\n \xA0 }\n\xA0 \xA0return node;\n}\n```\n\n**Solution with no collisions** (Attention: this one is not accepted).\n\n```\nclass Solution{\npublic:\n   vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {\n        MyTreeNode * t1 = getTree(nums1);\n\xA0 \xA0 \xA0 \xA0 MyTreeNode * t2 = getTree(nums2);\n\xA0 \xA0 \xA0 \xA0 vector<int> result;\n\t\t\n\t\tint idx1 = -1, idx2 = -1;\n\t\twhile(k > result.size()){\n\t\t    MyTreeNode * cur1 = getCandidate(t1, idx1, nums1.size() \xA0+ nums2.size() - idx2 -1 - k + result.size());\n\xA0 \xA0 \xA0 \xA0 \xA0 \xA0 MyTreeNode * cur2 = getCandidate(t2, idx2, nums1.size() \xA0+ nums2.size() - idx1 -1 - k + result.size());\n\t\t\t\n\t\t\t// We then merge sort these trees into the result\n\t\t\tif(cur1 && cur2){\n\t\t\t    if(cur1->val == cur2->val){\n\t\t\t\t    // this one is tricky so let us for a moment assume that we do not encounter such cases\n\t\t\t\t}\n\t\t\t\telse if(cur1->val > cur2->val){\n\t\t\t\t    // Move the last picked index of the first array \n\t\t\t\t    idx1 = cur1->idx;\n\t\t\t\t\t// Append to the result\n\t\t\t\t\tresult.push_back(cur1->val);\n\t\t\t\t}\n\t\t\t\telse {\n\t\t\t\t    idx2 = cur2->idx;\n\t\t\t\t\tresult.push_back(cur2->val);\n\t\t\t\t}\n\t\t\t}\n\t\t\telse if(cur1){\n\t\t\t     idx1 = cur1->idx;\n\t\t\t     result.push_back(cur1->val);\n\t\t\t}\n\t\t\telse{\n\t\t\t    idx2 = cur2->idx;\n\t\t\t\tresult.push_back(cur2->val);\t\t\t\n\t\t\t}\n\t\t}\n\n    }\n\n};\n```\n\nThe problem arises when the values of the candidate nodes are equal. I could not find a better solution to this rather than to maintain all possible paths until at some stage some of the paths give a smaller value to pick. For this reason let us introduce\n\n```\nstruct State{\n\xA0 \xA0 State(int idx1, int idx2, int value=numeric_limits<int>::min()): idx1(idx1), idx2(idx2), max_value(value){}\n\t\n\tint idx1;\n\xA0 \xA0 int idx2; \xA0 \n\xA0 \xA0 int max_value;\n\t\n    bool operator ==(const State & other) const {\n        return idx1 == other.idx1 && idx2 == other.idx2;\n    }\n};\n```\n\n\nAnd the code becomes (ugly!!!):\n\n```\nclass Solution{\npublic:\n   vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {\n        MyTreeNode * t1 = getTree(nums1);\n\xA0 \xA0 \xA0 \xA0 MyTreeNode * t2 = getTree(nums2);\n\xA0 \xA0 \xA0 \xA0 vector<int> result;\n\t\t\n\t\tlist<State> states;\xA0 \xA0 \xA0 \xA0 \n\xA0 \xA0 \xA0 \xA0 states.push_front (State(-1,-1));\n\t\t\n\t\tint idx1 = -1, idx2 = -1;\n\t\twhile(k > result.size()){\n\t\t    int max_value = numeric_limits<int>::min();\n\t\t\tlist<State> states_to_add;\n\t\t    for(State & st: states){\n\n                MyTreeNode * cur1 = getCandidate(t1, st.idx1, nums1.size() \xA0+ nums2.size() - st.idx2 -1 - k + result.size());\n\xA0 \xA0 \xA0 \xA0 \xA0 \xA0     MyTreeNode * cur2 = getCandidate(t2, st.idx2, nums1.size() \xA0+ nums2.size() - st.idx1 -1 - k + result.size());\n\t\t\t\n\t\t\t    // We then merge sort these trees into the result\n\t\t\t    if(cur1 && cur2){\n\t\t\t        if(cur1->val == cur2->val){\n\t\t\t\t        // We create 2 new states instead of one so that the comuptation will be done for both possible paths\n\t\t\t\t\t\tmax_value  = max(max_value, cur1->val );\n\t\t\t\t\t\tstates_to_add.push_front(State(cur1->idx, st.idx2, cur1->value));\n\t\t\t\t\t\tstates_to_add.push_front(State(st.idx1, cur2->idx, cur2->value));\n\t\t\t\t\t\t\n\t\t\t\t\t\t// We set this so it is removed in below\n\t\t\t\t\t\tst.max_value = numeric_limits<int>::min();\n\t\t\t\t    }\n\t\t\t\t    else if(cur1->val > cur2->val){\t\t\t\t    \n\t\t\t\t        st.idx1 = cur1->idx;\t\t\t\t\t\n\t\t\t\t\t    max_value  = max(max_value, cur1->val );\n\t\t\t\t\t    st.max_value = cur1->val;\n\t\t\t\t    }\n\t\t\t\t    else {\n\t\t\t\t         st.idx2 = cur2->idx;\t\t\t\t\t\n\t\t\t\t\t     max_value  = max(max_value, cur2->val );\n\t\t\t\t\t     st.max_value = cur2->val;\n\t\t\t\t    }\n\t\t\t    }\n\t\t\t    else if(cur1){\n\t\t\t        st.idx1 = cur1->idx;\t\t\t\t\t\n\t\t\t\t    max_value  = max(max_value, cur1->val );\n\t\t\t\t    st.max_value = cur1->val;\n\t\t\t    }\n\t\t\t    else{\n\t\t\t        st.idx2 = cur2->idx;\t\t\t\t\t\n\t\t\t\t    max_value  = max(max_value, cur2->val );\n\t\t\t\t    st.max_value = cur2->val;\t\n\t\t\t    }\n\t\t\t\n\t\t\t}\n\t\t    result.push_back(max_value);\n\t\t\t// We should remove all the states which are doing worse than the best one\xA0 \xA0 \xA0 \xA0 \xA0 \xA0 \n            states.remove_if([&](const State & st){return st.max_value < max_value;});\n\t\t\t\n\t\t\t// Add newly create states\n\t\t\tfor(State st: states_to_add)\n\xA0 \xA0 \xA0 \xA0 \xA0 \xA0 \xA0 \xA0 if(st.max_value == max_value)\n\xA0 \xA0 \xA0 \xA0 \xA0 \xA0 \xA0 \xA0 \xA0 \xA0 states.push_front(st);\n\t\t}\n\n    }\n\n};\n```\n\nIt turns out, however, that the picking paths are not unique and states can merge later. I was lazy to find a good solution for this so just copy-pasted a similar code from one of my projects. We just add hashing function to the std namespace (outside any scope )\n\n```\nnamespace std{\ntemplate<>\nstruct hash<State> {\n  std::size_t operator()(const State & state) const noexcept {\n    std::hash<int> hasher;\n    size_t seed = hasher(state.idx1);\n\t// from boost\n    seed ^= hasher(state.idx2) + 0x9e3779b9 + (seed<<6) + (seed>>2);\n    return seed;\n  }\n};\n}\n```\n\nAnd at the very end of the while(k > result.size()) loop just add this stupid code \n\n```\nunordered_set<State> unique_states(states.begin(), states.end());\nif(unique_states.size()!= states.size()){\n    states.clear();\n    for(const State &st: unique_states)\n        states.push_front(st);\n}\n```\n\n\nI will appretiate if someone points a good way to tackle the state problem and/or any other comments
[]