Skip to content

2771. Longest Non-decreasing Subarray From Two Arrays

Description

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 the longest non-decreasing subarray in nums3.

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

 

Example 1:

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:

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:

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 <= 105
  • 1 <= nums1[i], nums2[i] <= 109

Solutions

Solution 1: Dynamic Programming

Thinking

At each index we pick from \(nums1\) or \(nums2\) and want the longest non-decreasing contiguous run. The choice sequence is exponential, but the run is contiguous, so only how adjacent columns connect matters.

Let \(f\) and \(g\) be the longest lengths ending at this column in \(nums1\) and \(nums2\), transferred from the previous column’s two choices when the values are non-decreasing. Roll the pair and keep a global maximum.

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\).

Next, we iterate over the array elements in the range \(i \in [1, n)\), and for each \(i\), we define two variables \(ff\) and \(gg\), which represent the length of the longest non-decreasing subarray ending with \(nums1[i]\) and \(nums2[i]\) respectively. When initialized, \(ff = gg = 1\).

We can calculate the values of \(ff\) and \(gg\) based on the values of \(f\) and \(g\):

  • If \(nums1[i] \ge nums1[i - 1]\), then \(ff = \max(ff, f + 1)\);
  • If \(nums1[i] \ge nums2[i - 1]\), then \(ff = \max(ff, g + 1)\);
  • If \(nums2[i] \ge nums1[i - 1]\), then \(gg = \max(gg, f + 1)\);
  • If \(nums2[i] \ge nums2[i - 1]\), then \(gg = \max(gg, g + 1)\).

Then, we update \(f = ff\) and \(g = gg\), and update \(ans\) to \(\max(ans, f, g)\).

After the iteration ends, we return \(ans\).

The time complexity is \(O(n)\), where \(n\) is the length of the array. The space complexity is \(O(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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int maxNonDecreasingLength(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int f = 1, g = 1;
        int ans = 1;
        for (int i = 1; i < n; ++i) {
            int ff = 1, gg = 1;
            if (nums1[i] >= nums1[i - 1]) {
                ff = Math.max(ff, f + 1);
            }
            if (nums1[i] >= nums2[i - 1]) {
                ff = Math.max(ff, g + 1);
            }
            if (nums2[i] >= nums1[i - 1]) {
                gg = Math.max(gg, f + 1);
            }
            if (nums2[i] >= nums2[i - 1]) {
                gg = Math.max(gg, g + 1);
            }
            f = ff;
            g = gg;
            ans = Math.max(ans, Math.max(f, g));
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int maxNonDecreasingLength(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int f = 1, g = 1;
        int ans = 1;
        for (int i = 1; i < n; ++i) {
            int ff = 1, 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 = ff;
            g = gg;
            ans = max(ans, max(f, g));
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func maxNonDecreasingLength(nums1 []int, nums2 []int) int {
    n := len(nums1)
    f, g, ans := 1, 1, 1
    for i := 1; i < n; i++ {
        ff, gg := 1, 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, max(f, g))
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function maxNonDecreasingLength(nums1: number[], nums2: number[]): number {
    const n = nums1.length;
    let [f, g, ans] = [1, 1, 1];
    for (let i = 1; i < n; ++i) {
        let [ff, gg] = [1, 1];
        if (nums1[i] >= nums1[i - 1]) {
            ff = Math.max(ff, f + 1);
        }
        if (nums1[i] >= nums2[i - 1]) {
            ff = Math.max(ff, g + 1);
        }
        if (nums2[i] >= nums1[i - 1]) {
            gg = Math.max(gg, f + 1);
        }
        if (nums2[i] >= nums2[i - 1]) {
            gg = Math.max(gg, g + 1);
        }
        f = ff;
        g = gg;
        ans = Math.max(ans, f, g);
    }
    return ans;
}

Comments