Longest Non-decreasing Subarray From Two Arrays

Longest Non-decreasing Subarray From Two Arrays

What is this problem about?

This array problem gives you two arrays of the exact same length, nums1 and nums2. You need to construct a brand new array nums3 of the same length, where each element nums3[i] is chosen to be either nums1[i] or nums2[i]. Your objective is to make these choices in a way that maximizes the length of the longest contiguous non-decreasing subarray within nums3.

Why is this asked in interviews?

This problem is a fantastic test of a candidate's grasp of state-machine Dynamic Programming. Interviewers ask it because it forces candidates to manage multiple parallel states simultaneously. It moves beyond simple "include or exclude" logic and asks "if I pick from array A, how does it affect the chain versus if I pick from array B?" It is highly representative of real-world optimization problems where multiple valid configurations exist at each step.

Algorithmic pattern used

This problem is solved using Dynamic Programming with two states. Since at any index i we can choose from either array, we maintain two DP arrays (or just two variables to optimize space):

• dp1[i]: The length of the longest non-decreasing subarray ending at index i, assuming nums3[i] was picked from nums1.
• dp2[i]: The length of the longest non-decreasing subarray ending at index i, assuming nums3[i] was picked from nums2. We update these values by checking if the current choice is $\ge$ the previous choices from either nums1[i-1] or nums2[i-1].

Example explanation

Let nums1 = [2, 3, 1] and nums2 = [1, 2, 1]. At index 0:

• Pick nums1[0] (2): dp1[0] = 1.
• Pick nums2[0] (1): dp2[0] = 1.

At index 1:

• To pick nums1[1] (3):
  • Is $3 \ge nums1[0]$ (2)? Yes. We can extend dp1: $1 + 1 = 2$.
  • Is $3 \ge nums2[0]$ (1)? Yes. We can extend dp2: $1 + 1 = 2$.
  • dp1[1] = max(2, 2) = 2.
• To pick nums2[1] (2):
  • Is $2 \ge nums1[0]$ (2)? Yes. Extend dp1: $1 + 1 = 2$.
  • Is $2 \ge nums2[0]$ (1)? Yes. Extend dp2: $1 + 1 = 2$.
  • dp2[1] = 2.

At index 2:

• To pick nums1[2] (1): It is not $\ge$ 3, nor $\ge$ 2. The chain breaks. dp1[2] = 1.
• To pick nums2[2] (1): It is not $\ge$ 3, nor $\ge$ 2. Chain breaks. dp2[2] = 1.

The maximum value across all states is 2. The subarray is [2, 3] or [1, 2].

Common mistakes candidates make

A frequent mistake is trying to be greedy—for instance, always picking the smaller of the two arrays at index i to leave "room for growth." This greedy logic fails because picking a smaller number might break an already existing, highly lucrative sequence that relied on the larger number. This problem exhibits strict overlapping subproblems and optimal substructure, making DP mandatory.

Interview preparation tip

For the Longest Non-decreasing Subarray From Two Arrays coding problem, practice space optimization. Because dp[i] only relies on dp[i-1], you don't need full arrays. You can solve this in $O(1)$ space by using just two variables (e.g., prev_dp1 and prev_dp2), updating them iteratively. This optimization transforms a "good" solution into an "exceptional" one in an interview setting.