LeetCode 2771. Longest Non-decreasing Subarray From Two Arrays Solution in Java, C++, Python & More | Explanation + Code

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 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 ∈ [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).

PythonJavaC++GoTypeScript

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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

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; }(code-box)