2771. Longest Non-decreasing Subarray From Two Arrays
Problem Description
In this problem, you have two integer arrays nums1
and nums2
, both containing n
elements, indexed from 0. Your goal is to create a third array nums3
, also with n
elements, where each element at index i
is either the element from nums1[i]
or nums2[i]
. You want to fill nums3
such that it contains the longest non-decreasing subarray possible; basically, you want nums3
to have the longest sequence where elements from left to right are not in descending order. The desired output is the length of this longest non-decreasing subarray in nums3
.
A non-decreasing subarray is a contiguous sequence of elements that go from left to right without decreasing in value. In other words, every element is greater than or equal to the element that comes before it.
Intuition
The intuition behind the solution involves dynamic programming, a method that solves problems by combining solutions to subproblems and using these solutions to construct an answer for the larger problem.
Since for each index i
, you can choose either nums1[i]
or nums2[i]
for the nums3
array, there can be many potential combinations to consider. However, we only need to keep track of the longest subarray lengths up to the current position for both potential choices. Here we define two states: f
to represent the length of the longest non-decreasing subarray that ends with an element from nums1
, and g
to represent the length of the longest non-decreasing subarray that ends with an element from nums2
.
To arrive at the solution, we start by initializing f
and g
to 1, as the longest subarray at the start can only be of length 1. As we iterate through each index starting from 1, we determine the possible lengths of f
and g
by checking if the current elements in nums1
and nums2
can extend the non-decreasing subarrays ending at the previous index.
For each element at index i
, if nums1[i]
is greater than or equal to the previous elements (nums1[i-1]
or nums2[i-1]
), we can extend the non-decreasing subarray ending with nums1[i-1]
or nums2[i-1]
. The same applies for nums2[i]
. At each step, we update f
and g
to the longer of the current value of f
or g
and the length of the new non-decreasing subarray, which can be an extension of f
or g
from the previous step. Finally, the answer is the maximum value of f
and g
after traversing all elements.
This dynamic approach ensures that we do not need to evaluate all possible combinations of elements from nums1
and nums2
; instead, we can efficiently calculate the length of the longest non-decreasing subarray by considering each position's optimal choice based on the previous computations.
Learn more about Dynamic Programming patterns.
Solution Approach
The implementation of the solution makes use of a dynamic programming strategy. It involves tracking the potential longest non-decreasing subarray lengths dynamically as we iterate through the arrays. Here's a breakdown of how the algorithm works and the concepts it uses:
-
Initialization of States: We start with two variables,
f
andg
, both set to 1 because, at the very beginning, the longest non-decreasing subarray that can be formed will just include the first element from eithernums1
ornums2
. The variableans
is also set to 1, to track the length of the longest subarray found so far. -
Iteration through Arrays: We loop through the arrays starting from index 1, as the 0th index is already considered in our initial state.
-
State Transition: For each index
i
, we compute two temporary variablesff
andgg
which represent the potential new values off
andg
based on whether the current elements at indexi
can extend the longest non-decreasing subarray up to indexi - 1
. This involves four scenarios for updatingff
andgg
:- If
nums1[i]
is not smaller thannums1[i - 1]
, the subarray ending withnums1[i - 1]
can be extended, so we updateff
tomax(ff, f + 1)
. - If
nums1[i]
is not smaller thannums2[i - 1]
, the subarray ending withnums2[i - 1]
can be extended, so we updateff
tomax(ff, g + 1)
. - If
nums2[i]
is not smaller thannums1[i - 1]
, the subarray ending withnums1[i - 1]
can be extended, so we updategg
tomax(gg, f + 1)
. - If
nums2[i]
is not smaller thannums2[i - 1]
, the subarray ending withnums2[i - 1]
can be extended, so we updategg
tomax(gg, g + 1)
.
- If
-
State Update: After calculating
ff
andgg
, we setf
andg
to these new values, as they represent the updated longest non-decreasing subarray lengths ending at indexi
fornums1
andnums2
respectively. -
Answer Calculation: With each iteration, the
ans
variable is updated to reflect the maximum value amongans
,f
, andg
. This ensures that after traversing the entire array,ans
holds the length of the longest non-decreasing subarray that can be formed.
The code uses a simple for
loop for iteration and max
function calls for comparison to execute this algorithm effectively. By only maintaining the necessary states, we optimize space complexity while ensuring that the program runs in linear time relative to the size of the given arrays.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach.
Assume our input arrays are nums1 = [3, 4, 2, 6]
and nums2 = [1, 2, 3, 4]
, and we wish to construct nums3
with the longest non-decreasing subarray.
Initially, we set f = 1
, g = 1
, and ans = 1
, since the longest non-decreasing subarray at the beginning can only include one of the first elements.
Now we proceed to iterate through each index, starting from 1.
For i = 1
:
- We compute temporary variables
ff
andgg
; at the start of every iteration, they are set to zero. - Since
nums1[1]
(4) is not smaller thannums1[i - 1]
(3), we can extend the subarray ending withnums1[i - 1]
. Thus,ff = max(ff, f + 1) => ff = max(0, 1 + 1) => ff = 2
. - Since
nums1[1]
(4) is also not smaller thannums2[i - 1]
(1), we can extend the subarray ending withnums2[i - 1]
. Thus,ff = max(ff, g + 1) => ff = max(2, 1 + 1) => ff = 2
. nums2[1]
(2) is not smaller thannums1[i - 1]
(3), so we cannot extend fromnums1[i - 1]
this time;gg
remains the same.- Since
nums2[1]
(2) is not smaller thannums2[i - 1]
(1), we can extend the subarray ending withnums2[i - 1]
. Thus,gg = max(gg, g + 1) => gg = max(0, 1 + 1) => gg = 2
. - We now perform the state update,
f = ff
andg = gg
, setting bothf
andg
to 2.
Now, ans
is updated to be the max of ans
, f
, and g
, which is max(1, 2, 2)
, so ans
becomes 2.
Repeating this process for the rest of the indices:
For i = 2
:
nums1[2]
(2) is smaller thannums1[i - 1]
(4), soff
does not update based onf
.- But
nums1[2]
(2) is not smaller thannums2[i - 1]
(2), soff = max(ff, g + 1) => ff = max(0, 2 + 1) => ff = 3
. nums2[2]
(3) is not smaller thannums1[i - 1]
(4), sogg
does not update based onf
.nums2[2]
(3) is larger thannums2[i - 1]
(2), sogg = max(gg, g + 1) => gg = max(0, 2 + 1) => gg = 3
.- Reset
f
andg
to their new valuesff
andgg
, respectively, both are now 3. ans = max(ans, f, g) => ans = max(2, 3, 3) => ans = 3
.
For i = 3
:
nums1[3]
(6) is larger than bothnums1[i - 1]
(2) andnums2[i - 1]
(3), soff
becomesmax(0, f + 1)
andmax(0, g + 1)
, resulting inff = 4
.nums2[3]
(4) is larger thannums1[i - 1]
(2) but notnums2[i - 1]
(3), sogg
only updates fromf
, givinggg = max(0, f + 1) => gg = 4
.- State update puts
f = 4
andg = 4
. ans
updates tomax(ans, f, g) => ans = max(3, 4, 4) => ans = 4
.
In the end, the longest non-decreasing subarray that can be created (nums3
) is of length 4, which is our answer. Thus, nums3
can be [3, 4, 3, 4]
or [3, 4, 2, 4]
, both of which have the longest non-decreasing subarray of length 4.
Solution Implementation
1from typing import List
2
3class Solution:
4 def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:
5 # Get the length of the input lists
6 n = len(nums1)
7
8 # Initialize the lengths of non-decreasing sequences ending with the last element of nums1 and nums2
9 max_length_end_nums1 = max_length_end_nums2 = 1
10
11 # Initialize the answer with 1, since the smallest non-decreasing sequence has at least one element
12 max_length = 1
13
14 # Iterate through the lists starting from the second element
15 for i in range(1, n):
16 # Initialize new max lengths for the current iteration
17 new_max_length_end_nums1 = new_max_length_end_nums2 = 1
18
19 # Update the new_max_length_end_nums1 if the current nums1 element is not decreasing compared to the previous one
20 if nums1[i] >= nums1[i - 1]:
21 new_max_length_end_nums1 = max(new_max_length_end_nums1, max_length_end_nums1 + 1)
22
23 # Update the new_max_length_end_nums1 if the current nums1 element is not decreasing compared to the previous nums2 element
24 if nums1[i] >= nums2[i - 1]:
25 new_max_length_end_nums1 = max(new_max_length_end_nums1, max_length_end_nums2 + 1)
26
27 # Update the new_max_length_end_nums2 if the current nums2 element is not decreasing compared to the previous nums1 element
28 if nums2[i] >= nums1[i - 1]:
29 new_max_length_end_nums2 = max(new_max_length_end_nums2, max_length_end_nums1 + 1)
30
31 # Update the new_max_length_end_nums2 if the current nums2 element is not decreasing compared to the previous nums2 element
32 if nums2[i] >= nums2[i - 1]:
33 new_max_length_end_nums2 = max(new_max_length_end_nums2, max_length_end_nums2 + 1)
34
35 # Update the lengths of non-decreasing sequences ending with the last element of nums1 and nums2
36 max_length_end_nums1, max_length_end_nums2 = new_max_length_end_nums1, new_max_length_end_nums2
37
38 # Update the global max_length if necessary
39 max_length = max(max_length, max_length_end_nums1, max_length_end_nums2)
40
41 # Return the length of the maximum non-decreasing sequence that can be made
42 return max_length
43
1class Solution {
2
3 /**
4 * Computes the maximum length of a non-decreasing sequence from two arrays.
5 * The non-decreasing sequence can switch between arrays at any point.
6 *
7 * @param nums1 The first input array.
8 * @param nums2 The second input array.
9 * @return The maximum length of a non-decreasing sequence.
10 */
11 public int maxNonDecreasingLength(int[] nums1, int[] nums2) {
12 int n = nums1.length; // Length of the input arrays.
13 int maxLengthNums1 = 1; // Tracks max non-dec length ending with an element from nums1.
14 int maxLengthNums2 = 1; // Tracks max non-dec length ending with an element from nums2.
15 int ans = 1; // Stores the overall maximum non-decreasing length.
16
17 // Loop through both arrays starting from the second element.
18 for (int i = 1; i < n; ++i) {
19 int tempMaxLengthNums1 = 1; // Temp variable for non-dec length ending with nums1[i].
20 int tempMaxLengthNums2 = 1; // Temp variable for non-dec length ending with nums2[i].
21
22 // If the current element in nums1 is not smaller than the previous one in nums1,
23 // update the temporary maximum for nums1.
24 if (nums1[i] >= nums1[i - 1]) {
25 tempMaxLengthNums1 = Math.max(tempMaxLengthNums1, maxLengthNums1 + 1);
26 }
27
28 // If the current element in nums1 is not smaller than the previous one in nums2,
29 // update the temporary maximum for nums1.
30 if (nums1[i] >= nums2[i - 1]) {
31 tempMaxLengthNums1 = Math.max(tempMaxLengthNums1, maxLengthNums2 + 1);
32 }
33
34 // If the current element in nums2 is not smaller than the previous one in nums1,
35 // update the temporary maximum for nums2.
36 if (nums2[i] >= nums1[i - 1]) {
37 tempMaxLengthNums2 = Math.max(tempMaxLengthNums2, maxLengthNums1 + 1);
38 }
39
40 // If the current element in nums2 is not smaller than the previous one in nums2,
41 // update the temporary maximum for nums2.
42 if (nums2[i] >= nums2[i - 1]) {
43 tempMaxLengthNums2 = Math.max(tempMaxLengthNums2, maxLengthNums2 + 1);
44 }
45
46 // Update the lengths for the current element.
47 maxLengthNums1 = tempMaxLengthNums1;
48 maxLengthNums2 = tempMaxLengthNums2;
49
50 // Calculate the maximum length considering both nums1 and nums2.
51 ans = Math.max(ans, Math.max(maxLengthNums1, maxLengthNums2));
52 }
53
54 // Return the overall maximum non-decreasing length found.
55 return ans;
56 }
57}
58
1class Solution {
2public:
3 // Method to find the length of the longest non-decreasing subsequence that can be obtained
4 // by choosing elements either from nums1 or nums2 at each step, under the constraint
5 // that we can't switch from nums2 back to nums1.
6 int maxNonDecreasingLength(vector<int>& nums1, vector<int>& nums2) {
7 int n = nums1.size(); // Get the size of the input vectors
8
9 // Initialize lengths for non-decreasing subsequences ending with nums1[i] and nums2[i]
10 int lengthNums1 = 1, lengthNums2 = 1;
11
12 // Initialize the answer with a subsequence of length 1
13 int maxSequenceLength = 1;
14
15 // Loop through the array to compute the maximum length of non-decreasing subsequence
16 for (int i = 1; i < n; ++i) {
17 // Temporary variables to hold possible new lengths for the current index
18 int newLengthNums1 = 1, newLengthNums2 = 1;
19
20 // If the current element of nums1 is not smaller than the previous element of nums1,
21 // update the new length for nums1.
22 if (nums1[i] >= nums1[i - 1]) {
23 newLengthNums1 = max(newLengthNums1, lengthNums1 + 1);
24 }
25
26 // If the current element of nums1 is not smaller than the previous element of nums2,
27 // update the new length for nums1. This indicates switching from nums2 to nums1.
28 if (nums1[i] >= nums2[i - 1]) {
29 newLengthNums1 = max(newLengthNums1, lengthNums2 + 1);
30 }
31
32 // If the current element of nums2 is not smaller than the previous element of nums1,
33 // update the new length for nums2.
34 if (nums2[i] >= nums1[i - 1]) {
35 newLengthNums2 = max(newLengthNums2, lengthNums1 + 1);
36 }
37
38 // If the current element of nums2 is not smaller than the previous element of nums2,
39 // update the new length for nums2.
40 if (nums2[i] >= nums2[i - 1]) {
41 newLengthNums2 = max(newLengthNums2, lengthNums2 + 1);
42 }
43
44 // Update the lengths with the new computed values
45 lengthNums1 = newLengthNums1;
46 lengthNums2 = newLengthNums2;
47
48 // Update the maxSequenceLength considering the lengths of both nums1 and nums2
49 maxSequenceLength = max(maxSequenceLength, max(lengthNums1, lengthNums2));
50 }
51
52 // Return the computed maximum length of the non-decreasing subsequence
53 return maxSequenceLength;
54 }
55};
56
1/**
2 * Calculates the maximum length of a non-decreasing sequence
3 * that can be formed by elements taken from either nums1 or nums2
4 * at each position while maintaining the order.
5 * @param nums1 - The first array of numbers.
6 * @param nums2 - The second array of numbers.
7 * @returns The maximum length of a non-decreasing sequence from nums1 or nums2.
8 */
9function maxNonDecreasingLength(nums1: number[], nums2: number[]): number {
10 const n: number = nums1.length;
11 // Initialize lengths of non-decreasing subsequences for nums1 and nums2
12 let nums1Length: number = 1;
13 let nums2Length: number = 1;
14 // Initialize the global maximum length
15 let maxLength: number = 1;
16
17 // Iterate through the arrays to determine the non-decreasing subsequences
18 for (let i = 1; i < n; ++i) {
19 // Temporary variables to store the subsequence lengths at the current iteration
20 let nextNums1Length: number = 1;
21 let nextNums2Length: number = 1;
22
23 // Check and update the non-decreasing subsequence length for nums1
24 if (nums1[i] >= nums1[i - 1]) {
25 nextNums1Length = Math.max(nextNums1Length, nums1Length + 1);
26 }
27 if (nums1[i] >= nums2[i - 1]) {
28 nextNums1Length = Math.max(nextNums1Length, nums2Length + 1);
29 }
30
31 // Check and update the non-decreasing subsequence length for nums2
32 if (nums2[i] >= nums1[i - 1]) {
33 nextNums2Length = Math.max(nextNums2Length, nums1Length + 1);
34 }
35 if (nums2[i] >= nums2[i - 1]) {
36 nextNums2Length = Math.max(nextNums2Length, nums2Length + 1);
37 }
38
39 // Update the current lengths of the subsequences for nums1 and nums2
40 nums1Length = nextNums1Length;
41 nums2Length = nextNums2Length;
42
43 // Update the global maximum length
44 maxLength = Math.max(maxLength, nums1Length, nums2Length);
45 }
46
47 return maxLength;
48}
49
Time and Space Complexity
The time complexity of this code is O(n)
, where n
is the length of the input arrays nums1
and nums2
. The code consists of a single loop that iterates from 1
to n-1
, performing a constant amount of work for each element with no nested loops, resulting in a linear time complexity.
The space complexity of the code is O(1)
, as it uses a fixed number of integer variables (f
, g
, ff
, gg
, ans
, and n
). No additional space that grows with the input size is utilized, resulting in constant space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following array represent a max heap?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.