Longest Non-decreasing Subarray From Two Arrays

Medium

Google

1 view

Topics:

ArraysDynamic Programming

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^5
1 <= nums1[i], nums2[i] <= 10^9

Longest Non-decreasing Subarray From Two Arrays

Medium

Google

1 view

Topics:

ArraysDynamic Programming

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^5
1 <= nums1[i], nums2[i] <= 10^9

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the integer values in arrays A and B, and what is the maximum possible length of the arrays?
Can arrays A and B be empty or null? If so, what should the return value be?
If there are multiple non-decreasing subarrays of the same maximum length, is any one of them acceptable, or should I return a specific one (e.g., the first occurrence)?
Are we looking for a *strictly* non-decreasing subarray, or is it okay if consecutive elements are equal?
By 'subarray', do you mean a contiguous section of the combined sequence of numbers selected from A or B?

Brute Force Solution

Approach

The brute force method is about trying absolutely everything. We will generate every possible sequence of numbers by picking from the two original lists and then check if each sequence is non-decreasing to find the longest one.

Here's how the algorithm would work step-by-step:

Imagine we have two stacks of cards, each with numbers written on them.
We'll start building a new sequence by picking a card from the top of either the first stack or the second stack.
Then, we'll pick another card from either stack, adding it to our sequence.
We keep doing this, trying every possible combination of cards from the two stacks.
Each time we build a sequence, we check if the numbers are in non-decreasing order (each number is at least as big as the one before it).
If a sequence is non-decreasing, we compare its length to the longest non-decreasing sequence we've found so far.
If the new sequence is longer, it becomes our new longest sequence.
After trying every possible combination of cards, the longest non-decreasing sequence we've found is our answer.

Code Implementation

def longest_non_decreasing_subarray_brute_force(first_array, second_array):
    longest_sequence_length = 0

    def generate_sequences(current_sequence, first_index, second_index):
        nonlocal longest_sequence_length

        # Base case: If both arrays are exhausted
        if first_index == len(first_array) and second_index == len(second_array):
            if len(current_sequence) > 0:
                is_non_decreasing = all(current_sequence[i] <= current_sequence[i+1] for i in range(len(current_sequence)-1))
                if is_non_decreasing:
                    longest_sequence_length = max(longest_sequence_length, len(current_sequence))
            return

        # Recursive step: Try picking from the first array
        if first_index < len(first_array):
            #Explore with value from first array
            generate_sequences(current_sequence + [first_array[first_index]], first_index + 1, second_index)

            #If the current element of the first array is larger, then we explore the second array

        # Recursive step: Try picking from the second array
        if second_index < len(second_array):
            generate_sequences(current_sequence + [second_array[second_index]], first_index, second_index + 1)

    generate_sequences([], 0, 0)
    return longest_sequence_length

Big(O) Analysis

Time Complexity

O(2^n * n) – The algorithm explores all possible subsequences that can be formed by picking elements from the two arrays. Since at each step, we have two choices (pick from array1 or array2), and there are n total elements to potentially pick, there are 2^n possible subsequences. For each subsequence, we need to check if it is non-decreasing, which takes O(n) time. Therefore, the overall time complexity is O(2^n * n).

Space Complexity

O(2^N) – The brute force method generates every possible subsequence by picking elements from the two input arrays. In the worst-case scenario, where N is the length of each input array, this involves exploring 2^N different combinations (each element can be chosen from either the first or second array). Each of these combinations needs to be stored temporarily to check if it is non-decreasing and to compare its length. Therefore, the auxiliary space required to store these sequences grows exponentially with the input size N, leading to O(2^N) space complexity. Note that the length of the longest non-decreasing subarray can be at most N; however, in this brute-force approach, we store all possible combinations, regardless of whether they are non-decreasing or not.

Optimal Solution

Approach

The key is to build the longest possible line as you go, without needing to backtrack or reconsider past decisions. We keep track of the current best line, and then extend it if possible, or start a new one if needed.

Here's how the algorithm would work step-by-step:

Start with a length of zero, meaning you haven't built any part of the line yet.
At each position, look at your two choices: either pick from the first list or pick from the second list.
If your current choice is at least as big as the last number in your line (meaning it doesn't break the non-decreasing rule), add it to the line and increase the line length.
If your current choice *does* break the rule, your current line ends. Start a new line with a length of one, beginning with your current choice.
Keep track of the longest line you've made so far. This will always be the best non-decreasing sequence you've seen.
Do this until you reach the end of both lists. The longest line you tracked is your final answer.

Code Implementation

def longest_non_decreasing_subarray(array1, array2):
    longest_length = 0
    current_length = 0
    last_value = float('-inf')

    for i in range(len(array1)):
        # Choice from the first array.
        if array1[i] >= last_value:
            current_length += 1
            last_value = array1[i]
        else:
            current_length = 1
            last_value = array1[i]

        longest_length = max(longest_length, current_length)

        # Reset current length for the second array.
        current_length_array2 = 0
        last_value_array2 = float('-inf')

        # Choice from the second array.
        if array2[i] >= last_value:
            current_length = 1 + current_length_array2
            last_value = array2[i]
            current_length_array2 +=1
        else:
            # Current choice breaks rule, start a new subarray
            current_length = 1
            last_value = array2[i]
            current_length_array2 +=1

        longest_length = max(longest_length, current_length)

        # To account for array2 subarrays continuing after array1 reset
        if array2[i] >= last_value_array2:
            current_length_array2 += 1
            last_value_array2 = array2[i]
        else:
            # Break, restart array 2 sequence
            current_length_array2 = 1
            last_value_array2 = array2[i]

        # Keep track of longest length
        longest_length = max(longest_length, current_length_array2)

    # The maximum length represents the longest subarray seen so far
    return longest_length

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the arrays once. At each index, it makes a constant number of comparisons: it checks if the current element from array1 can extend the current longest non-decreasing subarray, and then checks if the current element from array2 can extend the current longest non-decreasing subarray. The length of the arrays is denoted by n. Thus, the time complexity is directly proportional to n.

Space Complexity

O(1) – The algorithm maintains a constant number of variables to track the current line length and the longest line length seen so far. No auxiliary data structures that scale with the input size are used. Therefore, the space complexity is independent of the input size N and remains constant.

Edge Cases

Case	How to Handle
Empty arrays A or B	Return 0, as there's no subarray possible.
Arrays A and B have only one element	Return 1 if A[0] <= B[0] or B[0] <= A[0], otherwise 0.
Arrays A and B are of different lengths	The algorithm should iterate up to the length of the shorter array.
Arrays A and B contain all identical values	If all A values are the same and all B values are the same, the solution should find the longest possible length.
Arrays A and B are strictly decreasing	The algorithm should correctly identify subarrays of length 1 or 0.
Arrays A and B contain negative numbers	The non-decreasing comparison should handle negative numbers correctly.
Integer overflow when calculating length	Use appropriate data types (e.g., long) or check for potential overflow during length calculation.
Large input arrays to test performance/scalability	The solution's time complexity should be considered and optimized if necessary (e.g., dynamic programming).