LeetCode 3269 - Constructing Two Increasing Arrays

We are given two binary arrays, nums1 and nums2. Each element is either 0 or 1. We must replace every value with a positive integer according to its parity: - Every 0 must become an even positive integer. - Every 1 must become an odd positive integer.

leetcodehardarraydynamic-programming

LeetCode Problem 3269

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

Problem Understanding

We are given two binary arrays, nums1 and nums2. Each element is either 0 or 1. We must replace every value with a positive integer according to its parity:

  • Every 0 must become an even positive integer.
  • Every 1 must become an odd positive integer.

After replacement, both resulting arrays must satisfy two conditions:

  1. Each array must be strictly increasing.
  2. No integer may appear more than once across both arrays combined.

Our goal is to minimize the largest number used anywhere in either array.

The problem is essentially asking us to assign distinct positive integers with required parity constraints while preserving increasing order inside each array. Among all valid assignments, we want the smallest possible maximum assigned value.

For example, if we see a 1, we need an unused odd number. If we see a 0, we need an unused even number. Since each array must be increasing, the assigned values inside each array must grow from left to right.

The constraints are:

  • 0 <= nums1.length <= 1000
  • 1 <= nums2.length <= 1000

This immediately tells us that brute force enumeration of assignments is impossible. Even for small arrays, the number of ways to assign increasing distinct integers explodes combinatorially.

An important observation is that the actual numeric values matter only through:

  • parity,
  • ordering,
  • uniqueness,
  • and minimizing the maximum value.

Several edge cases are important:

  • One array may be empty.
  • Both arrays may contain many repeated parity requirements.
  • One parity may dominate heavily, forcing the answer upward because odd and even numbers alternate.
  • Two arrays may compete for the same parity positions, making naive greedy assignment invalid.

The problem guarantees only binary input values, which strongly hints that parity counting and ordering properties are central to the solution.

Approaches

Brute Force Approach

A brute force solution would attempt to generate assignments for all positions using unused integers of the correct parity while maintaining increasing order in both arrays.

We could imagine recursively assigning numbers position by position:

  • For every 0, try all unused even integers.
  • For every 1, try all unused odd integers.
  • Ensure increasing order constraints remain valid.
  • Track the largest assigned number.
  • Minimize the final maximum.

This approach is correct because it explores all valid assignments.

However, it is computationally infeasible. Even with small arrays, the branching factor becomes enormous. Since the answer can grow beyond the array sizes, the search space is effectively exponential.

Key Insight

The critical observation is that we do not need the exact assignments. We only need to know whether a certain maximum value M is sufficient.

Suppose we fix some candidate maximum number M.

Then among numbers from 1 to M:

  • There are (M + 1) // 2 odd numbers.
  • There are M // 2 even numbers.

Now the problem becomes:

Can we place all required odd and even values into the two arrays while preserving increasing order and uniqueness?

The ordering constraint becomes surprisingly manageable because if we process positions from left to right, assigning the smallest available valid number always works whenever a solution exists.

The real challenge is competition between the two arrays for odd and even numbers.

This transforms the problem into a feasibility problem, which naturally suggests binary search on the answer.

For a candidate M, we greedily simulate constructing both arrays using numbers from 1 to M. If construction succeeds, then M is feasible. Otherwise, it is too small.

Because feasibility is monotonic:

  • If M works, every larger value also works.
  • If M fails, every smaller value also fails.

Binary search becomes valid.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Tries all valid assignments
Optimal O((n + m) log(n + m)) O(1) Binary search with greedy feasibility check

Algorithm Walkthrough

Step 1: Define the feasibility check

We create a helper function can(max_value).

This function determines whether it is possible to construct both arrays using only numbers from 1 to max_value.

Step 2: Simulate number assignment greedily

We maintain:

  • a pointer to the next unused odd number,
  • a pointer to the next unused even number.

