Scale Engineer

Longest Non-decreasing Subarray From Two Arrays

Med
#2488Time: 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.1 company
Patterns
Dynamic Programming
Data structures
Array
Companies
Citadel

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

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.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem