What is the time complexity of the Brute Force approach?

The Brute Force approach has a time complexity of O(n²) as we check every possible subarray.

What is the time complexity of the Single Pass approach?

The Single Pass approach has a time complexity of O(n) as we traverse the array only once.

What is the space complexity of both approaches?

Both approaches have a space complexity of O(1) as we only use a constant amount of extra space.

Longest Even Odd Subarray With Threshold

Difficulty: Easy | Acceptance: 32.10% | Paid: No Topics: Array, Sliding Window

You are given a 0-indexed integer array nums and an integer threshold.

Find the length of the longest subarray of nums starting at index l and ending at index r (0 <= l <= r < nums.length) such that for each index i in the range [l, r - 1], nums[i] % 2 != nums[i + 1] % 2 and for each index i in the range [l, r], nums[i] <= threshold.

Return the length of the longest such subarray.

Examples
Constraints
Brute Force
Single Pass

Examples

Example 1

Input: nums = [3,2,5,4], threshold = 4
Output: 3
Explanation: The longest subarray is [2,5,4].

Example 2

Input: nums = [1,2], threshold = 2
Output: 1
Explanation: The longest subarray is [1] or [2].

Example 3

Input: nums = [2,3,4,5], threshold = 4
Output: 3
Explanation: The longest subarray is [2,3,4].

Constraints

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
1 <= threshold <= 10⁹

Brute Force

Intuition Check every possible starting position and extend the subarray as far as possible while maintaining the alternating parity and threshold conditions.

Steps

Iterate through each index as a potential starting point
If the starting element exceeds threshold, skip it
Extend the subarray while elements are within threshold and alternate in parity
Track the maximum length found

python

from typing import List

class Solution:
    def longestAlternatingSubarray(self, nums: List[int], threshold: int) -> int:
        n = len(nums)
        max_len = 0
        
        for i in range(n):
            if nums[i] &gt; threshold:
                continue
            curr_len = 1
            for j in range(i + 1, n):
                if nums[j] &gt; threshold:
                    break
                if (nums[j] % 2) == (nums[j-1] % 2):
                    break
                curr_len += 1
            max_len = max(max_len, curr_len)
        
        return max_len

Complexity

Time: O(n²)
Space: O(1)
Notes: Simple but inefficient for large inputs

Single Pass

Intuition Maintain a running count of the current valid subarray. When conditions are violated, reset or start a new subarray from the current position.

Steps

Track current subarray length and maximum length
If current element exceeds threshold, reset current length to 0
If current element alternates parity with previous, extend current subarray
If parity doesn’t alternate, start new subarray from current element
Update maximum length at each step

python

from typing import List

class Solution:
    def longestAlternatingSubarray(self, nums: List[int], threshold: int) -> int:
        n = len(nums)
        max_len = 0
        curr_len = 0
        
        for i in range(n):
            if nums[i] &gt; threshold:
                curr_len = 0
            elif curr_len == 0 or (nums[i] % 2) != (nums[i-1] % 2):
                curr_len += 1
            else:
                curr_len = 1
            
            max_len = max(max_len, curr_len)
        
        return max_len

Complexity

Time: O(n)
Space: O(1)
Notes: Optimal solution with single pass through the array