321. Create Maximum Number

We need to compute the maximum number of length i from vector one and the maximum number of length k-i from vector two and then merge them together. After enumerating all possible i's, we'll get the maximum number. Therefore, there are two steps to achieve the goal:

1. create maximum number of lengths varying from 0 - k per input vector. This can be done dynamically. For example, for [9, 1, 2, 5, 8, 3], with length  = 5, we remove 1 and get [9, 2, 5, 8, 3]. When computing maximum number of length 4, we don't have to restart computing from the original input. Instead, given maximum number of length 5, we can compute maximum number of length 4 on top of it, i.e. remove 2 and get [9, 5, 8, 3].

2. merge the two maximum numbers. It's similar to merge linked list but with exception. When there are identical numbers in the two maximum numbers, we should move the pointer in the maximum number that hasn't reached the end or has larger digit in the end.

When I revisited this problem, I made mistake in
Line 28: I didn’t carefully think of the case where two numbers are equal. I should move i only when there is no more numbers after equal sequence or the first number after equal sequence in list1 is larger than that in list2.
Line 38: I moved the if-else clause into the while loop.

However, with following solution, I still got TLE. The problem is in line 8-13. Since list1 and list2 contains lists of size from 0 to k and we only care about the merged list of size k, so we only need to check pairs in list1 and list2 that can be merged to size k. Instead of traversing all pairs in list1 and list2, we only need to check pairs of nums of size i in list1 and nums of size k-i in list2.

1:  class Solution {  
2:  public:  
3:    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {  
4:      vector<vector<int>> dp1(k+1), dp2(k+1);  
5:      vector<int> res(k), tmp_result(k);  
6:      genDP(nums1, dp1, k);  
7:      genDP(nums2, dp2, k);  
8:      for (int i = 0; i <= k; i++) {  
9:        if (dp1[i].size() + dp2[k-i].size() < k) continue;  
10:        merge(dp1[i], dp2[k-i], tmp_result);  
11:        if (compare(tmp_result, res)) res = tmp_result;  
12:      }  
13:      return res;  
14:    }  
15:  private:  
16:    void genDP(vector<int>& nums, vector<vector<int>> &dp, int k) {  
17:      int start, i = 0;  
18:      for (start = 0; nums.size() > 0; start = (i == 0 ? 0 : i-1)) {  
19:        if (nums.size() <= k) {  
20:          dp[nums.size()] = nums;  
21:        }  
22:        for (i = start; i+1 < nums.size() && nums[i] >= nums[i+1]; i++);  
23:        nums.erase(nums.begin() + i);  
24:      }  
25:    }  
26:    void merge(vector<int> &nums1, vector<int> &nums2, vector<int> &res) {  
27:      int i = 0, j = 0, k = 0;  
28:      int ii = 0, jj = 0;  
29:      for (; i < nums1.size() && j < nums2.size(); k++) {  
30:        for (ii = i, jj = j; ii < nums1.size() && jj < nums2.size() && nums1[ii] == nums2[jj]; ii++, jj++);  
31:        if (jj == nums2.size() || ii < nums1.size() && nums1[ii] > nums2[jj]) {  
32:          res[k] = nums1[i];  
33:          i++;  
34:        } else {  
35:          res[k] = nums2[j];  
36:          j++;  
37:        }  
38:      }  
39:      while (i < nums1.size()) {  
40:        res[k++] = nums1[i++];  
41:      }  
42:      while (j < nums2.size()) {  
43:        res[k++] = nums2[j++];  
44:      }  
45:    }  
46:    int compare(vector<int> &nums1, vector<int> &nums2) {  
47:      int i = 0;  
48:      for (;i < nums1.size() && nums1[i] == nums2[i]; i++);  
49:      if (nums1[i] > nums2[i]) return 1;  
50:      else return 0;  
51:    }
52:  };