LeetCode 2771 - Longest Non-decreasing Subarray From Two Arrays

The problem is asking us to construct an array nums3 of length n from two given arrays nums1 and nums2 of the same length. For each index i, we can choose either nums1[i] or nums2[i] as the value for nums3[i].

leetcodemediumarraydynamic-programming

LeetCode Problem 2771

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem is asking us to construct an array nums3 of length n from two given arrays nums1 and nums2 of the same length. For each index i, we can choose either nums1[i] or nums2[i] as the value for nums3[i]. Once nums3 is constructed, we want to find the length of its longest contiguous non-decreasing subarray. The goal is to maximize this length by choosing the values in nums3 optimally.

The input arrays can be quite large (n up to 100,000), and the values themselves can be very large (1 <= nums1[i], nums2[i] <= 10^9). This means that any solution with a complexity worse than O(n) or O(n log n) will likely be too slow.

Important edge cases include arrays with all identical elements, arrays where one is strictly decreasing while the other is increasing, and arrays with length 1, since in that case the longest non-decreasing subarray is trivially 1.

The problem guarantees non-empty arrays of equal length and positive integer values, which avoids concerns about empty inputs or negative numbers.

Approaches

Brute Force

The brute-force approach would attempt to try every possible combination of choices from nums1 and nums2 for each index. For each combination, we could compute the longest non-decreasing subarray. While this approach is correct, it is infeasible because there are 2^n possible arrays nums3 for length n. Even for modest values of n, this approach would take astronomically long and is not acceptable for the constraints.

Optimal Approach

The key insight is that the problem can be solved using dynamic programming with state tracking. At each index i, we only need to track two quantities:

  1. The length of the longest non-decreasing subarray ending at index i if nums3[i] = nums1[i].
  2. The length of the longest non-decreasing subarray ending at index i if nums3[i] = nums2[i].

We can update these lengths based on the values at index i-1. Specifically, if nums1[i] >= nums1[i-1], the length can be extended from the previous length ending with nums1[i-1]. Similarly, if nums1[i] >= nums2[i-1], it can extend the length ending with nums2[i-1], and the same logic applies to nums2[i].

By iterating from left to right and keeping only the lengths for the previous index, we can solve this problem in O(n) time and O(1) extra space.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * n) O(n) Try all combinations of nums3 and compute longest non-decreasing subarray
Optimal O(n) O(1) Track two DP states for each index and update iteratively

Algorithm Walkthrough

  1. Initialize two variables len1 and len2 to 1. These represent the longest non-decreasing subarray ending at index 0 if nums3[0] is chosen from nums1 or nums2 respectively.

  2. Initialize max_len to 1 to keep track of the maximum length found so far.

  3. Iterate through the arrays from index 1 to n-1:

  4. For each index i, calculate two new lengths, new_len1 and new_len2.

  5. Set new_len1 to 1 initially. If nums1[i] >= nums1[i-1], then new_len1 = max(new_len1, len1 + 1). If nums1[i] >= nums2[i-1], then new_len1 = max(new_len1, len2 + 1).

  6. Set new_len2 to 1 initially. If nums2[i] >= nums1[i-1], then new_len2 = max(new_len2, len1 + 1). If nums2[i] >= nums2[i-1], then new_len2 = max(new_len2, len2 + 1).

  7. Update len1 to new_len1 and len2 to new_len2.

  8. Update max_len to max(max_len, len1, len2).

  9. After the loop, max_len contains the length of the longest non-decreasing subarray that can be formed.

Why it works: At each step, we maintain the maximum length of a subarray ending at that index for each choice. Since we consider all valid transitions from the previous index, we guarantee that max_len represents the global maximum.

Python Solution

from typing import List

class Solution:
    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        len1 = len2 = 1
        max_len = 1
        
        for i in range(1, n):
            new_len1 = new_len2 = 1
            
            if nums1[i] >= nums1[i - 1]:
                new_len1 = max(new_len1, len1 + 1)
            if nums1[i] >= nums2[i - 1]:
                new_len1 = max(new_len1, len2 + 1)
                
            if nums2[i] >= nums1[i - 1]:
                new_len2 = max(new_len2, len1 + 1)
            if nums2[i] >= nums2[i - 1]:
                new_len2 = max(new_len2, len2 + 1)
                
            len1, len2 = new_len1, new_len2
            max_len = max(max_len, len1, len2)
        
        return max_len

The code directly follows the algorithm. len1 and len2 track the best lengths ending with nums1[i] and nums2[i]. We update them based on previous values and keep the global maximum max_len.

Go Solution

func maxNonDecreasingLength(nums1 []int, nums2 []int) int {
    n := len(nums1)
    len1, len2 := 1, 1
    maxLen := 1
    
    for i := 1; i < n; i++ {
        newLen1, newLen2 := 1, 1
        
        if nums1[i] >= nums1[i-1] {
            newLen1 = max(newLen1, len1+1)
        }
        if nums1[i] >= nums2[i-1] {
            newLen1 = max(newLen1, len2+1)
        }
        
        if nums2[i] >= nums1[i-1] {
            newLen2 = max(newLen2, len1+1)
        }
        if nums2[i] >= nums2[i-1] {
            newLen2 = max(newLen2, len2+1)
        }
        
        len1, len2 = newLen1, newLen2
        maxLen = max(maxLen, max(len1, len2))
    }
    
    return maxLen
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

The Go implementation mirrors the Python logic. The main differences are explicit variable initialization, using a helper max function, and type-safe integer operations.

Worked Examples

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

i nums1[i] nums2[i] len1 len2 max_len
0 2 1 1 1 1
1 3 2 2 2 2
2 1 1 1 1 2

Output: 2

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

i nums1[i] nums2[i] len1 len2 max_len
0 1 2 1 1 1
1 3 2 2 2 2
2 2 3 2 3 3
3 1 4 1 4 4

Output: 4

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass over the arrays, constant work per element
Space O(1) Only two state variables (len1, len2) and some constants