For every position in both arrays:

  • If the value is 1, assign the smallest available odd number.
  • If the value is 0, assign the smallest available even number.

Because we always choose the smallest valid unused number, we automatically preserve increasing order inside each array.

Step 3: Ensure uniqueness

Whenever we assign a number, we advance the corresponding odd or even pointer.

Since numbers are assigned only once globally, uniqueness is guaranteed.

Step 4: Detect failure

If at any point:

  • the next required odd exceeds max_value, or
  • the next required even exceeds max_value,

then the candidate maximum is impossible.

Step 5: Binary search the answer

We binary search over possible answers.

The lower bound is 1.

A safe upper bound is large enough to always work, such as 4 * (len(nums1) + len(nums2)).

For each midpoint:

  • If feasible, search smaller values.
  • Otherwise search larger values.

Eventually we obtain the minimum feasible maximum value.

Why it works

The greedy assignment is optimal because using smaller valid numbers earlier can never hurt future assignments. Larger numbers only reduce future flexibility.

The feasibility condition is monotonic:

  • If all assignments fit within M, they also fit within any larger limit.
  • If they do not fit within M, they cannot fit within any smaller limit.

Therefore binary search correctly finds the minimum feasible maximum.

Python Solution

from typing import List

class Solution:
    def minLargest(self, nums1: List[int], nums2: List[int]) -> int:
        def can(limit: int) -> bool:
            next_odd = 1
            next_even = 2

            for value in nums1:
                if value == 1:
                    if next_odd > limit:
                        return False
                    next_odd += 2
                else:
                    if next_even > limit:
                        return False
                    next_even += 2

            for value in nums2:
                if value == 1:
                    if next_odd > limit:
                        return False
                    next_odd += 2
                else:
                    if next_even > limit:
                        return False
                    next_even += 2

            return True

        total_length = len(nums1) + len(nums2)

        left = 1
        right = 4 * total_length + 10

        while left < right:
            mid = (left + right) // 2

            if can(mid):
                right = mid
            else:
                left = mid + 1

        return left

The implementation begins with the helper function can(limit).

This function simulates assigning numbers up to limit. We track the next available odd and even numbers separately.

For every 1, we consume the current odd number and move to the next odd. For every 0, we do the same with even numbers.

If the required parity number exceeds the limit, the candidate answer fails immediately.

The binary search then searches for the smallest feasible limit. Since feasibility is monotonic, standard binary search applies directly.

The upper bound is intentionally generous. Since the total number of required assignments is at most 2000, this bound remains small and efficient.

Go Solution

package main

func minLargest(nums1 []int, nums2 []int) int {
	can := func(limit int) bool {
		nextOdd := 1
		nextEven := 2

		for _, value := range nums1 {
			if value == 1 {
				if nextOdd > limit {
					return false
				}
				nextOdd += 2
			} else {
				if nextEven > limit {
					return false
				}
				nextEven += 2
			}
		}

		for _, value := range nums2 {
			if value == 1 {
				if nextOdd > limit {
					return false
				}
				nextOdd += 2
			} else {
				if nextEven > limit {
					return false
				}
				nextEven += 2
			}
		}

		return true
	}

	totalLength := len(nums1) + len(nums2)

	left := 1
	right := 4*totalLength + 10

	for left < right {
		mid := (left + right) / 2

		if can(mid) {
			right = mid
		} else {
			left = mid + 1
		}
	}

	return left
}

The Go implementation mirrors the Python logic closely.

Go slices naturally handle empty arrays, so no special handling is needed for nil versus empty slices.

Integer overflow is not a concern because the maximum possible answer is small relative to Go's integer range.

The feasibility function is implemented as a closure for clarity and locality.

Worked Examples

Example 1

Input:

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

We binary search the answer.

Try limit = 5.

Step Required Parity Assigned Number Next Odd Next Even
1 odd 1 3 2
2 even 2 3 4
3 odd 3 5 4
4 odd 5 7 4

