3269. Constructing Two Increasing Arrays 🔒

Problem Description

Given two integer arrays nums1 and nums2 consisting only of 0 and 1, the task is to calculate the minimum possible largest number in both arrays after performing specific replacements. Every 0 must be replaced with an even positive integer, and every 1 must be replaced with an odd positive integer. Post replacement, both arrays should be strictly increasing, and each integer should be used at most once. Return the minimum possible largest number after applying these transformations.

Intuition

The approach to solving this problem involves using dynamic programming. The intuition is to maintain a 2D array f[i][j] that represents the minimum possible largest number for the first i elements of nums1 and the first j elements of nums2. This requires considering the constraints that each 0 and 1 must be replaced with even and odd positive integers, respectively, and that the sequences must be strictly increasing.

The function nxt(x, y) determines the minimal number greater than x with the desired parity (even or odd, depending on whether y was originally 0 or 1). The algorithm involves initializing the dynamic programming table, filling it by calculating the possible values for f[i][j] based on the previous elements in both nums1 and nums2, and ensuring that each step adheres to the increasing order requirement. Finally, the result is the value of f[m][n], where m and n are the lengths of nums1 and nums2, respectively.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution to this problem employs dynamic programming. Here's how we arrive at the solution:

Define DP Table: Create a 2D table f where f[i][j] will store the minimum possible largest number considering the first i elements of nums1 and the first j elements of nums2.
Initial Conditions: Both nums1 and nums2 are initially all zeros. We assume f[0][0] = 0 since we start from no elements.
Define the nxt Function: This helper function nxt(x, y) calculates the minimum integer greater than x that can replace the y character from the arrays:
- If y is 0, find the next even integer greater than x.
- If y is 1, find the next odd integer greater than x.
- This is implemented as:
```
def nxt(x: int, y: int) -> int:
   return x + 1 if (x & 1 ^ y) == 1 else x + 2
```
Fill the DP Table:
- For i = 1 to m, compute f[i][0] by transitioning from f[i-1][0] using the nxt function to maintain an increasing sequence in nums1.
- Similarly, for j = 1 to n, compute f[0][j] by transitioning from f[0][j-1] using the same nxt function to maintain sequence order in nums2.
- For each i and j where both are greater than zero, calculate f[i][j] as the minimum resultant number from using either:
  - Transitioning from f[i-1][j] considering current element in nums1.
  - Transitioning from f[i][j-1] considering current element in nums2.
- This results in the transition equation:
```
f[i][j] = min(nxt(f[i-1][j], nums1[i-1]), nxt(f[i][j-1], nums2[j-1]))
```
Return the Result: The final answer is found in f[m][n], which is the minimum possible largest number considering all elements of both arrays.

This method ensures that every transition maintains the increasing property and uses integers correctly as per the parity and unique integer constraints.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider two small arrays nums1 = [0, 1] and nums2 = [1, 0]. The goal is to replace 0 with even integers and 1 with odd integers, ensuring that both arrays become strictly increasing, and return the minimum possible largest number.

Define the DP Table: We'll create a 2D table f where f[i][j] represents the minimum possible largest number for the first i elements of nums1 and the first j elements of nums2. Initialized as f[0][0] = 0.
Use the nxt Function: This helps find the next suitable integer greater than the current maximum:
- For nums1[0] = 0, an even number, the first suitable even integer greater than 0 is 2.
- For nums2[0] = 1, an odd number, the first suitable odd integer greater than 0 is 1.
Fill the DP Table:
- Calculate f[1][0]: Using f[0][0] = 0 and nums1[0] = 0, the replacement is 2. So, f[1][0] = 2.
- Calculate f[0][1]: Using f[0][0] = 0 and nums2[0] = 1, the replacement is 1. So, f[0][1] = 1.
- For f[1][1]: This comes from both possibilities:
  - Transition from f[0][1] with nums1[0]: max(1, 2) = 2.
  - Transition from f[1][0] with nums2[0]: max(2, 1) = 2. Consequently, f[1][1] = min(2, 2) = 2.
Return the Result: The result stored in f[2][2] is 2, indicating that the minimum possible largest number after the replacements is 2.

Solution Implementation

1from typing import List
2
3class Solution:
4    def minLargest(self, nums1: List[int], nums2: List[int]) -> int:
5        # Helper function to determine the next increment for the value based on current bit mask logic
6        def nxt(current: int, value: int) -> int:
7            # If the current and value's bits xor to 1, increase current by 1, else increase by 2
8            return current + 1 if (current & 1 ^ value) == 1 else current + 2
9
10        m, n = len(nums1), len(nums2)
11      
12        # Initialize a 2-dimensional array (DP table) with zero values
13        # Dimensions are (m+1) by (n+1) to account for extra initial row and column
14        dp = [[0] * (n + 1) for _ in range(m + 1)]
15      
16        # Fill the first column with values derived only from nums1
17        for i, x in enumerate(nums1, 1):
18            dp[i][0] = nxt(dp[i - 1][0], x)
19
20        # Fill the first row with values derived only from nums2
21        for j, y in enumerate(nums2, 1):
22            dp[0][j] = nxt(dp[0][j - 1], y)
23
24        # Fill the rest of the DP table
25        for i, x in enumerate(nums1, 1):
26            for j, y in enumerate(nums2, 1):
27                # Compute the minimum largest value by considering both previous results
28                dp[i][j] = min(nxt(dp[i - 1][j], x), nxt(dp[i][j - 1], y))
29      
30        # Return the value at the bottom-right corner of the DP table, which is the result
31        return dp[m][n]
32

