# Longest Even Odd Subarray With Threshold
**Difficulty:** EASY
[External](https://leetcode.com/problems/longest-even-odd-subarray-with-threshold)
Canonical: https://scaleengineer.com/dsa/problems/longest-even-odd-subarray-with-threshold
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Array
---
## Problem
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 `i` in the range `[l, r - 1]`, `nums[i] % 2 != nums[i + 1] % 2`
* For all indices `i` in 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 <= 100 `
* `1 <= nums[i] <= 100 `
* `1 <= threshold <= 100`

# Approaches
## Brute Force: Check All Subarrays
This approach involves generating every possible subarray of the input array `nums` and then checking if each subarray satisfies all the given conditions. The length of the longest valid subarray found is tracked and returned.
**Time:** O(n^3), where n is the length of `nums`. We have two nested loops to define the start (l) and end (r) of a subarray, which is O(n^2). For each subarray, we iterate through it again to check the conditions, which takes O(n) time in the worst case. This results in a total time complexity of O(n^3). · **Space:** O(1), as we only use a few variables to store indices and the maximum length. No extra space proportional to the input size is required.
**Pros:** Simple to understand and implement.; Correctly solves the problem by exhaustively checking all possibilities.
**Cons:** Highly inefficient due to its cubic time complexity.; Likely to result in a 'Time Limit Exceeded' (TLE) error on larger inputs, although it might pass given the small constraints of this problem.
### Explanation
The core idea is to check every single contiguous subarray. We use a pair of nested loops, with `l` representing the starting index and `r` representing the ending index. This defines a subarray `nums[l...r]`. For each of these subarrays, we perform a third loop to validate it against the three given conditions:
1. The first element `nums[l]` must be even.
2. All elements in `nums[l...r]` must be less than or equal to `threshold`.
3. Adjacent elements in `nums[l...r]` must have alternating parity.
If a subarray is valid, we update our `maxLength` with its length (`r - l + 1`). This process is repeated until all subarrays have been checked.

```java
class Solution {
    public int longestAlternatingSubarray(int[] nums, int threshold) {
        int n = nums.length;
        int maxLength = 0;
        for (int l = 0; l < n; l++) {
            for (int r = l; r < n; r++) {
                // Check the subarray nums[l...r]
                boolean isValid = true;
                // Condition 1: nums[l] must be even
                if (nums[l] % 2 != 0) {
                    isValid = false;
                } else {
                    // Check conditions 2 and 3 for the whole subarray
                    for (int i = l; i <= r; i++) {
                        // Condition 3: All elements <= threshold
                        if (nums[i] > threshold) {
                            isValid = false;
                            break;
                        }
                        // Condition 2: Alternating parity
                        if (i > l && (nums[i] % 2 == nums[i - 1] % 2)) {
                            isValid = false;
                            break;
                        }
                    }
                }
                
                if (isValid) {
                    maxLength = Math.max(maxLength, r - l + 1);
                }
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength` to 0.
- Use a nested loop to generate all possible start `l` and end `r` indices for subarrays.
- For each subarray from `l` to `r`:
  - Create a flag `isValid`, initially `true`.
  - Check the first condition: `nums[l]` must be even. If not, the subarray is invalid.
  - If the first condition holds, iterate from `l` to `r` to check the other two conditions:
    - All elements `nums[i]` must be `<= threshold`.
    - Adjacent elements `nums[i]` and `nums[i-1]` must have different parity.
  - If any condition is violated, set `isValid` to `false` and break the inner check.
- If the subarray is `isValid` after all checks, update `maxLength = max(maxLength, r - l + 1)`.
- After checking all subarrays, return `maxLength`.

## Improved Brute Force: Iterate Start Points
This method improves upon the brute-force approach by iterating through each possible starting index `l`. For each potential start, it attempts to extend a subarray to the right, checking conditions one element at a time. This avoids the redundant checks of the O(n^3) approach.
**Time:** O(n^2), where n is the length of `nums`. The outer loop iterates through all possible starting positions (n possibilities), and the inner loop extends the subarray, also taking up to O(n) time. This leads to a quadratic time complexity. · **Space:** O(1), as we only use constant extra space for variables.
**Pros:** More efficient than the pure brute-force approach.; Still relatively easy to reason about and implement.
**Cons:** Not the most optimal solution.; Can be slow for larger arrays, though it's acceptable for the given constraints.
### Explanation
Instead of re-validating the entire subarray from scratch every time, we can be smarter. We iterate through each possible starting index `l`. If `nums[l]` is a valid starting element (it's even and not over the threshold), we then try to extend this subarray to the right. We use a second loop with index `r` starting from `l+1`. We keep extending the subarray as long as `nums[r]` satisfies the threshold and alternating parity conditions. Once a condition is violated, we know that no longer subarray can be formed starting from `l`, so we break the inner loop and move to the next potential starting index `l+1`.

```java
class Solution {
    public int longestAlternatingSubarray(int[] nums, int threshold) {
        int n = nums.length;
        int maxLength = 0;
        for (int l = 0; l < n; l++) {
            // Check if nums[l] is a valid starting point
            if (nums[l] % 2 == 0 && nums[l] <= threshold) {
                // We have a valid subarray of length 1
                maxLength = Math.max(maxLength, 1);
                // Try to extend it
                for (int r = l + 1; r < n; r++) {
                    // Check if nums[r] can extend the subarray
                    if (nums[r] <= threshold && nums[r] % 2 != nums[r - 1] % 2) {
                        maxLength = Math.max(maxLength, r - l + 1);
                    } else {
                        // Condition violated, break and try next starting point
                        break;
                    }
                }
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength` to 0.
- Iterate through the array with an index `l` from `0` to `n-1` to select a potential starting point.
- For each `l`, check if `nums[l]` is a valid start: `nums[l] % 2 == 0` and `nums[l] <= threshold`.
- If it is a valid start, we have a valid subarray of length 1. Update `maxLength = max(maxLength, 1)`.
- Then, start a nested loop with index `r` from `l + 1` to `n-1` to try and extend the subarray.
- In the inner loop, check if `nums[r]` can extend the current subarray (i.e., `nums[r] <= threshold` and `nums[r] % 2 != nums[r-1] % 2`).
- If it can, update `maxLength = max(maxLength, r - l + 1)`.
- If it cannot, break the inner loop since the subarray cannot be extended further.
- After the loops complete, return `maxLength`.

## Single Pass (Sliding Window)
The most efficient approach uses a single pass through the array. It identifies potential starting points for a valid subarray and then extends the subarray as far as possible. By intelligently advancing the main loop's index, it ensures that each element is visited only a constant number of times, achieving linear time complexity.
**Time:** O(n), where n is the length of `nums`. Although there appears to be a nested loop, the outer loop's index `i` is always advanced to the end of the subarray just found. This ensures that each element is processed at most twice, resulting in a linear time complexity. · **Space:** O(1), as only a few variables are needed to keep track of the current state, regardless of the input size.
**Pros:** Optimal time complexity.; Highly efficient and will pass even with much larger constraints.
**Cons:** The logic for advancing the loop index can be slightly more complex to implement correctly compared to the brute-force methods.
### Explanation
This optimal solution avoids redundant checks by processing the array in a single pass. We use a pointer `i` to iterate through the array. When we find an element `nums[i]` that can start a valid subarray (even and within the threshold), we then use a second pointer `j` (implicitly the same `i` in this implementation) to find the end of this specific subarray. The pointer `i` moves forward as long as the elements satisfy the alternating parity and threshold conditions. Once the subarray ends (either by violating a condition or reaching the end of the array), we record its length. The key optimization is that after processing the subarray from a `start` index to `i-1`, we resume our search for the *next* potential subarray starting from index `i`. This prevents the O(n^2) behavior because each element is examined only a constant number of times.

```java
class Solution {
    public int longestAlternatingSubarray(int[] nums, int threshold) {
        int n = nums.length;
        int maxLength = 0;
        int i = 0;
        while (i < n) {
            // Find a valid starting point
            if (nums[i] % 2 == 0 && nums[i] <= threshold) {
                // Found a start at index i
                int start = i;
                i++; // Move to the next element to check for extension
                // Extend the subarray
                while (i < n && nums[i] <= threshold && nums[i] % 2 != nums[i - 1] % 2) {
                    i++;
                }
                // Subarray is from start to i-1
                maxLength = Math.max(maxLength, i - start);
            } else {
                // Not a valid start, move to the next element
                i++;
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength = 0` and an index `i = 0`.
- Use a `while` loop to iterate as long as `i < n`.
- Inside the loop, check if `nums[i]` is a valid starting point (`nums[i] % 2 == 0` and `nums[i] <= threshold`).
- If it's not a valid start, simply increment `i` and continue.
- If it is a valid start, record this position as `start = i`.
- Start a nested `while` loop to extend the subarray. This inner loop continues as long as the next element `nums[i]` is valid (`nums[i] <= threshold` and `nums[i] % 2 != nums[i-1] % 2`). Increment `i` in this inner loop.
- Once the inner loop terminates, a valid subarray from `start` to `i-1` has been found. Calculate its length `i - start`.
- Update `maxLength = max(maxLength, i - start)`.
- The outer loop automatically continues from the new position of `i`, effectively skipping over the elements that were just checked.
- Return `maxLength` after the main loop finishes.

# Solutions
### Java

```java
class Solution {
public
  int longestAlternatingSubarray(int[] nums, int threshold) {
    int ans = 0, n = nums.length;
    for (int l = 0; l < n; ++l) {
      if (nums[l] % 2 == 0 && nums[l] <= threshold) {
        int r = l + 1;
        while (r < n && nums[r] % 2 != nums[r - 1] % 2 &&
               nums[r] <= threshold) {
          ++r;
        }
        ans = Math.max(ans, r - l);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int longestAlternatingSubarray(vector<int> &nums, int threshold) {
    int ans = 0, n = nums.size();
    for (int l = 0; l < n; ++l) {
      if (nums[l] % 2 == 0 && nums[l] <= threshold) {
        int r = l + 1;
        while (r < n && nums[r] % 2 != nums[r - 1] % 2 &&
               nums[r] <= threshold) {
          ++r;
        }
        ans = max(ans, r - l);
      }
    }
    return ans;
  }
};

```

### Python

```python
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
```