#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
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 innums3.
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].
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.
1class Solution {2 public int maxNonDecreasingLength(int[] nums1, int[] nums2) {3 int n = nums1.length;4 if (n <= 1) {5 return n;6 }78 int[][] dp = new int[n][2];9 // dp[i][0]: longest non-decreasing subarray ending at i using nums1[i]10 // dp[i][1]: longest non-decreasing subarray ending at i using nums2[i]1112 dp[0][0] = 1;13 dp[0][1] = 1;14 int maxLength = 1;1516 for (int i = 1; i < n; i++) {17 // Calculate dp[i][0] (choosing nums1[i])18 int len1 = 1;19 if (nums1[i] >= nums1[i-1]) {20 len1 = Math.max(len1, dp[i-1][0] + 1);21 }22 if (nums1[i] >= nums2[i-1]) {23 len1 = Math.max(len1, dp[i-1][1] + 1);24 }25 dp[i][0] = len1;2627 // Calculate dp[i][1] (choosing nums2[i])28 int len2 = 1;29 if (nums2[i] >= nums1[i-1]) {30 len2 = Math.max(len2, dp[i-1][0] + 1);31 }32 if (nums2[i] >= nums2[i-1]) {33 len2 = Math.max(len2, dp[i-1][1] + 1);34 }35 dp[i][1] = len2;3637 maxLength = Math.max(maxLength, Math.max(dp[i][0], dp[i][1]));38 }3940 return maxLength;41 }42}
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.
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).
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).
Update dp1 = current_dp1 and dp2 = current_dp2 to be used in the next iteration.
Update maxLength = max(maxLength, dp1, dp2).
Return maxLength.
Walkthrough
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.
1class Solution {2 public int maxNonDecreasingLength(int[] nums1, int[] nums2) {3 int n = nums1.length;4 if (n == 0) {5 return 0;6 }78 int dp1 = 1; // length of LNDS ending at previous index with nums19 int dp2 = 1; // length of LNDS ending at previous index with nums210 int maxLength = 1;1112 for (int i = 1; i < n; i++) {13 // Calculate length of LNDS ending at i with nums1[i]14 int current_dp1 = 1;15 if (nums1[i] >= nums1[i-1]) {16 current_dp1 = Math.max(current_dp1, dp1 + 1);17 }18 if (nums1[i] >= nums2[i-1]) {19 current_dp1 = Math.max(current_dp1, dp2 + 1);20 }2122 // Calculate length of LNDS ending at i with nums2[i]23 int current_dp2 = 1;24 if (nums2[i] >= nums1[i-1]) {25 current_dp2 = Math.max(current_dp2, dp1 + 1);26 }27 if (nums2[i] >= nums2[i-1]) {28 current_dp2 = Math.max(current_dp2, dp2 + 1);29 }3031 // Update dp values for the next iteration32 dp1 = current_dp1;33 dp2 = current_dp2;3435 maxLength = Math.max(maxLength, Math.max(dp1, dp2));36 }3738 return maxLength;39 }40}
Complexity
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.
Trade-offs
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.
Solutions
Solution
1class Solution {2public3 int maxNonDecreasingLength(int[] nums1, int[] nums2) {4 int n = nums1.length;5 int f = 1, g = 1;6 int ans = 1;7 for (int i = 1; i < n; ++i) {8 int ff = 1, gg = 1;9 if (nums1[i] >= nums1[i - 1]) {10 ff = Math.max(ff, f + 1);11 }12 if (nums1[i] >= nums2[i - 1]) {13 ff = Math.max(ff, g + 1);14 }15 if (nums2[i] >= nums1[i - 1]) {16 gg = Math.max(gg, f + 1);17 }18 if (nums2[i] >= nums2[i - 1]) {19 gg = Math.max(gg, g + 1);20 }21 f = ff;22 g = gg;23 ans = Math.max(ans, Math.max(f, g));24 }25 return ans;26 }27}
1class Solution {2public:3 int maxNonDecreasingLength(vector<int> &nums1, vector<int> &nums2) {4 int n = nums1.size();5 int f = 1, g = 1;6 int ans = 1;7 for (int i = 1; i < n; ++i) {8 int ff = 1, gg = 1;9 if (nums1[i] >= nums1[i - 1]) {10 ff = max(ff, f + 1);11 }12 if (nums1[i] >= nums2[i - 1]) {13 ff = max(ff, g + 1);14 }15 if (nums2[i] >= nums1[i - 1]) {16 gg = max(gg, f + 1);17 }18 if (nums2[i] >= nums2[i - 1]) {19 gg = max(gg, g + 1);20 }21 f = ff;22 g = gg;23 ans = max(ans, max(f, g));24 }25 return ans;26 }27};
1class Solution:2 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
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.
