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.
In this approach, we will use Dynamic Programming (DP) to keep track of the longest non-decreasing subarrays ending at each index. We'll maintain two arrays, dp1 and dp2, where dp1[i] is the longest subarray ending at i if nums3[i] is from nums1[i], and dp2[i] is if it's from nums2[i]. For each position, you can take the maximum of either picking from nums1 or nums2, and update accordingly by checking the previous values whether they form a non-decreasing sequence.
This function utilizes dynamic programming to compute the longest non-decreasing subarray, by deciding at each index whether the element from nums1 or nums2 should be taken based on the conditions described in the DP arrays.
Time Complexity: O(n) - where n is the length of the input arrays. We iterate through the arrays only once.
Space Complexity: O(n) - for storing the dp1 and dp2 arrays.
This approach starts by selecting elements greedily from either nums1 or nums2 to maintain a non-decreasing subarray as long as possible. Compare both candidates at each index and append the most fitting one to the current subarray to potentially reach the longest non-decreasing subarray. However, with careful design of conditional logic broadly covering all scenarios, one might achieve similar outcomes with optimized checks.
This greedy Python solution operates by attempting to extend the subarray as far as possible at every step. It initializes a current value from either array and proceeds as long as choosing further elements can prolong the subsequence.
Python
Time Complexity: O(n) - as we scan the array nums1 and nums2 from start to end whilst maintaining pointers.
Space Complexity: O(1) - since we're using constant space to track lengths and values.
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 \in [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:
nums1[i] \ge nums1[i - 1], then ff = max(ff, f + 1);nums1[i] \ge nums2[i - 1], then ff = max(ff, g + 1);nums2[i] \ge nums1[i - 1], then gg = max(gg, f + 1);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).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n) - where n is the length of the input arrays. We iterate through the arrays only once. |
| Greedy Approach | Time Complexity: O(n) - as we scan the array |
| Dynamic Programming | — |
| 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. |
Leetcode Weekly contest 353 - Medium - Longest Non-decreasing Subarray From Two Arrays • Prakhar Agrawal • 2,060 views views
Watch 9 more video solutions →Practice Longest Non-decreasing Subarray From Two Arrays with our built-in code editor and test cases.
Practice on FleetCode