Problem

Given 2 integer arrays nums1 and nums2 consisting only of 0 and 1, your task is to calculate the minimum possible largest number in arrays nums1 and nums2, after doing the following.

Replace every 0 with an even positive integer and every 1 with an odd positive integer. After replacement, both arrays should be increasing and each integer should be used at most once.

Return the minimum possible largest number after applying the changes.

Examples

Example 1:

1
2
3
4

Input: nums1 = [], nums2 = [1,0,1,1]
Output: 5
Explanation:
After replacing, `nums1 = []`, and `nums2 = [1, 2, 3, 5]`.

Example 2:

1
2
3
4
5

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

Example 3:

1
2
3
4
5

Input: nums1 = [0,1,0,0,1], nums2 = [0,0,0,1]
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

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

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int minLargestNumber(vector<int>& nums1, vector<int>& nums2) {
        vector<int> arr[2];
        for (int x : nums1) arr[x].push_back(0);
        for (int x : nums2) arr[x].push_back(1);
        int n0 = arr[0].size(), n1 = arr[1].size();
        vector<int> even, odd;
        for (int i = 2; even.size() < n0; i += 2) even.push_back(i);
        for (int i = 1; odd.size() < n1; i += 2) odd.push_back(i);
        int ans = 0, i0 = 0, i1 = 0;
        for (int x : nums1) {
            if (x == 0) ans = max(ans, even[i0++]);
            else ans = max(ans, odd[i1++]);
        }
        for (int x : nums2) {
            if (x == 0) ans = max(ans, even[i0++]);
            else ans = max(ans, odd[i1++]);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func MinLargestNumber(nums1, nums2 []int) int {
    n0, n1 := 0, 0
    for _, x := range nums1 { if x == 0 { n0++ } else { n1++ } }
    for _, x := range nums2 { if x == 0 { n0++ } else { n1++ } }
    even, odd := make([]int, n0), make([]int, n1)
    for i, v := 0, 2; i < n0; i, v = i+1, v+2 { even[i] = v }
    for i, v := 0, 1; i < n1; i, v = i+1, v+2 { odd[i] = v }
    ans, i0, i1 := 0, 0, 0
    for _, x := range nums1 {
        if x == 0 { ans = max(ans, even[i0]); i0++ } else { ans = max(ans, odd[i1]); i1++ }
    }
    for _, x := range nums2 {
        if x == 0 { ans = max(ans, even[i0]); i0++ } else { ans = max(ans, odd[i1]); i1++ }
    }
    return ans
}
func max(a, b int) int { if a > b { return a } else { return b } }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int minLargestNumber(int[] nums1, int[] nums2) {
        int n0 = 0, n1 = 0;
        for (int x : nums1) if (x == 0) n0++; else n1++;
        for (int x : nums2) if (x == 0) n0++; else n1++;
        int[] even = new int[n0], odd = new int[n1];
        for (int i = 0, v = 2; i < n0; i++, v += 2) even[i] = v;
        for (int i = 0, v = 1; i < n1; i++, v += 2) odd[i] = v;
        int ans = 0, i0 = 0, i1 = 0;
        for (int x : nums1) {
            if (x == 0) ans = Math.max(ans, even[i0++]);
            else ans = Math.max(ans, odd[i1++]);
        }
        for (int x : nums2) {
            if (x == 0) ans = Math.max(ans, even[i0++]);
            else ans = Math.max(ans, odd[i1++]);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun minLargestNumber(nums1: IntArray, nums2: IntArray): Int {
        var n0 = 0; var n1 = 0
        for (x in nums1) if (x == 0) n0++ else n1++
        for (x in nums2) if (x == 0) n0++ else n1++
        val even = IntArray(n0) { 2 * (it + 1) }
        val odd = IntArray(n1) { 2 * it + 1 }
        var ans = 0; var i0 = 0; var i1 = 0
        for (x in nums1) {
            if (x == 0) { ans = maxOf(ans, even[i0]); i0++ } else { ans = maxOf(ans, odd[i1]); i1++ }
        }
        for (x in nums2) {
            if (x == 0) { ans = maxOf(ans, even[i0]); i0++ } else { ans = maxOf(ans, odd[i1]); i1++ }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def minLargestNumber(self, nums1: list[int], nums2: list[int]) -> int:
        n0 = nums1.count(0) + nums2.count(0)
        n1 = nums1.count(1) + nums2.count(1)
        even = [2 * (i + 1) for i in range(n0)]
        odd = [2 * i + 1 for i in range(n1)]
        ans, i0, i1 = 0, 0, 0
        for x in nums1:
            if x == 0:
                ans = max(ans, even[i0]); i0 += 1
            else:
                ans = max(ans, odd[i1]); i1 += 1
        for x in nums2:
            if x == 0:
                ans = max(ans, even[i0]); i0 += 1
            else:
                ans = max(ans, odd[i1]); i1 += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn min_largest_number(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let n0 = nums1.iter().filter(|&&x| x == 0).count() + nums2.iter().filter(|&&x| x == 0).count();
        let n1 = nums1.iter().filter(|&&x| x == 1).count() + nums2.iter().filter(|&&x| x == 1).count();
        let even: Vec<i32> = (1..=n0).map(|i| 2 * i as i32).collect();
        let odd: Vec<i32> = (0..n1).map(|i| 2 * i as i32 + 1).collect();
        let mut ans = 0; let mut i0 = 0; let mut i1 = 0;
        for &x in &nums1 {
            if x == 0 { ans = ans.max(even[i0]); i0 += 1; } else { ans = ans.max(odd[i1]); i1 += 1; }
        }
        for &x in &nums2 {
            if x == 0 { ans = ans.max(even[i0]); i0 += 1; } else { ans = ans.max(odd[i1]); i1 += 1; }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    minLargestNumber(nums1: number[], nums2: number[]): number {
        const n0 = nums1.filter(x => x === 0).length + nums2.filter(x => x === 0).length;
        const n1 = nums1.filter(x => x === 1).length + nums2.filter(x => x === 1).length;
        const even = Array.from({length: n0}, (_, i) => 2 * (i + 1));
        const odd = Array.from({length: n1}, (_, i) => 2 * i + 1);
        let ans = 0, i0 = 0, i1 = 0;
        for (const x of nums1) {
            if (x === 0) ans = Math.max(ans, even[i0++]);
            else ans = Math.max(ans, odd[i1++]);
        }
        for (const x of nums2) {
            if (x === 0) ans = Math.max(ans, even[i0++]);
            else ans = Math.max(ans, odd[i1++]);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the total length of nums1 and nums2. Each element is processed once.
  • 🧺 Space complexity: O(n), for the even/odd arrays.