Watch 10 video solutions for Longest Non-decreasing Subarray From Two Arrays, a medium level problem involving Array, Dynamic Programming. This walkthrough by Prakhar Agrawal has 2,060 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1051 <= nums1[i], nums2[i] <= 109Problem Overview: You are given two arrays nums1 and nums2 of equal length. At each index i, you must choose either nums1[i] or nums2[i]. The goal is to build the longest possible contiguous sequence where the chosen values form a non‑decreasing subarray.
Approach 1: Dynamic Programming (O(n) time, O(1) space)
Track two states while iterating through the arrays: the longest non‑decreasing subarray ending at index i if you pick nums1[i], and the longest if you pick nums2[i]. For each index, compare the current candidate with both values chosen at i-1. If nums1[i] >= nums1[i-1], extend the previous state that also ended with nums1. If nums1[i] >= nums2[i-1], extend the state that ended with nums2. Repeat the same logic for choosing nums2[i]. Update the maximum length during the iteration. This works because the only dependency for a non‑decreasing subarray is the previous element, so maintaining two running states captures every valid transition efficiently. Time complexity is O(n) and space complexity is O(1).
Approach 2: Greedy with State Tracking (O(n) time, O(1) space)
The greedy idea is similar but focuses on extending the longest valid sequence whenever possible. At each index, attempt to extend the current sequence by comparing the chosen value with both possible previous values. Maintain two running lengths representing sequences ending with nums1 or nums2. Always pick the transition that keeps the sequence non‑decreasing and maximizes the length. If neither option maintains order, reset the length to 1. This approach avoids storing full DP arrays and instead updates only the current state. Time complexity remains O(n) with O(1) space.
Both approaches rely on understanding that the constraint is purely local: each step only depends on the previous chosen value. This makes the problem a clean application of dynamic programming with constant memory, operating over sequential comparisons in an array. The greedy formulation is effectively a compressed DP state transition often seen in sequence optimization problems.
Recommended for interviews: The Dynamic Programming approach is what interviewers expect. It shows you can model multiple states and transitions clearly. Starting with the DP reasoning and then optimizing to constant space demonstrates strong understanding of greedy state compression. The greedy variant is essentially the same logic but expressed more compactly.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Two States | O(n) | O(1) | General solution. Best for explaining transitions clearly during interviews. |
| Greedy State Compression | O(n) | O(1) | When you recognize the DP states can be maintained with only current values. |