We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Non-decreasing Subarray From Two Arrays

Number: 2869

Difficulty: Medium

Paid? No

Companies: Citadel, Meesho, Polar

Problem Description

Given two 0-indexed arrays, nums1 and nums2, of equal length n, we must construct a new array nums3 such that for each index i (0 ≤ i < n) we can choose either nums1[i] or nums2[i]. Our goal is to maximize the length of the longest contiguous (subarray) non-decreasing segment in nums3.

Key Insights

  • At each index i, there are two options; the decision at index i affects whether the non-decreasing condition holds relative to the choice at index i-1.
  • We can use dynamic programming where the state is based on the choice at the previous index and updated based on valid transitions.
  • Maintain two DP states at each index:
    • dp1: the longest non-decreasing subarray ending at i if we choose nums1[i].
    • dp2: the longest non-decreasing subarray ending at i if we choose nums2[i].
  • Transitions are determined by comparing the current value with the prior value chosen from either nums1 or nums2.
  • The answer is the maximum value found over all indices among the two DP states.

Space and Time Complexity

Time Complexity: O(n) – we traverse the arrays once.
Space Complexity: O(1) – by storing only dp1 and dp2 from previous index, constant space is used.

Solution

The approach is to iterate through the indices of the arrays, maintaining two variables (dp1 and dp2) representing the length of the longest non-decreasing subarray ending at the current index if we take the value from nums1 or nums2 respectively. For each index, we check the valid transitions:

  • If choosing nums1[i] and if nums1[i] is at least as large as the previous value from either nums1 (if that state was chosen) or nums2, then extend the corresponding dp value.
  • Similarly for choosing nums2[i]. At each step, update a global maximum with the maximum of dp1 and dp2 for that index. This ensures we capture the maximum possible length overall.

Code Solutions

# Python solution
def longestNonDecreasingSubarray(nums1, nums2):
    n = len(nums1)
    dp1 = dp2 = 1  # Initialize for index 0
    max_len = 1

    # Process from index 1 to n-1
    for i in range(1, n):
        # Temporary values for the new state
        next_dp1 = 1
        next_dp2 = 1
        
        # If taking nums1[i], check valid transitions from both dp1 (from nums1[i-1]) and dp2 (from nums2[i-1])
        if nums1[i] >= nums1[i-1]:
            next_dp1 = max(next_dp1, dp1 + 1)
        if nums1[i] >= nums2[i-1]:
            next_dp1 = max(next_dp1, dp2 + 1)
        
        # Similarly for taking nums2[i]
        if nums2[i] >= nums1[i-1]:
            next_dp2 = max(next_dp2, dp1 + 1)
        if nums2[i] >= nums2[i-1]:
            next_dp2 = max(next_dp2, dp2 + 1)
        
        # Update dp1 and dp2 for next iteration
        dp1, dp2 = next_dp1, next_dp2
        
        # Record maximum segment length seen so far
        max_len = max(max_len, dp1, dp2)
    
    return max_len

# Example test
print(longestNonDecreasingSubarray([2,3,1], [1,2,1]))  # Expected output: 2
← Back to All Questions