Problem

You are given two 0-indexed integer arrays nums1 and nums2 of length n.

Let’s define another 0-indexed integer array, nums3, of length n. For each index i in the range [0, n - 1], you can assign either nums1[i] or nums2[i] to nums3[i].

Your task is to maximize the length of the longest non-decreasing subarray in nums3 by choosing its values optimally.

Return an integer representing the length of thelongest non-decreasing subarray in nums3.

Note: A subarray is a contiguous non-empty sequence of elements within an array.

Examples

Example 1

1
2
3
4
5
6
7
8
9


    
    
    Input: nums1 = [2,3,1], nums2 = [1,2,1]
    Output: 2
    Explanation: 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

1
2
3
4
5
6
7
8
9


    
    
    Input: nums1 = [1,3,2,1], nums2 = [2,2,3,4]
    Output: 4
    Explanation: 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

1
2
3
4
5
6
7
8
9


    
    
    Input: nums1 = [1,1], nums2 = [2,2]
    Output: 2
    Explanation: 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 <= 10^5
  • 1 <= nums1[i], nums2[i] <= 10^9

Solution

Method 1 – Dynamic Programming (1)

Intuition

At each index, we can choose either value from nums1 or nums2. We keep track of the longest non-decreasing subarray ending at each index for both choices, and update based on previous values.

Approach

  1. Initialize two dp variables: dp1 and dp2, representing the length of the longest non-decreasing subarray ending at index i if we pick nums1[i] or nums2[i], respectively.
  2. For each index i > 0:
    • If nums1[i] >= nums1[i-1], extend dp1 from previous dp1.
    • If nums1[i] >= nums2[i-1], extend dp1 from previous dp2.
    • If nums2[i] >= nums1[i-1], extend dp2 from previous dp1.
    • If nums2[i] >= nums2[i-1], extend dp2 from previous dp2.
    • Otherwise, start new subarrays.
  3. Track the maximum value of dp1 and dp2 at each step.
  4. Return the maximum found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int maxNonDecreasingLength(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), ans = 1, dp1 = 1, dp2 = 1;
        for (int i = 1; i < n; ++i) {
            int t1 = 1, t2 = 1;
            if (nums1[i] >= nums1[i-1]) t1 = max(t1, dp1+1);
            if (nums1[i] >= nums2[i-1]) t1 = max(t1, dp2+1);
            if (nums2[i] >= nums1[i-1]) t2 = max(t2, dp1+1);
            if (nums2[i] >= nums2[i-1]) t2 = max(t2, dp2+1);
            dp1 = t1; dp2 = t2;
            ans = max({ans, dp1, dp2});
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func maxNonDecreasingLength(nums1, nums2 []int) int {
    n, ans := len(nums1), 1
    dp1, dp2 := 1, 1
    for i := 1; i < n; i++ {
        t1, t2 := 1, 1
        if nums1[i] >= nums1[i-1] { t1 = max(t1, dp1+1) }
        if nums1[i] >= nums2[i-1] { t1 = max(t1, dp2+1) }
        if nums2[i] >= nums1[i-1] { t2 = max(t2, dp1+1) }
        if nums2[i] >= nums2[i-1] { t2 = max(t2, dp2+1) }
        dp1, dp2 = t1, t2
        ans = max(ans, dp1, dp2)
    }
    return ans
}
func max(a, b, c int) int {
    if a > b { b = a }
    if b > c { return b }
    return c
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int maxNonDecreasingLength(int[] nums1, int[] nums2) {
        int n = nums1.length, ans = 1, dp1 = 1, dp2 = 1;
        for (int i = 1; i < n; i++) {
            int t1 = 1, t2 = 1;
            if (nums1[i] >= nums1[i-1]) t1 = Math.max(t1, dp1+1);
            if (nums1[i] >= nums2[i-1]) t1 = Math.max(t1, dp2+1);
            if (nums2[i] >= nums1[i-1]) t2 = Math.max(t2, dp1+1);
            if (nums2[i] >= nums2[i-1]) t2 = Math.max(t2, dp2+1);
            dp1 = t1; dp2 = t2;
            ans = Math.max(ans, Math.max(dp1, dp2));
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun maxNonDecreasingLength(nums1: IntArray, nums2: IntArray): Int {
        val n = nums1.size
        var ans = 1
        var dp1 = 1
        var dp2 = 1
        for (i in 1 until n) {
            var t1 = 1
            var t2 = 1
            if (nums1[i] >= nums1[i-1]) t1 = maxOf(t1, dp1+1)
            if (nums1[i] >= nums2[i-1]) t1 = maxOf(t1, dp2+1)
            if (nums2[i] >= nums1[i-1]) t2 = maxOf(t2, dp1+1)
            if (nums2[i] >= nums2[i-1]) t2 = maxOf(t2, dp2+1)
            dp1 = t1; dp2 = t2
            ans = maxOf(ans, dp1, dp2)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def maxNonDecreasingLength(self, nums1: list[int], nums2: list[int]) -> int:
        n = len(nums1)
        ans = dp1 = dp2 = 1
        for i in range(1, n):
            t1 = t2 = 1
            if nums1[i] >= nums1[i-1]: t1 = max(t1, dp1+1)
            if nums1[i] >= nums2[i-1]: t1 = max(t1, dp2+1)
            if nums2[i] >= nums1[i-1]: t2 = max(t2, dp1+1)
            if nums2[i] >= nums2[i-1]: t2 = max(t2, dp2+1)
            dp1, dp2 = t1, t2
            ans = max(ans, dp1, dp2)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn max_non_decreasing_length(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let n = nums1.len();
        let (mut ans, mut dp1, mut dp2) = (1, 1, 1);
        for i in 1..n {
            let (mut t1, mut t2) = (1, 1);
            if nums1[i] >= nums1[i-1] { t1 = t1.max(dp1+1); }
            if nums1[i] >= nums2[i-1] { t1 = t1.max(dp2+1); }
            if nums2[i] >= nums1[i-1] { t2 = t2.max(dp1+1); }
            if nums2[i] >= nums2[i-1] { t2 = t2.max(dp2+1); }
            dp1 = t1; dp2 = t2;
            ans = ans.max(dp1).max(dp2);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    maxNonDecreasingLength(nums1: number[], nums2: number[]): number {
        const n = nums1.length;
        let ans = 1, dp1 = 1, dp2 = 1;
        for (let i = 1; i < n; i++) {
            let t1 = 1, t2 = 1;
            if (nums1[i] >= nums1[i-1]) t1 = Math.max(t1, dp1+1);
            if (nums1[i] >= nums2[i-1]) t1 = Math.max(t1, dp2+1);
            if (nums2[i] >= nums1[i-1]) t2 = Math.max(t2, dp1+1);
            if (nums2[i] >= nums2[i-1]) t2 = Math.max(t2, dp2+1);
            dp1 = t1; dp2 = t2;
            ans = Math.max(ans, dp1, dp2);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the arrays. We scan the arrays once.
  • 🧺 Space complexity: O(1), only a few variables are used.