1class Solution {
2    public int minLargest(int[] nums1, int[] nums2) {
3        int m = nums1.length, n = nums2.length;
4        int[][] f = new int[m + 1][n + 1];
5      
6        // Fill the first column using nums1
7        for (int i = 1; i <= m; ++i) {
8            f[i][0] = nxt(f[i - 1][0], nums1[i - 1]);
9        }
10      
11        // Fill the first row using nums2
12        for (int j = 1; j <= n; ++j) {
13            f[0][j] = nxt(f[0][j - 1], nums2[j - 1]);
14        }
15      
16        // Fill the rest of the table
17        for (int i = 1; i <= m; ++i) {
18            for (int j = 1; j <= n; ++j) {
19                // Calculate possible values from the previous states
20                int fromNums1 = nxt(f[i - 1][j], nums1[i - 1]);
21                int fromNums2 = nxt(f[i][j - 1], nums2[j - 1]);
22                // Choose the minimal value
23                f[i][j] = Math.min(fromNums1, fromNums2);
24            }
25        }
26      
27        // Return the value for using all elements from nums1 and nums2
28        return f[m][n];
29    }
30
31    // Private method to determine the next value
32    private int nxt(int x, int y) {
33        // If the operation (x & 1) ^ y equals 1, increase x by 1, otherwise increase it by 2
34        return ((x & 1) ^ y) == 1 ? x + 1 : x + 2;
35    }
36}
37

1#include <vector>
2#include <cstring>
3
4class Solution {
5public:
6    int minLargest(std::vector<int>& nums1, std::vector<int>& nums2) {
7        int m = nums1.size(), n = nums2.size();
8        int dp[m + 1][n + 1]; // 2D array to store intermediate results
9        memset(dp, 0, sizeof(dp)); // Initialize the array with zeroes
10      
11        // Lambda function to calculate the next value based on the condition
12        auto nextValue = [](int x, int y) -> int {
13            return ((x & 1) ^ y) == 1 ? x + 1 : x + 2;
14        };
15
16        // Initialize the first column based on nums1
17        for (int i = 1; i <= m; ++i) {
18            dp[i][0] = nextValue(dp[i - 1][0], nums1[i - 1]);
19        }
20
21        // Initialize the first row based on nums2
22        for (int j = 1; j <= n; ++j) {
23            dp[0][j] = nextValue(dp[0][j - 1], nums2[j - 1]);
24        }
25
26        // Fill the rest of the dp table
27        for (int i = 1; i <= m; ++i) {
28            for (int j = 1; j <= n; ++j) {
29                int option1 = nextValue(dp[i - 1][j], nums1[i - 1]); // Option from nums1
30                int option2 = nextValue(dp[i][j - 1], nums2[j - 1]); // Option from nums2
31                dp[i][j] = std::min(option1, option2); // Take the minimum of both options
32            }
33        }
34
35        return dp[m][n]; // The answer is stored in dp[m][n]
36    }
37};
38

1// Function to compute the minimum largest of interleaved selecting sequence from nums1 and nums2
2function minLargest(nums1: number[], nums2: number[]): number {
3    // Get the lengths of nums1 and nums2
4    const m = nums1.length;
5    const n = nums2.length;
6
7    // Create a 2D array to store the results of subproblems
8    const f: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
9
10    // Helper function to calculate the next value in sequence
11    const nxt = (x: number, y: number): number => {
12        // Calculate the next value based on current x and y
13        return (x & 1) ^ y ? x + 1 : x + 2;
14    };
15
16    // Initialize the first column of the matrix
17    for (let i = 1; i <= m; ++i) {
18        f[i][0] = nxt(f[i - 1][0], nums1[i - 1]);
19    }
20
21    // Initialize the first row of the matrix
22    for (let j = 1; j <= n; ++j) {
23        f[0][j] = nxt(f[0][j - 1], nums2[j - 1]);
24    }
25
26    // Fill the matrix using dynamic programming
27    for (let i = 1; i <= m; ++i) {
28        for (let j = 1; j <= n; ++j) {
29            // Choose the minimum largest of choosing from nums1 or nums2
30            f[i][j] = Math.min(nxt(f[i - 1][j], nums1[i - 1]), nxt(f[i][j - 1], nums2[j - 1]));
31        }
32    }
33
34    // Return the final result
35    return f[m][n];
36}
37

Time and Space Complexity

The time complexity of the code is O(m * n). This is because the nested loops iterate over each element in the two-dimensional list f which has dimensions (m + 1) x (n + 1), where m is the length of nums1 and n is the length of nums2.

The space complexity of the code is O(m * n). This is due to the creation of a two-dimensional list f with dimensions (m + 1) x (n + 1), which stores the intermediate results for dynamic programming.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which algorithm should you use to find a node that is close to the root of the tree?

Depth First Search

Breadth First Search

I don’t know