Skip to main content
Talentd

Longest Non-decreasing Subarray From Two Arrays - Solution & Explanation

MediumArrayDynamic Programming19 min readAsked at: Amazon, Visa, Google +3
Practice this problem

Problem Statement

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

Approach Overview

Problem 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 1: Dynamic Programming Approach

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.

Code

PythonC++JavaC#JavaScriptC

Python

C++

Java

C#

JavaScript

C

Complexity

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.

Try this approach in the editor →

Approach 2: Greedy Approach

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.

Code

Python

Python

Complexity

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.

Try this approach in the editor →

Approach 3: 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 \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:

  • 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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

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.

Greedy Approach

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.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with Two StatesO(n)O(1)General solution. Best for explaining transitions clearly during interviews.
Greedy State CompressionO(n)O(1)When you recognize the DP states can be maintained with only current values.

Video Solution

Leetcode Weekly contest 353 - Medium - Longest Non-decreasing Subarray From Two Arrays • Prakhar Agrawal • 2,065 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Longest Non-decreasing Subarray From Two Arrays easy or hard?
This problem is generally classified as Medium difficulty. The challenge comes from modeling the two choices at every index and handling transitions correctly. Once the dynamic programming states are identified, the implementation becomes straightforward.
Longest Non-decreasing Subarray From Two Arrays Python/Java solution
Python and Java implementations typically use two integer variables representing the sequence length if the current element is chosen from nums1 or nums2. Update these values at each step based on comparisons with the previous elements. Both implementations run in O(n) time and O(1) space.
How to solve Longest Non-decreasing Subarray From Two Arrays in O(n)?
Iterate through both arrays and maintain two DP values: the longest subarray ending at index i when choosing nums1[i] and when choosing nums2[i]. Compare each candidate with nums1[i-1] and nums2[i-1] to determine valid transitions. Update the lengths and keep a global maximum. This single pass gives O(n) time and constant space.
What is the best approach for Longest Non-decreasing Subarray From Two Arrays?
Dynamic Programming with two running states is the most reliable approach. Track the longest non-decreasing subarray ending at index i if you pick nums1[i] or nums2[i]. Each step compares the current values with both previous choices. This yields an O(n) time and O(1) space solution.
Is Longest Non-decreasing Subarray From Two Arrays asked at Google/Amazon/Meta?
Problems involving dynamic programming over arrays and sequence transitions frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that require maintaining multiple state choices or comparing previous selections are common in mid-level algorithm rounds.
What data structure is used in Longest Non-decreasing Subarray From Two Arrays?
The solution mainly uses arrays and constant variables to track dynamic programming states. No complex data structures like heaps or trees are required. The key idea is maintaining two running sequence lengths while iterating through the arrays.
What is the time complexity of Longest Non-decreasing Subarray From Two Arrays?
The optimal solution runs in O(n) time because the arrays are scanned once while maintaining two state values. Each index performs a constant number of comparisons. Space complexity is O(1) since only the previous state lengths are stored.

Ready to solve this problem?

Practice Longest Non-decreasing Subarray From Two Arrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Length of Pair Chain

Next

Russian Doll Envelopes