We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Constructing Two Increasing Arrays

Number: 3586

Difficulty: Hard

Paid? Yes

Companies: N/A

Problem Description

Given two integer arrays nums1 and nums2 containing only 0s and 1s, replace every 0 with an even positive integer and every 1 with an odd positive integer. After the replacement, both arrays must be strictly increasing and each integer can be used at most once across both arrays. The goal is to minimize the maximum integer appearing in either array after the replacements.

Key Insights

  • Each 0 must be replaced with an even number and each 1 with an odd number.
  • Both arrays must be strictly increasing, which forces every replacement to be larger than the previous one.
  • No integer may be reused between the two arrays, so assignments must be coordinated.
  • A dynamic programming state can be used to simulate the construction of both arrays simultaneously.
  • The DP state tracks the smallest possible “last used number” after processing a given prefix of each array.
  • The main challenge is to decide the next valid candidate (ensuring the correct parity) that is greater than the last used number.

Space and Time Complexity

Time Complexity: O(n1 * n2) where n1 and n2 are the lengths of nums1 and nums2 respectively. Space Complexity: O(n1 * n2) for storing the dynamic programming table.

Solution

We use a dynamic programming approach. Define dp[i][j] to be the minimum possible last number used after forming i elements of nums1 and j elements of nums2. We start with dp[0][0] = 0. For every state, if the next element from either array is a 0, we choose the smallest even number greater than the current last number; if it is a 1, we choose the smallest odd number greater than the current last number. We update the state accordingly. The final answer will be found at dp[n1][n2].

The key trick is to compute the next candidate number with the required parity using:

  • For even: candidate = (last + 1) if (last + 1) is even, otherwise (last + 2).
  • For odd: candidate = (last + 1) if (last + 1) is odd, otherwise (last + 2).

This process inherently guarantees that both arrays maintain a strictly increasing order while ensuring no reuse of numbers.

Code Solutions

# Python solution with comments

def min_max_number(nums1, nums2):
    # lengths of the input arrays
    n1, n2 = len(nums1), len(nums2)
    # dp[i][j] tracks the minimal last number used after i elements from nums1 and j elements from nums2
    INF = float('inf')
    dp = [[INF] * (n2 + 1) for _ in range(n1 + 1)]
    dp[0][0] = 0  # base case: no elements assigned, last number is 0

    # iterate through all dp states
    for i in range(n1 + 1):
        for j in range(n2 + 1):
            if dp[i][j] == INF:
                continue
            last = dp[i][j]
            # Option to extend nums1 if elements remain
            if i < n1:
                if nums1[i] == 0:  # requires an even number
                    candidate = last + 1 if (last + 1) % 2 == 0 else last + 2
                else:            # requires an odd number
                    candidate = last + 1 if (last + 1) % 2 == 1 else last + 2
                dp[i + 1][j] = min(dp[i + 1][j], candidate)
            # Option to extend nums2 if elements remain
            if j < n2:
                if nums2[j] == 0:  # requires an even number
                    candidate = last + 1 if (last + 1) % 2 == 0 else last + 2
                else:            # requires an odd number
                    candidate = last + 1 if (last + 1) % 2 == 1 else last + 2
                dp[i][j + 1] = min(dp[i][j + 1], candidate)
    # The final state gives the minimum maximum number required for valid assignments.
    return dp[n1][n2]

# Example usage:
print(min_max_number([], [1, 0, 1, 1]))  # Expected output: 5
← Back to All Questions