# Longest Non-decreasing Subarray From Two Arrays
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-non-decreasing-subarray-from-two-arrays)
Canonical: https://scaleengineer.com/dsa/problems/longest-non-decreasing-subarray-from-two-arrays
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Citadel](https://scaleengineer.com/companies/citadel)
---
## Problem
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`

# Approaches
## Dynamic Programming with Tabulation
This approach uses dynamic programming to solve the problem. The core idea is that the optimal choice for an element at index `i` depends on the choice made at index `i-1`. We can define a DP state that captures the length of the longest non-decreasing subarray ending at a particular index, considering both possible choices from `nums1` and `nums2`.
**Time:** O(n) - We iterate through the input arrays once, performing constant time operations at each step. · **Space:** O(n) - We use a 2D array of size `n x 2` to store the DP states.
**Pros:** Provides a clear and structured way to solve the problem.; The logic is relatively straightforward to follow due to the explicit DP table.
**Cons:** Uses extra space proportional to the input size, which is not optimal for large `n`.
### Explanation
We define a 2D DP array, `dp`, of size `n x 2`. `dp[i][0]` stores the length of the longest non-decreasing subarray ending at index `i` if we select `nums1[i]`, and `dp[i][1]` stores the same if we select `nums2[i]`. We iterate from the second element to the end of the arrays. For each index `i`, we calculate `dp[i][0]` and `dp[i][1]` based on the values at `i` and `i-1` and the previously computed DP values `dp[i-1][0]` and `dp[i-1][1]`. The overall maximum length is tracked throughout this process.

```java
class Solution {
    public int maxNonDecreasingLength(int[] nums1, int[] nums2) {
        int n = nums1.length;
        if (n <= 1) {
            return n;
        }
        
        int[][] dp = new int[n][2];
        // dp[i][0]: longest non-decreasing subarray ending at i using nums1[i]
        // dp[i][1]: longest non-decreasing subarray ending at i using nums2[i]
        
        dp[0][0] = 1;
        dp[0][1] = 1;
        int maxLength = 1;
        
        for (int i = 1; i < n; i++) {
            // Calculate dp[i][0] (choosing nums1[i])
            int len1 = 1;
            if (nums1[i] >= nums1[i-1]) {
                len1 = Math.max(len1, dp[i-1][0] + 1);
            }
            if (nums1[i] >= nums2[i-1]) {
                len1 = Math.max(len1, dp[i-1][1] + 1);
            }
            dp[i][0] = len1;
            
            // Calculate dp[i][1] (choosing nums2[i])
            int len2 = 1;
            if (nums2[i] >= nums1[i-1]) {
                len2 = Math.max(len2, dp[i-1][0] + 1);
            }
            if (nums2[i] >= nums2[i-1]) {
                len2 = Math.max(len2, dp[i-1][1] + 1);
            }
            dp[i][1] = len2;
            
            maxLength = Math.max(maxLength, Math.max(dp[i][0], dp[i][1]));
        }
        
        return maxLength;
    }
}
```
### Algorithm
- Create a 2D DP array, `dp[n][2]`, where `n` is the length of the input arrays.
- `dp[i][0]` will store the length of the longest non-decreasing subarray ending at index `i` if we choose `nums3[i] = nums1[i]`.
- `dp[i][1]` will store the length of the longest non-decreasing subarray ending at index `i` if we choose `nums3[i] = nums2[i]`.
- Initialize a variable `maxLength = 1` to keep track of the maximum length found so far.
- Set the base cases for index 0: `dp[0][0] = 1` and `dp[0][1] = 1`.
- Iterate from `i = 1` to `n-1`:
  - Calculate `dp[i][0]`: Initialize a temporary length to 1. If `nums1[i]` can extend a subarray ending at `i-1` (i.e., `nums1[i] >= nums1[i-1]` or `nums1[i] >= nums2[i-1]`), update the temporary length to be the maximum of its current value and the extended length (`dp[i-1][0] + 1` or `dp[i-1][1] + 1`). Assign this final temporary length to `dp[i][0]`.
  - Calculate `dp[i][1]` similarly, considering choosing `nums2[i]`.
  - Update `maxLength` with the maximum of `maxLength`, `dp[i][0]`, and `dp[i][1]`.
- After the loop, `maxLength` will hold the result.

## Space-Optimized Dynamic Programming
This approach is an optimization of the previous DP solution. By observing that the DP state at index `i` only depends on the state at `i-1`, we can get rid of the `O(n)` space DP table. Instead, we only need to maintain two variables that store the DP values for the previous index, reducing the space complexity to `O(1)`.
**Time:** O(n) - We perform a single pass through the input arrays. · **Space:** O(1) - We only use a few variables to store the previous state, regardless of the input size.
**Pros:** Extremely efficient in terms of space, using only a constant amount of extra memory.; Maintains the optimal O(n) time complexity.
**Cons:** The logic can be slightly less intuitive to grasp at first compared to the version with a full DP table.
### Explanation
We can optimize the space complexity by noticing that to compute the lengths for the current index `i`, we only need the lengths from the immediate previous index `i-1`. We don't need the entire history. Therefore, we can use just two variables, `dp1` and `dp2`, to store the lengths of the longest non-decreasing subarrays ending at the previous index. We iterate through the arrays, and in each step, we calculate the new lengths for the current index `i` using temporary variables, and then update `dp1` and `dp2` for the next iteration. The overall maximum length is updated in each step.

```java
class Solution {
    public int maxNonDecreasingLength(int[] nums1, int[] nums2) {
        int n = nums1.length;
        if (n == 0) {
            return 0;
        }
        
        int dp1 = 1; // length of LNDS ending at previous index with nums1
        int dp2 = 1; // length of LNDS ending at previous index with nums2
        int maxLength = 1;
        
        for (int i = 1; i < n; i++) {
            // Calculate length of LNDS ending at i with nums1[i]
            int current_dp1 = 1;
            if (nums1[i] >= nums1[i-1]) {
                current_dp1 = Math.max(current_dp1, dp1 + 1);
            }
            if (nums1[i] >= nums2[i-1]) {
                current_dp1 = Math.max(current_dp1, dp2 + 1);
            }
            
            // Calculate length of LNDS ending at i with nums2[i]
            int current_dp2 = 1;
            if (nums2[i] >= nums1[i-1]) {
                current_dp2 = Math.max(current_dp2, dp1 + 1);
            }
            if (nums2[i] >= nums2[i-1]) {
                current_dp2 = Math.max(current_dp2, dp2 + 1);
            }
            
            // Update dp values for the next iteration
            dp1 = current_dp1;
            dp2 = current_dp2;
            
            maxLength = Math.max(maxLength, Math.max(dp1, dp2));
        }
        
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength = 1`.
- Initialize `dp1 = 1` and `dp2 = 1`. `dp1` represents the length of the longest non-decreasing subarray ending at the *previous* index using `nums1`, and `dp2` is for `nums2`.
- Iterate from `i = 1` to `n-1`:
  - Calculate `current_dp1`, the length of the subarray ending at `i` with `nums1[i]`. This is done by checking if `nums1[i]` can extend the subarrays ending at `i-1` (which had lengths `dp1` and `dp2`).
  - `current_dp1 = max( (nums1[i] >= nums1[i-1] ? dp1 + 1 : 1), (nums1[i] >= nums2[i-1] ? dp2 + 1 : 1) )`.
  - Similarly, calculate `current_dp2` for `nums2[i]`.
  - `current_dp2 = max( (nums2[i] >= nums1[i-1] ? dp1 + 1 : 1), (nums2[i] >= nums2[i-1] ? dp2 + 1 : 1) )`.
  - Update `dp1 = current_dp1` and `dp2 = current_dp2` to be used in the next iteration.
  - Update `maxLength = max(maxLength, dp1, dp2)`.
- Return `maxLength`.

# Solutions
### Java

```java
class Solution {
public
  int maxNonDecreasingLength(int[] nums1, int[] nums2) {
    int n = nums1.length;
    int f = 1, g = 1;
    int ans = 1;
    for (int i = 1; i < n; ++i) {
      int ff = 1, gg = 1;
      if (nums1[i] >= nums1[i - 1]) {
        ff = Math.max(ff, f + 1);
      }
      if (nums1[i] >= nums2[i - 1]) {
        ff = Math.max(ff, g + 1);
      }
      if (nums2[i] >= nums1[i - 1]) {
        gg = Math.max(gg, f + 1);
      }
      if (nums2[i] >= nums2[i - 1]) {
        gg = Math.max(gg, g + 1);
      }
      f = ff;
      g = gg;
      ans = Math.max(ans, Math.max(f, g));
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxNonDecreasingLength(vector<int> &nums1, vector<int> &nums2) {
    int n = nums1.size();
    int f = 1, g = 1;
    int ans = 1;
    for (int i = 1; i < n; ++i) {
      int ff = 1, gg = 1;
      if (nums1[i] >= nums1[i - 1]) {
        ff = max(ff, f + 1);
      }
      if (nums1[i] >= nums2[i - 1]) {
        ff = max(ff, g + 1);
      }
      if (nums2[i] >= nums1[i - 1]) {
        gg = max(gg, f + 1);
      }
      if (nums2[i] >= nums2[i - 1]) {
        gg = max(gg, g + 1);
      }
      f = ff;
      g = gg;
      ans = max(ans, max(f, g));
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int: n = len(nums1) f = g = 1 ans = 1 for i in range(1, n): ff = gg = 1 if nums1[i] >= nums1[i - 1]: ff = max(ff, f + 1) if nums1[i] >= nums2[i - 1]: ff = max(ff, g + 1) if nums2[i] >= nums1[i - 1]: gg = max(gg, f + 1) if nums2[i] >= nums2[i - 1]: gg = max(gg, g + 1) f, g = ff, gg ans = max(ans, f, g) return ans

```