All assignments fit within 5.

Try limit = 4.

The last odd assignment would require 5, which exceeds 4.

Therefore the minimum feasible answer is 5.

Example 2

Input:

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

Total required:

  • Four odd numbers
  • Four even numbers

Try limit = 9.

Assignments proceed as follows.

For nums1:

Position Value Assigned
0 0 2
1 1 1
2 0 4
3 1 3

For nums2:

Position Value Assigned
0 1 5
1 0 6
2 0 8
3 1 7

Largest assigned number is 8, so 9 is certainly feasible.

Trying smaller values eventually fails because there are insufficient odd and even numbers available.

Final answer is 9.

Example 3

Input:

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

Required:

  • Three odd numbers
  • Six even numbers

Within 1..13:

  • Odd numbers available: 1,3,5,7,9,11,13
  • Even numbers available: 2,4,6,8,10,12

There are enough of both parities.

Within 1..12:

  • Only six even numbers exist.
  • But ordering and uniqueness constraints force the odd assignment higher.

Thus the minimum feasible answer is 13.

Complexity Analysis

Measure Complexity Explanation
Time O((n + m) log(n + m)) Binary search with linear feasibility checks
Space O(1) Only a few counters are used

The feasibility check scans both arrays once, giving linear time complexity.

Binary search performs O(log(n + m)) iterations because the answer range is proportional to the input size.

The algorithm uses constant extra space because it only maintains a few integer pointers.

Test Cases

sol = Solution()

assert sol.minLargest([], [1, 0, 1, 1]) == 5
# Empty first array

assert sol.minLargest([0, 1, 0, 1], [1, 0, 0, 1]) == 9
# Mixed parity requirements

assert sol.minLargest([0, 1, 0, 0, 1], [0, 0, 0, 1]) == 13
# Heavy even usage

assert sol.minLargest([], [1]) == 1
# Single odd number

assert sol.minLargest([], [0]) == 2
# Single even number

assert sol.minLargest([1, 1, 1], []) == 5
# Only odd assignments

assert sol.minLargest([0, 0, 0], []) == 6
# Only even assignments

assert sol.minLargest([1, 0, 1, 0], []) == 7
# Alternating parity in one array

assert sol.minLargest([1] * 1000, []) == 1999
# Maximum odd-heavy input

assert sol.minLargest([0] * 1000, []) == 2000
# Maximum even-heavy input

assert sol.minLargest([1] * 500, [0] * 500) == 1000
# Balanced parity usage
Test Why
[], [1,0,1,1] Empty array edge case
[0,1,0,1], [1,0,0,1] Mixed parity competition
[0,1,0,0,1], [0,0,0,1] Large even requirement
[], [1] Smallest odd-only case
[], [0] Smallest even-only case
[1,1,1], [] Sequential odd assignments
[0,0,0], [] Sequential even assignments
[1,0,1,0], [] Alternating parity ordering
[1] * 1000, [] Maximum odd stress test
[0] * 1000, [] Maximum even stress test
[1] * 500, [0] * 500 Balanced large input

Edge Cases

One important edge case occurs when one array is empty. In this situation, the entire problem reduces to assigning increasing parity-constrained numbers to a single array. Some implementations accidentally assume both arrays contain elements, which can lead to incorrect iteration logic or invalid bounds. This implementation handles empty arrays naturally because the feasibility check simply skips the empty loop.

Another important case is when all values require the same parity. For example, if every element is 1, then only odd numbers may be used. The largest assigned value becomes the largest required odd number. A buggy implementation might incorrectly assume even and odd assignments interleave naturally. This solution correctly tracks odd and even sequences independently.

A third tricky case is heavy competition between arrays for the same parity. Since all assigned numbers must be globally unique, the arrays cannot independently reuse parity sequences. A naive solution that processes arrays separately would incorrectly reuse numbers. This implementation uses shared odd and even pointers across both arrays, guaranteeing uniqueness globally.