**Difficulty: Hard**

**Frequency: N/A**

Given two arrays of length `m`

and `n`

with digits `0-9`

representing two numbers. Create the maximum number of length `k <= m + n`

from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the `k`

digits. You should try to optimize your time and space complexity.

**Example 1:**

nums1 = `[3, 4, 6, 5]`

nums2 = `[9, 1, 2, 5, 8, 3]`

k = `5`

return `[9, 8, 6, 5, 3]`

**Example 2:**

nums1 = `[6, 7]`

nums2 = `[6, 0, 4]`

k = `5`

return `[6, 7, 6, 0, 4]`

**Example 3:**

nums1 = `[3, 9]`

nums2 = `[8, 9]`

k = `3`

return `[9, 8, 9]`

**Test Cases:**

**Solution 1:**

**Data structure:**

**Steps:**

**Complexity:**

**Code:**

class Solution { public: vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) { int n = nums1.size(), m = nums2.size(); vector<int> result; for (int i = max(0, k - m); i <= k && i <= n; i++) { vector<int> tmp = merge(maxArray(nums1, i), maxArray(nums2, k - i), k); if (greater(tmp, 0, result, 0)) result = tmp; } return result; } vector<int> merge(vector<int> nums1, vector<int> nums2, int k) { vector<int> result; for (int i = 0, j = 0, r = 0; r < k; r++) { if (greater(nums1, i, nums2, j)) result.push_back(nums1[i++]); else result.push_back(nums2[j++]); } return result; } bool greater(vector<int> nums1, int i, vector<int> nums2, int j) { while (i < nums1.size() && j < nums2.size() && nums1[i] == nums2[j]) { i++; j++; } return j == nums2.size() || i < nums1.size() && nums1[i] > nums2[j]; } vector<int> maxArray(vector<int> nums, int k) { int n = nums.size(); vector<int> result(k, 0); for (int i = 0, j = 0; i < n; i++) { while (n - i + j > k && j > 0 && result[j - 1] < nums[i]) j--; if (j < k) result[j++] = nums[i]; } return result; } };

**Solution 2:**

**Data structure:**

**steps:**

**Complexity**:

**Code**:

**Submission errors:**

**Things to learn:**