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.

Initial Attempts and Thoughts

For this problem, I initially tried to do a greedy algorithm approach. After a couple runs and failing some cases, it became quickly evident this wouldn’t work. A greedy algorithm is not optimal when locally optimal choices don’t translate to globally optimal result. The greedy algorithm logic goes like this.

When presented a choice for the ith position, we have nums1[i] or nums2[i] to pick from:

Pick the one which increases the length of the current non-decreasing subarray.
If they both do, pick the smallest of the two.

This logic works for a lot of examples. It runs into issues when we satisfy the first condition with one of the candidates but not the other, which causes us to immediately pick that option.

Counterexample input: nums1 = [4, 8, 9, 1, 2] and nums2 = [4, 2, 2, 2, 2]. When we run this through our greedy algorithm logic, the result is [4, 8, 9, 1, 2] and thus 3 is the length of the longest decreasing subarray. However, the longest is actually 4 - [2, 2, 2, 2]. The issue is at the second entry, we choose nums1[1] instead of nums2[1] since 8 continues the current non-decreasing subarray while 2 does not. This causes us to miss the longer subarray.

Another idea would be too brute-force every combination and find the longest non-decreasing subarray and then return its length. Brute-forcing every combination means checking all possible ways to pick elements from nums1 or nums2 at each index, which is \(2^n\) possibilities for length n. This is an unscalable approach as it is computationally costly even for moderately sized input arrays.

Solution: Dynamic Programming

def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:
    # dp1: length of longest non-decreasing subarray ending at i if nums1[i] is chosen
    # dp2: same, but if nums2[i] is chosen
    dp1 = dp2 = 1  
    res = 1        # res will be our overall max length

    for i in range(1, len(nums1)):
        # Store previous dp values to refer to before overwriting
        prev_dp1 = dp1
        prev_dp2 = dp2

        # Reset current dp values to 1 (at minimum, each position is length-1)
        dp1 = dp2 = 1

        # If nums1[i] continues a non-decreasing subarray from nums1[i-1] or nums2[i-1]
        if nums1[i] >= nums1[i - 1]:
            dp1 = max(dp1, prev_dp1 + 1)
        if nums1[i] >= nums2[i - 1]:
            dp1 = max(dp1, prev_dp2 + 1)

        # Same logic, but for picking nums2[i]
        if nums2[i] >= nums1[i - 1]:
            dp2 = max(dp2, prev_dp1 + 1)
        if nums2[i] >= nums2[i - 1]:
            dp2 = max(dp2, prev_dp2 + 1)

        # Update the global maximum
        res = max(res, dp1, dp2)

    return res

The dynamic programming approach works by not immediately choosing one or the other, it considers both choices, looking at the current choices and one step back. This is just enough to determine whether a choice is valid.

The greedy approach doesn’t track enough history (what is optimal now may not be optimal overall) and brute-forcing tracks too much (literally making every subarray) which is computationally expensive.

Why is looking at the current choice and one step back enough? Because our condition we are trying to satisfy is local, we only care if current ≥ previous. If our condition depends on comparisons involving the current element and elements at two previous positions (for example, something like: nums[i] ≥ nums[i-1] and nums[i] ≤ nums[i-2]), then we need to track choices to another depth (i, i-1 and i-2).

To see what this code is doing let’s test it on the example which failed in our greedy approach.

i = 1

nums1[1] = 8
- 8 ≥ 4 (nums1[0]) → dp1 = 1 + dp1_prev = 2
- 8 ≥ 4 (nums2[0]) → dp1 = max(2, 1 + dp2_prev) = 2
nums2[1] = 2
- 2 < 4 and 2 < 4 → dp2 = 1
res = max(1, 2, 1) = 2

i = 2

nums1[2] = 9
- 9 ≥ 8 → dp1 = 2 + 1 = 3
- 9 ≥ 2 → dp1 = max(3, 1 + 1) = 3
nums2[2] = 2
- 2 < 8 and 2 ≥ 2 → dp2 = 1 + 1 = 2
res = max(2, 3, 2) = 3

i = 3

nums1[3] = 1
- 1 < 9 and 1 < 2 → dp1 = 1
nums2[3] = 2
- 2 ≥ 9 → False
- 2 ≥ 2 → dp2 = 1 + 2 = 3
res = max(3, 1, 3) = 3

i = 4

nums1[4] = 2
- 2 ≥ 1 → dp1 = 1 + 1 = 2
- 2 ≥ 2 → dp1 = max(2, 3 + 1) = 4
nums2[4] = 2
- 2 ≥ 1 → dp2 = 1 + 1 = 2
- 2 ≥ 2 → dp2 = max(2, 3 + 1) = 4
res = max(3, 4, 4) = 4

Works like magic.

Intro to Dynamic Programming - Problem 2771