Welcome to Subscribe On Youtube

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

We define two variables $f$ and $g$, which represent the longest non-decreasing subarray length at the current position, where $f$ represents the longest non-decreasing subarray length ending in the $nums1$ element, and $g$ represents the longest non-decreasing subarray length ending in the $nums2$ element. At the beginning, $f = g = 1$, and the initial answer $ans = 1$.

Next, we traverse the array elements in the range of $i \in [1, n)$, for each $i$, we define two variables $ff$ and $gg$, which represent the longest non-decreasing subarray length ending in the $nums1[i]$ and $nums2[i]$ element, respectively, and initialize $ff = gg = 1$.

We can calculate the value of $ff$ and $gg$ from 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 traversal is over, we return $ans$.

The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.

  • 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;
        }
    }
    
  • 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;
        }
    };
    
  • 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
    
    
  • 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
    }
    
    func max(a, b int) int {
    	if a > b {
    		return a
    	}
    	return b
    }
    
  • 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;
    }
    
    

All Problems

All Solutions