#2760

Easy

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Longest Even Odd Subarray With Threshold

Determine the length of the longest subarray where elements alternate even and odd while staying below a given threshold.

array sliding window

Problem Statement

Given a 0-indexed array of integers and an integer threshold, identify subarrays where every number is less than or equal to the threshold and elements strictly alternate between even and odd values.

Return the length of the longest subarray satisfying these conditions. Each subarray must start and end within the original array bounds, and the array length is at least one.

Examples

Example 1

Input: nums = [3,2,5,4], threshold = 5

Output: 3

In this example, we can select the subarray that starts at l = 1 and ends at r = 3 => [2,5,4]. This subarray satisfies the conditions. Hence, the answer is the length of the subarray, 3. We can show that 3 is the maximum possible achievable length.

Example 2

Input: nums = [1,2], threshold = 2

Output: 1

In this example, we can select the subarray that starts at l = 1 and ends at r = 1 => [2]. It satisfies all the conditions and we can show that 1 is the maximum possible achievable length.

Example 3

Input: nums = [2,3,4,5], threshold = 4

Output: 3

In this example, we can select the subarray that starts at l = 0 and ends at r = 2 => [2,3,4]. It satisfies all the conditions. Hence, the answer is the length of the subarray, 3. We can show that 3 is the maximum possible achievable length.

Constraints

1 <= nums.length <= 100
1 <= nums[i] <= 100
1 <= threshold <= 100

Solution Approach

Sliding Window Tracking

Initialize two pointers representing the start and end of the current subarray. Move the end pointer while maintaining the alternating even-odd pattern and threshold constraint. If a violation occurs, shift the start pointer forward to restore validity.

Validate Elements Efficiently

Check each element against the threshold and ensure it alternates in parity compared to the previous element. Reset the current subarray length when a violation occurs to avoid counting invalid sequences.

Update Maximum Length

Keep a running maximum of the subarray lengths that satisfy the conditions. After scanning the array, the stored maximum represents the length of the longest valid even-odd subarray under the threshold.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each element is visited at most twice by the sliding window. Space complexity is O(1) as no additional arrays or structures are required beyond pointers and counters.

What Interviewers Usually Probe

They may hint at optimizing brute force by using a sliding window.
Watch for questions about handling consecutive numbers with the same parity.
Expect discussion on early stopping when elements exceed the threshold.

Common Pitfalls or Variants

Common pitfalls

Forgetting to check the threshold for every element.
Not correctly resetting the window when parity alternation fails.
Counting subarrays that partially violate the alternating pattern.

Follow-up variants

Longest odd-even subarray ignoring threshold constraints.
Maximum length subarray with alternating parity and a minimum value requirement.
Subarray with alternating even-odd elements and sum below a given target.

FAQ

What is the main idea behind Longest Even Odd Subarray With Threshold?

It focuses on using a sliding window to efficiently find subarrays that alternate even-odd and stay below the threshold.

Do I need to check every subarray individually?

No, a sliding window allows updating the subarray length dynamically without brute-forcing all combinations.

How do I handle consecutive numbers with the same parity?

Reset the current subarray window when two consecutive elements share the same parity to maintain the alternating pattern.

Is the threshold condition applied to every element?

Yes, any element exceeding the threshold breaks the subarray and requires the window to be reset.

Can this approach work for larger arrays efficiently?

Yes, the sliding window ensures O(n) time complexity, making it scalable within the problem constraints.

terminal

Solution

Solution 1: Enumeration

We enumerate all $l$ in the range $[0,..n-1]$. If $nums[l]$ satisfies $nums[l] \bmod 2 = 0$ and $nums[l] \leq threshold$, then we start from $l+1$ to find the largest $r$ that meets the condition. At this time, the length of the longest odd-even subarray with $nums[l]$ as the left endpoint is $r - l$. We take the maximum of all $r - l$ as the answer.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def longestAlternatingSubarray(self, nums: List[int], threshold: int) -> int:
        ans, n = 0, len(nums)
        for l in range(n):
            if nums[l] % 2 == 0 and nums[l] <= threshold:
                r = l + 1
                while r < n and nums[r] % 2 != nums[r - 1] % 2 and nums[r] <= threshold:
                    r += 1
                ans = max(ans, r - l)
        return ans

Solution 2: Optimized Enumeration

We notice that the problem actually divides the array into several disjoint subarrays that meet the condition. We only need to find the longest one among these subarrays. Therefore, when enumerating $l$ and $r$, we don't need to backtrack, we just need to traverse from left to right once.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def longestAlternatingSubarray(self, nums: List[int], threshold: int) -> int:
        ans, n = 0, len(nums)
        for l in range(n):
            if nums[l] % 2 == 0 and nums[l] <= threshold:
                r = l + 1
                while r < n and nums[r] % 2 != nums[r - 1] % 2 and nums[r] <= threshold:
                    r += 1
                ans = max(ans, r - l)
        return ans

Continue Practicing

#2762 continuous subarrays #2747 count zero request servers #2779 maximum beauty of an array after applying operation