Longest Even Odd Subarray With Threshold - Solution & Explanation
Problem Statement
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 == 0- For all indices
iin the range[l, r - 1],nums[i] % 2 != nums[i + 1] % 2 - For all indices
iin the range[l, r],nums[i] <= threshold
Return 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 <= 1001 <= nums[i] <= 1001 <= threshold <= 100
Approach Overview
Problem 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 1: Sliding Window Approach
This approach utilizes a sliding window technique to find the longest subarray that meets the specified conditions. Begin with two pointers (one starting and one ending) and expand the window while all conditions are met. If a condition is violated, adjust the starting pointer to maintain validity.
This C implementation uses a single loop with a two-pointer method to calculate the longest valid subarray by adjusting the starting pointer whenever conditions fail.
Complexity
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1), as we use a constant amount of extra space.
Approach 2: Brute Force Approach
In the brute force approach, iterate over all possible subarrays, checking each one for the validity conditions and keeping track of the maximum valid length.
In this C implementation, nested loops check each potential subarray for validity, recording the maximum length of valid subarrays found.
Complexity
Time Complexity: O(n^2), due to the nested loops.
Space Complexity: O(1)
Approach 3: 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.
The time complexity is O(n^2), where n is the length of the array nums. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Approach 4: 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.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n), where n is the number of elements in the array. |
| Brute Force Approach | Time Complexity: O(n^2), due to the nested loops. |
| Enumeration | ā |
| Optimized Enumeration | ā |
Detailed Complexity Analysis
| 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 |
Video Solution
Longest Even Odd Subarray With Threshold | Leetcode 2760 | Contest 352 ā¢ Tech Courses ā¢ 1,483 views views
Watch 9 more video solutions āFrequently Asked Questions
Is Longest Even Odd Subarray With Threshold easy or hard?
Longest Even Odd Subarray With Threshold Python/Java solution
How to solve Longest Even Odd Subarray With Threshold in O(n)?
What is the best approach for Longest Even Odd Subarray With Threshold?
Is Longest Even Odd Subarray With Threshold asked at Google/Amazon/Meta?
What data structure is used in Longest Even Odd Subarray With Threshold?
What is the time complexity of Longest Even Odd Subarray With Threshold?
Ready to solve this problem?
Practice Longest Even Odd Subarray With Threshold with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor