Problem Description

You have two arrays nums1 and nums2, both of length n and 0-indexed. Your task is to create a third array nums3 of the same length by selecting elements strategically.

For each position i in nums3, you must choose either nums1[i] or nums2[i] to place at that position. In other words:

• nums3[i] = nums1[i] OR nums3[i] = nums2[i]

Your goal is to make the choices in such a way that nums3 contains the longest possible non-decreasing subarray. A non-decreasing subarray means each element is greater than or equal to the previous one (elements can be equal or increasing, but not decreasing).

A subarray is a contiguous sequence of elements from the array, and it must be non-empty.

Example to illustrate the concept: If nums1 = [2, 3, 1] and nums2 = [1, 2, 3], you could create:

• nums3 = [2, 3, 3] by choosing from [nums1[0], nums1[1], nums2[2]]
• nums3 = [1, 2, 3] by choosing all from nums2

The second choice gives a non-decreasing subarray of length 3, which would be optimal.

The function should return an integer representing the maximum possible length of a non-decreasing subarray that can be achieved in nums3 through optimal selection of elements from nums1 and nums2.

Intuition

The key insight is that at each position, we have a choice between two elements, and we need to track the longest non-decreasing subarray that can end at that position. This naturally leads to a dynamic programming approach.

Think about it this way: when we're at position i, we need to know what's the longest non-decreasing subarray we can build that ends at this position. But here's the catch - we have two choices for the element at position i: either nums1[i] or nums2[i].

This means we need to track two pieces of information:

1. The longest non-decreasing subarray ending with an element from nums1
2. The longest non-decreasing subarray ending with an element from nums2

Why do we need both? Because the choice we make at position i affects what we can choose at position i+1. If we end with nums1[i-1], then at position i, we can extend the subarray only if:

• nums1[i] >= nums1[i-1] (if we choose nums1[i])
• nums2[i] >= nums1[i-1] (if we choose nums2[i])

Similarly, if we ended with nums2[i-1], we have different conditions for extension.

By maintaining two variables f and g that represent the longest non-decreasing subarray ending with elements from nums1 and nums2 respectively, we can make optimal decisions at each step. At each position, we check all four possible transitions:

• Previous ended with nums1, current chooses nums1
• Previous ended with nums2, current chooses nums1
• Previous ended with nums1, current chooses nums2
• Previous ended with nums2, current chooses nums2

We take the maximum valid extension for each choice, and keep track of the overall maximum length seen so far. This greedy approach with dynamic programming ensures we find the optimal solution in a single pass through the arrays.

Learn more about Dynamic Programming patterns.

Solution Approach

We use dynamic programming with state compression to solve this problem efficiently. The implementation maintains two variables to track the current state:

• f: Length of the longest non-decreasing subarray ending with an element from nums1
• g: Length of the longest non-decreasing subarray ending with an element from nums2

Initialization: We start with f = g = 1 since any single element forms a non-decreasing subarray of length 1. The answer ans is also initialized to 1.

Main Algorithm: We iterate through positions i from 1 to n-1. For each position, we calculate new values ff and gg representing the longest non-decreasing subarrays ending at position i with nums1[i] and nums2[i] respectively.

For each position i, we examine four possible transitions:

1. Extend f to ff: If nums1[i] >= nums1[i-1], we can extend the subarray ending with nums1[i-1] by choosing nums1[i]. Update: ff = max(ff, f + 1)

2. Extend g to ff: If nums1[i] >= nums2[i-1], we can extend the subarray ending with nums2[i-1] by choosing nums1[i]. Update: ff = max(ff, g + 1)

3. Extend f to gg: If nums2[i] >= nums1[i-1], we can extend the subarray ending with nums1[i-1] by choosing nums2[i]. Update: gg = max(gg, f + 1)

4. Extend g to gg: If nums2[i] >= nums2[i-1], we can extend the subarray ending with nums2[i-1] by choosing nums2[i]. Update: gg = max(gg, g + 1)

State Update: After calculating ff and gg, we update our state variables: f = ff and g = gg. We also update the global answer: ans = max(ans, f, g).

Time and Space Complexity:

• Time Complexity: O(n) - We iterate through the array once
• Space Complexity: O(1) - We only use a constant number of variables

The beauty of this approach is that we don't need to store the entire DP table. By only keeping track of the previous state (f and g), we can compute the current state (ff and gg) and find the optimal solution in a single pass.

Example Walkthrough

Let's walk through a concrete example to understand how the algorithm works.

Given:

• nums1 = [1, 4, 2, 3]
• nums2 = [2, 1, 3, 4]

We'll track f (longest non-decreasing subarray ending with nums1) and g (longest ending with nums2).

Initial State (i=0):

• f = 1 (choosing nums1[0] = 1)
• g = 1 (choosing nums2[0] = 2)
• ans = 1

Iteration 1 (i=1): Looking at position 1: nums1[1] = 4, nums2[1] = 1

Calculate ff (if we choose nums1[1] = 4):

• Can extend from f? Check if 4 >= 1 (nums1[0]): ✓ → ff = 1 + 1 = 2
• Can extend from g? Check if 4 >= 2 (nums2[0]): ✓ → ff = max(2, 1 + 1) = 2

Calculate gg (if we choose nums2[1] = 1):

