Watch 10 video solutions for Longest Even Odd Subarray With Threshold, a easy level problem involving Array, Sliding Window. This walkthrough by Tech Courses has 1,430 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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) that satisfies the following conditions:
nums[l] % 2 == 0i in the range [l, r - 1], nums[i] % 2 != nums[i + 1] % 2i in the range [l, r], nums[i] <= thresholdReturn an integer denoting the length of the longest such subarray.
Note: A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [3,2,5,4], threshold = 5 Output: 3 Explanation: 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 Explanation: 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 Explanation: 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 <= 100Problem Overview: You are given an integer array nums and a value threshold. The task is to find the length of the longest contiguous subarray that starts with an even number, alternates between even and odd values, and where every element is less than or equal to the threshold.
Approach 1: Brute Force (O(n²) time, O(1) space)
The straightforward strategy checks every possible starting index and expands the subarray while the conditions remain valid. For each index i, first verify that nums[i] is even and nums[i] ≤ threshold. Then iterate forward from j = i + 1, ensuring two rules hold: the current element is within the threshold and its parity alternates compared to the previous element. Stop expanding once any rule breaks and record the length of the valid segment. This method directly simulates the problem definition but may scan the same elements repeatedly, leading to O(n²) time in the worst case. Space usage stays constant since only counters and indices are tracked.
Approach 2: Sliding Window (O(n) time, O(1) space)
A more efficient method uses a sliding window over the array. Traverse the array once while maintaining the current alternating segment length. Whenever you encounter a number greater than the threshold, the window becomes invalid and resets. If a number is valid and even, it can start a new window. From there, extend the window only if the parity alternates with the previous element. If the alternation breaks but the current number is even and within threshold, start a new window from that index; otherwise reset the window length to zero. This technique avoids re-checking earlier elements and ensures each element is processed once. The result is an optimal O(n) traversal using constant space.
The solution relies mainly on simple array iteration and parity checks, making it a good exercise in recognizing patterns that fit a array scan with window-style constraints. Alternating parity behaves like a dynamic window condition, which is why the sliding window model works naturally here.
Recommended for interviews: The sliding window solution is what interviewers typically expect because it demonstrates the ability to convert repeated subarray checks into a single linear pass. Showing the brute force approach first proves you understand the constraints, but optimizing it with a sliding window highlights strong problem-solving and algorithmic thinking.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Good for understanding the problem or when input size is very small |
| Sliding Window | O(n) | O(1) | Best choice for interviews and production code due to linear scan |