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 Even Odd Subarray With Threshold

Number: 2866

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an array of integers "nums" and an integer "threshold", the task is to find the length of the longest contiguous subarray such that the first element (nums[l]) is even, all elements in the subarray are ≤ threshold, and the parity (even or odd) alternates between consecutive elements.

Key Insights

  • The subarray must start with an even number.
  • Every number in the subarray must be ≤ threshold.
  • The parity of adjacent numbers must alternate (even followed by odd, or odd followed by even).
  • Given the constraint that nums.length is at most 100, an O(n^2) solution is acceptable.

Space and Time Complexity

Time Complexity: O(n^2) – for each starting index, we attempt to build the longest valid subarray. Space Complexity: O(1) – constant extra space is used.

Solution

We approach the problem by iterating over each index in the array to consider it as a starting point for a valid subarray. The starting number must be even and not exceed the threshold. Then, we expand the subarray from that index and check the following for each subsequent number:

  • The current number must be ≤ threshold.
  • The parity of the current number must be different from that of the previous number in the subarray. If either condition is violated, we stop expanding from that starting index. We update the maximum length found among all valid subarrays.

Data structures and techniques used:

  • Simple iteration (nested loops) since the input size is small.
  • Condition checks for threshold and parity using modulus operator (%).

Code Solutions

# Python solution

def longestEvenOddSubarray(nums, threshold):
    # Initialize max_length as 0
    max_length = 0
    n = len(nums)
    # Iterate over each index to consider it as a starting point
    for i in range(n):
        # The starting element must be even and not exceed the threshold.
        if nums[i] % 2 != 0 or nums[i] > threshold:
            continue
        # Starting a potential subarray; initialize current length to 1.
        length = 1
        # Expand the subarray from index i to the right.
        for j in range(i, n - 1):
            # Check if next element exceeds threshold.
            if nums[j+1] > threshold:
                break
            # Check that the parity alternates.
            if nums[j] % 2 == nums[j+1] % 2:
                break
            # Extend the subarray if valid.
            length += 1
        # Update maximum length if this subarray is longer.
        max_length = max(max_length, length)
    return max_length

# Example usage:
print(longestEvenOddSubarray([3,2,5,4], 5))  # Expected output: 3
← Back to All Questions