• Can extend from f? Check if 1 >= 1 (nums1[0]): ✓ → gg = 1 + 1 = 2
• Can extend from g? Check if 1 >= 2 (nums2[0]): ✗ → gg stays 1

Update: f = 2, g = 2, ans = 2

Iteration 2 (i=2): Looking at position 2: nums1[2] = 2, nums2[2] = 3

Calculate ff (if we choose nums1[2] = 2):

• Can extend from f? Check if 2 >= 4 (nums1[1]): ✗ → ff = 1
• Can extend from g? Check if 2 >= 1 (nums2[1]): ✓ → ff = max(1, 2 + 1) = 3

Calculate gg (if we choose nums2[2] = 3):

• Can extend from f? Check if 3 >= 4 (nums1[1]): ✗ → gg = 1
• Can extend from g? Check if 3 >= 1 (nums2[1]): ✓ → gg = max(1, 2 + 1) = 3

Update: f = 3, g = 3, ans = 3

Iteration 3 (i=3): Looking at position 3: nums1[3] = 3, nums2[3] = 4

Calculate ff (if we choose nums1[3] = 3):

• Can extend from f? Check if 3 >= 2 (nums1[2]): ✓ → ff = 3 + 1 = 4
• Can extend from g? Check if 3 >= 3 (nums2[2]): ✓ → ff = max(4, 3 + 1) = 4

Calculate gg (if we choose nums2[3] = 4):

• Can extend from f? Check if 4 >= 2 (nums1[2]): ✓ → gg = 3 + 1 = 4
• Can extend from g? Check if 4 >= 3 (nums2[2]): ✓ → gg = max(4, 3 + 1) = 4

Update: f = 4, g = 4, ans = 4

Result: The maximum length is 4.

One optimal nums3 would be [2, 1, 2, 3] (choosing nums2[0], nums2[1], nums1[2], nums1[3]), which forms the non-decreasing subarray [1, 2, 3] from indices 1 to 3. Another optimal choice is [1, 1, 2, 3] (choosing nums1[0], nums2[1], nums1[2], nums1[3]), forming the complete non-decreasing array of length 4.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through the arrays once with a single for loop from index 1 to n-1. Within each iteration, it performs a constant number of operations:

• Four comparison operations to check if elements are non-decreasing
• Several max operations to update ff and gg
• Variable assignments and one final max operation to update ans

Since all operations inside the loop take constant time O(1) and the loop runs n-1 times, the overall time complexity is O(n), where n is the length of the input arrays.

Space Complexity: O(1)

The algorithm uses only a fixed number of variables regardless of input size:

• Variables f and g to track the maximum non-decreasing lengths ending at the previous position
• Variables ff and gg as temporary storage for the current position
• Variable ans to store the maximum length found
• Loop variable i

No additional data structures that scale with input size are created. Therefore, the space complexity is O(1) - constant space.

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

Common Pitfalls

1. Incorrect State Initialization for New Positions

A common mistake is forgetting that at each position, we can always start a new non-decreasing subarray of length 1, regardless of previous choices. Some implementations might incorrectly initialize new_dp_nums1 and new_dp_nums2 to 0 or forget to consider this base case.

Incorrect approach:

# Wrong: Assuming we must extend from previous
new_dp_nums1 = 0  # This would fail if no extension is possible
new_dp_nums2 = 0

Correct approach:

# Right: We can always start fresh with length 1
new_dp_nums1 = 1
new_dp_nums2 = 1

2. Mixing Up Comparison Indices

Another frequent error is confusing which elements to compare when checking if we can extend a subarray. The key is to compare the current element we want to choose with the previous element that was actually chosen.

Incorrect approach:

# Wrong: Comparing with wrong array's previous element
if nums1[i] >= nums1[i-1]:
    new_dp_nums2 = max(new_dp_nums2, dp_nums1 + 1)  # Wrong assignment

Correct approach:

# Right: If choosing nums1[i], compare with what was chosen at i-1
if nums1[i] >= nums1[i-1]:  # Previous choice was nums1
    new_dp_nums1 = max(new_dp_nums1, dp_nums1 + 1)
if nums1[i] >= nums2[i-1]:  # Previous choice was nums2
    new_dp_nums1 = max(new_dp_nums1, dp_nums2 + 1)

3. Forgetting to Update the Global Maximum

Some solutions might only return the final state values (dp_nums1 or dp_nums2) without tracking the maximum throughout the iteration. The longest non-decreasing subarray might end at any position, not necessarily at the last index.

Incorrect approach:

# Wrong: Only considering final position
for i in range(1, n):
    # ... calculate new_dp_nums1 and new_dp_nums2
    dp_nums1, dp_nums2 = new_dp_nums1, new_dp_nums2
return max(dp_nums1, dp_nums2)  # Misses optimal subarrays ending earlier

Correct approach:

# Right: Track maximum at every position
max_length = 1
for i in range(1, n):
    # ... calculate new_dp_nums1 and new_dp_nums2
    dp_nums1, dp_nums2 = new_dp_nums1, new_dp_nums2
    max_length = max(max_length, dp_nums1, dp_nums2)
return max_length

4. Edge Case: Single Element Arrays

While the provided solution handles this correctly, a pitfall could be not considering arrays of length 1, where the answer is always 1.

Solution: Always initialize the maximum length to 1, as done in the correct implementation.