Skip to content

3269. Constructing Two Increasing Arrays πŸ”’

DifficultyHard

Description

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.

 

Example 1:

Input: nums1 = [], nums2 = [1,0,1,1]

Output: 5

Explanation:

After replacing, nums1 = [], and nums2 = [1, 2, 3, 5].

Example 2:

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:

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.

Solutions

Solution 1: Dynamic Programming

Thinking

Two arrays must become strictly increasing with prescribed parities, minimizing the final maximum. \(m,n\le 1000\) would allow guessing that maximum, but filling has optimal substructure.

\(f[i][j]\) is the smallest achievable maximum after \(i\) values of \(nums1\) and \(j\) of \(nums2\). The next write attaches to one array the least integer larger than the current maximum with the right parity. Boundaries follow one array; the interior takes the better of the two attachments.

We define \(f[i][j]\) to represent the minimum of the maximum values among the first \(i\) elements of array \(\textit{nums1}\) and the first \(j\) elements of array \(\textit{nums2}\). Initially, \(f[i][j] = 0\), and the answer is \(f[m][n]\), where \(m\) and \(n\) are the lengths of arrays \(\textit{nums1}\) and \(\textit{nums2}\), respectively.

If \(j = 0\), then the value of \(f[i][0]\) can only be derived from \(f[i - 1][0]\), with the transition equation \(f[i][0] = \textit{nxt}(f[i - 1][0], \textit{nums1}[i - 1])\), where \(\textit{nxt}(x, y)\) represents the smallest integer greater than \(x\) that has the same parity as \(y\).

If \(i = 0\), then the value of \(f[0][j]\) can only be derived from \(f[0][j - 1]\), with the transition equation \(f[0][j] = \textit{nxt}(f[0][j - 1], \textit{nums2}[j - 1])\).

If \(i > 0\) and \(j > 0\), then the value of \(f[i][j]\) can be derived from both \(f[i - 1][j]\) and \(f[i][j - 1]\), with the transition equation \(f[i][j] = \min(\textit{nxt}(f[i - 1][j], \textit{nums1}[i - 1]), \textit{nxt}(f[i][j - 1], \textit{nums2}[j - 1]))\).

Finally, return \(f[m][n]\).

The time complexity is \(O(m \times n)\), and the space complexity is \(O(m \times n)\). Here, \(m\) and \(n\) are the lengths of arrays \(\textit{nums1}\) and \(\textit{nums2}\), respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def minLargest(self, nums1: List[int], nums2: List[int]) -> int:
        def nxt(x: int, y: int) -> int:
            return x + 1 if (x & 1 ^ y) == 1 else x + 2

        m, n = len(nums1), len(nums2)
        f = [[0] * (n + 1) for _ in range(m + 1)]
        for i, x in enumerate(nums1, 1):
            f[i][0] = nxt(f[i - 1][0], x)
        for j, y in enumerate(nums2, 1):
            f[0][j] = nxt(f[0][j - 1], y)
        for i, x in enumerate(nums1, 1):
            for j, y in enumerate(nums2, 1):
                f[i][j] = min(nxt(f[i - 1][j], x), nxt(f[i][j - 1], y))
        return f[m][n]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int minLargest(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[][] f = new int[m + 1][n + 1];
        for (int i = 1; i <= m; ++i) {
            f[i][0] = nxt(f[i - 1][0], nums1[i - 1]);
        }
        for (int j = 1; j <= n; ++j) {
            f[0][j] = nxt(f[0][j - 1], nums2[j - 1]);
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                int x = nxt(f[i - 1][j], nums1[i - 1]);
                int y = nxt(f[i][j - 1], nums2[j - 1]);
                f[i][j] = Math.min(x, y);
            }
        }
        return f[m][n];
    }

    private int nxt(int x, int y) {
        return (x & 1 ^ y) == 1 ? x + 1 : x + 2;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int minLargest(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        int f[m + 1][n + 1];
        memset(f, 0, sizeof(f));
        auto nxt = [](int x, int y) -> int {
            return (x & 1 ^ y) == 1 ? x + 1 : x + 2;
        };
        for (int i = 1; i <= m; ++i) {
            f[i][0] = nxt(f[i - 1][0], nums1[i - 1]);
        }
        for (int j = 1; j <= n; ++j) {
            f[0][j] = nxt(f[0][j - 1], nums2[j - 1]);
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                int x = nxt(f[i - 1][j], nums1[i - 1]);
                int y = nxt(f[i][j - 1], nums2[j - 1]);
                f[i][j] = min(x, y);
            }
        }
        return f[m][n];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func minLargest(nums1 []int, nums2 []int) int {
    m, n := len(nums1), len(nums2)
    f := make([][]int, m+1)
    for i := range f {
        f[i] = make([]int, n+1)
    }
    nxt := func(x, y int) int {
        if (x&1 ^ y) == 1 {
            return x + 1
        }
        return x + 2
    }
    for i := 1; i <= m; i++ {
        f[i][0] = nxt(f[i-1][0], nums1[i-1])
    }
    for j := 1; j <= n; j++ {
        f[0][j] = nxt(f[0][j-1], nums2[j-1])
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            x := nxt(f[i-1][j], nums1[i-1])
            y := nxt(f[i][j-1], nums2[j-1])
            f[i][j] = min(x, y)
        }
    }
    return f[m][n]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function minLargest(nums1: number[], nums2: number[]): number {
    const m = nums1.length;
    const n = nums2.length;
    const f: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
    const nxt = (x: number, y: number): number => {
        return (x & 1) ^ y ? x + 1 : x + 2;
    };
    for (let i = 1; i <= m; ++i) {
        f[i][0] = nxt(f[i - 1][0], nums1[i - 1]);
    }
    for (let j = 1; j <= n; ++j) {
        f[0][j] = nxt(f[0][j - 1], nums2[j - 1]);
    }
    for (let i = 1; i <= m; ++i) {
        for (let j = 1; j <= n; ++j) {
            f[i][j] = Math.min(nxt(f[i - 1][j], nums1[i - 1]), nxt(f[i][j - 1], nums2[j - 1]));
        }
    }
    return f[m][n];
}

Comments