Skip to main content
Talentd

Constructing Two Increasing Arrays - Solution & Explanation

HardPremiumFree on FleetCodeArrayDynamic Programming11 min read
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: You are given an array nums. The task is to construct two arrays a and b such that for every index i, a[i] + b[i] = nums[i], while both arrays remain strictly increasing. The goal is to count how many valid constructions exist.

Approach 1: Brute Force Enumeration (Exponential Time)

At each index i, iterate over all possible values for a[i] from 0 to nums[i], then set b[i] = nums[i] - a[i]. Track the previous values to ensure a and b stay strictly increasing. This produces a branching search tree where each index explores multiple splits. The time complexity grows exponentially because every position can have many candidate pairs, and the space complexity is O(n) due to recursion depth. This approach only works for very small inputs and mainly helps clarify the constraints.

Approach 2: Dynamic Programming on Value Transitions (O(n · m^2) time, O(m) space)

Use Dynamic Programming to track valid choices for a[i]. Let dp[i][x] represent the number of ways to build arrays up to index i with a[i] = x. Since b[i] = nums[i] - x, both arrays must remain strictly increasing: x > a[i-1] and nums[i] - x > b[i-1]. For each candidate x, iterate over all previous a[i-1] values that satisfy both constraints. The maximum candidate value is bounded by nums[i], so if m is the maximum value in nums, the transition costs O(m^2) per index.

Approach 3: Optimized DP with Prefix Sums (O(n · m) time, O(m) space)

The DP transition can be optimized by noticing that valid previous states form a continuous range. Instead of iterating over all previous values, maintain prefix sums of the DP row. For a chosen a[i] = x, compute the maximum allowed previous value derived from both increasing constraints. Then query the prefix sum to count all valid states in constant time. This removes the inner loop and reduces the transition cost to O(1). The overall complexity becomes O(n · m) time with O(m) space. The technique combines array traversal with dynamic programming state transitions and prefix accumulation.

Recommended for interviews: The prefix-sum optimized dynamic programming approach is the expected solution. Interviewers want to see the DP formulation first (state definition and transition constraints), then the optimization that reduces the transition from quadratic to linear per index. Showing the brute force reasoning demonstrates understanding, but implementing the optimized DP shows strong algorithmic skill.

Solution

We define f[i][j] to represent the minimum of the maximum values among the first i elements of array nums1 and the first j elements of array nums2. Initially, f[i][j] = 0, and the answer is f[m][n], where m and n are the lengths of arrays nums1 and 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] = nxt(f[i - 1][0], nums1[i - 1]), where 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] = nxt(f[0][j - 1], 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(nxt(f[i - 1][j], nums1[i - 1]), nxt(f[i][j - 1], 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 nums1 and nums2, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(k^n)O(n)Conceptual understanding or very small inputs
Basic Dynamic ProgrammingO(n · m^2)O(m)When deriving DP transitions before optimization
DP with Prefix Sum OptimizationO(n · m)O(m)Optimal solution for large constraints and interview settings

Video Solution

5 Simple Steps for Solving Dynamic Programming Problems • Reducible • 1,234,244 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Constructing Two Increasing Arrays easy or hard?
Constructing Two Increasing Arrays is classified as a Hard problem because it requires careful dynamic programming state design and transition optimization. Recognizing that valid previous states form a continuous range and applying prefix sums to reduce complexity is the key challenge.
Constructing Two Increasing Arrays Python/Java solution
The typical implementation builds a DP array representing valid values for a[i]. For each index, iterate through possible splits, enforce increasing constraints, and use prefix sums to accumulate counts efficiently. The same logic translates cleanly across Python, Java, C++, Go, and TypeScript using arrays and modular arithmetic.
How to solve Constructing Two Increasing Arrays in O(n)?
Strict O(n) is generally not achievable because each index may require evaluating multiple candidate values for the split. The practical optimal solution is O(n · m) using dynamic programming and prefix sums, where m is the maximum allowed value for a[i]. Prefix sums eliminate nested transitions and keep each state update constant time.
What is the best approach for Constructing Two Increasing Arrays?
The best approach uses dynamic programming with prefix sum optimization. Define a DP state for the value chosen in the first array at each index and derive the second array value from nums[i] - a[i]. Using prefix sums allows you to aggregate valid previous states efficiently, reducing the transition cost and achieving O(n · m) time complexity.
Is Constructing Two Increasing Arrays asked at Google/Amazon/Meta?
Problems involving counting valid constructions with monotonic constraints commonly appear in interviews at companies like Google, Amazon, and Meta. Variants that combine array constraints with dynamic programming transitions are particularly common in senior-level algorithm rounds.
What data structure is used in Constructing Two Increasing Arrays?
The main technique is dynamic programming implemented with arrays to store DP states. Prefix sum arrays are used to speed up transitions by quickly summing ranges of valid previous states. The algorithm primarily relies on array iteration and DP state transitions.
What is the time complexity of Constructing Two Increasing Arrays?
The optimized dynamic programming solution runs in O(n · m) time, where n is the length of nums and m is the maximum possible value considered for a[i]. Space complexity is O(m) by storing only the previous DP row. A naive DP approach without prefix sums can take O(n · m^2).

Ready to solve this problem?

Practice Constructing Two Increasing Arrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays