Longest Non-decreasing Subarray From Two Arrays

MEDIUM

Description

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 <= 10⁵
1 <= nums1[i], nums2[i] <= 10⁹

Approaches

Checkout 2 different approaches to solve Longest Non-decreasing Subarray From Two Arrays. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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;
    }
}

Complexity Analysis

Time Complexity: O(n) - We iterate through the input arrays once, performing constant time operations at each step.Space Complexity: O(n) - We use a 2D array of size `n x 2` to store the DP states.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Longest Non-decreasing Subarray From Two Arrays. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Longest Non-decreasing Subarray From Two Arrays

Patterns:

Dynamic Programming

Data Structures:

Array

Companies:

Citadel |