Output: 13 Explanation: One way to replace, having 13 as the largest element is `nums1 = [2, 3, 4, 6, 7]`, and `nums2 = [8, 10, 12, 13]`.

Constraints:

0 <= nums1.length <= 1000
1 <= nums2.length <= 1000
nums1 and nums2 consist only of 0 and 1.

Solution

Method 1 – Greedy Assignment with Set

Intuition

We need to assign even positive integers to 0s and odd positive integers to 1s in both arrays, such that both arrays are strictly increasing and each integer is used at most once. The goal is to minimize the largest number used. The greedy approach is to assign the smallest available even/odd numbers to each position, maintaining the increasing property.

Approach

Count the number of 0s and 1s in both arrays.
For each array, create a list of positions for 0s and 1s.
Assign the smallest available even numbers to 0s and the smallest available odd numbers to 1s, ensuring the sequence is strictly increasing.
Use a set to keep track of used numbers.
The answer is the largest number assigned.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int minLargestNumber(vector<int>& nums1, vector<int>& nums2) {\n        vector<int> arr[2];\n        for (int x : nums1) arr[x].push_back(0);\n        for (int x : nums2) arr[x].push_back(1);\n        int n0 = arr[0].size(), n1 = arr[1].size();\n        vector<int> even, odd;\n

Related Tags