#2771

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Longest Non-decreasing Subarray From Two Arrays

Maximize the length of a non-decreasing subarray by optimally choosing elements from two arrays using dynamic programming.

array dynamic programming

Problem Statement

You are given two integer arrays nums1 and nums2 of equal length n. Construct a new array nums3 by choosing for each index i either nums1[i] or nums2[i].

Your goal is to maximize the length of the longest contiguous non-decreasing subarray in nums3. Determine the maximum achievable length and return it.

Examples

Example 1

Input: nums1 = [2,3,1], nums2 = [1,2,1]

Output: 2

One way to construct nums3 is: nums3 = [nums1[0], nums2[1], nums2[2]] => [2,2,1]. The subarray starting from index 0 and ending at index 1, [2,2], forms a non-decreasing subarray of length 2. We can show that 2 is the maximum achievable length.

Example 2

Input: nums1 = [1,3,2,1], nums2 = [2,2,3,4]

Output: 4

One way to construct nums3 is: nums3 = [nums1[0], nums2[1], nums2[2], nums2[3]] => [1,2,3,4]. The entire array forms a non-decreasing subarray of length 4, making it the maximum achievable length.

Example 3

Input: nums1 = [1,1], nums2 = [2,2]

Output: 2

One way to construct nums3 is: nums3 = [nums1[0], nums1[1]] => [1,1]. The entire array forms a non-decreasing subarray of length 2, making it the maximum achievable length.

Constraints

1 <= nums1.length == nums2.length == n <= 105
1 <= nums1[i], nums2[i] <= 109

Solution Approach

Define State Variables

Use two arrays dp1 and dp2 where dp1[i] represents the length of the longest non-decreasing subarray ending at index i if nums3[i] is nums1[i], and dp2[i] for nums2[i]. Initialize dp1[0] = dp2[0] = 1.

Apply State Transition

For each index i > 0, update dp1[i] and dp2[i] by checking if nums1[i] >= nums1[i-1] and nums1[i] >= nums2[i-1] for dp1, and similar checks for dp2. Set dp1[i] = max(dp1[i], dp2[i-1] + 1) when possible, and vice versa. This ensures optimal choice propagation.

Compute Maximum Length

Iterate through all dp1 and dp2 values, tracking the maximum value found. This maximum represents the length of the longest non-decreasing subarray achievable by selecting elements optimally from nums1 and nums2.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each index is processed once and updates two states. Space complexity is O(n) for dp1 and dp2, or O(1) if using rolling variables instead of full arrays.

What Interviewers Usually Probe

They may hint at using DP and tracking two choices per index.
Expect questions about handling equal values or non-decreasing conditions.
They might ask about optimizing space from O(n) to O(1) using rolling variables.

Common Pitfalls or Variants

Common pitfalls

Forgetting to consider both previous dp1 and dp2 values when updating the current state.
Misinterpreting non-decreasing as strictly increasing.
Not initializing the first element correctly, leading to off-by-one errors.

Follow-up variants

Find the longest non-decreasing subarray when more than two arrays are available to choose from.
Determine the maximum sum of the non-decreasing subarray instead of the length.
Compute the number of distinct longest non-decreasing subarrays constructible from two arrays.

FAQ

What is the main pattern used in Longest Non-decreasing Subarray From Two Arrays?

The main pattern is state transition dynamic programming, tracking longest non-decreasing subarrays ending at each index for both array choices.

Can this problem be solved with O(1) extra space?

Yes, by using two rolling variables instead of full dp arrays, since only the previous state is needed for the transition.

How do I handle equal values between nums1 and nums2?

Treat equal values as valid for non-decreasing subarrays, updating both dp1 and dp2 accordingly to capture all possibilities.

What is the time complexity of the solution?

Time complexity is O(n) because each element is processed once with constant-time updates for both states.

What are common mistakes when solving this problem?

Common mistakes include ignoring one of the two previous states, treating non-decreasing as strictly increasing, or misinitializing the first element of dp arrays.

terminal

Solution

Solution 1: Dynamic Programming

We define two variables $f$ and $g$, which represent the length of the longest non-decreasing subarray at the current position. Here, $f$ represents the length of the longest non-decreasing subarray ending with an element from $nums1$, and $g$ represents the length of the longest non-decreasing subarray ending with an element from $nums2$. Initially, $f = g = 1$, and the initial answer $ans = 1$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        f = g = 1
        ans = 1
        for i in range(1, n):
            ff = gg = 1
            if nums1[i] >= nums1[i - 1]:
                ff = max(ff, f + 1)
            if nums1[i] >= nums2[i - 1]:
                ff = max(ff, g + 1)
            if nums2[i] >= nums1[i - 1]:
                gg = max(gg, f + 1)
            if nums2[i] >= nums2[i - 1]:
                gg = max(gg, g + 1)
            f, g = ff, gg
            ans = max(ans, f, g)
        return ans

Continue Practicing

#2770 maximum number of jumps to reach the last index #2786 visit array positions to maximize score #2750 ways to split array into good subarrays