LeetCode 2760 - Longest Even Odd Subarray With Threshold

The problem asks us to find the length of the longest contiguous subarray in a given integer array nums that satisfies three specific conditions. First, the subarray must start with an even number.

leetcodeeasyarraysliding-window

LeetCode Problem 2760

Difficulty: 🟢 Easy
Topics: Array, Sliding Window

Solution

Problem Understanding

The problem asks us to find the length of the longest contiguous subarray in a given integer array nums that satisfies three specific conditions. First, the subarray must start with an even number. Second, the subarray must alternate between even and odd numbers throughout its length. Third, every number in the subarray must be less than or equal to the given threshold.

The input is a list of integers nums where each element is between 1 and 100, and an integer threshold between 1 and 100. The expected output is a single integer representing the maximum length of any subarray that satisfies all three conditions.

Key points and constraints include:

  • The array is guaranteed to be non-empty and has a maximum length of 100, which is small. This means that even less optimized solutions may be feasible, though an efficient solution is preferred.
  • The numbers in the array are bounded (1 to 100), and the threshold is also bounded (1 to 100), simplifying comparisons.
  • A subarray must be contiguous, so you cannot skip elements.
  • Edge cases to consider include arrays with all elements above the threshold, arrays with no even numbers, arrays that are already alternating, or arrays of length 1.

Understanding these points ensures that we focus on subarrays starting with even numbers and alternating properly without exceeding the threshold.

Approaches

The brute-force approach involves checking every possible subarray in nums and verifying if it satisfies the three conditions. For each subarray starting at index i, we check if nums[i] is even and then iterate through subsequent elements, checking alternation and threshold. If the conditions hold, we calculate the length and update the maximum length seen so far. This works because it examines all possibilities but is inefficient because it involves nested iteration over the array, giving a worst-case time complexity of O(n²), where n is the length of the array.

The optimal approach leverages a sliding window / linear scan strategy. Instead of checking every possible subarray, we iterate through the array once, maintaining the length of the current valid alternating subarray. When we encounter an element that breaks any of the three conditions, we reset the current subarray length. This approach works because the subarray must be contiguous and always starts with an even number, so a linear scan can efficiently track valid subarrays.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Checks all subarrays starting at each index
Optimal O(n) O(1) Linear scan using current length tracking, resets when conditions break

Algorithm Walkthrough

  1. Initialize two variables: max_len to store the maximum subarray length seen, and current_len to track the current alternating subarray length.
  2. Iterate through the array using an index i.
  3. If nums[i] is greater than the threshold or nums[i] is odd at the start of a subarray, reset current_len to 0, as this cannot be a valid starting point.
  4. If current_len is 0 and nums[i] is even and ≤ threshold, set current_len to 1 to start a new subarray.
  5. For subsequent elements, check if they alternate in parity with the previous element and are ≤ threshold. If so, increment current_len.
  6. If the alternation or threshold condition fails, reset current_len to 0 if the current element is odd, or to 1 if the element is even and ≤ threshold (starting a new subarray).
  7. After each step, update max_len if current_len exceeds it.
  8. After iterating through all elements, return max_len.

Why it works:

This algorithm works because it maintains an invariant that current_len always represents the length of the longest valid alternating subarray ending at the current index. Resetting correctly ensures no invalid subarray is counted, while valid ones are extended and counted efficiently.

Python Solution

from typing import List

class Solution:
    def longestAlternatingSubarray(self, nums: List[int], threshold: int) -> int:
        max_len = 0
        current_len = 0

        for i, num in enumerate(nums):
            if num > threshold or (current_len == 0 and num % 2 != 0):
                current_len = 0
            else:
                if current_len == 0:
                    current_len = 1
                else:
                    if (nums[i] % 2) != (nums[i - 1] % 2):
                        current_len += 1
                    else:
                        current_len = 1  # reset if alternation breaks but starts with even
            max_len = max(max_len, current_len)

        return max_len

Explanation:

We initialize max_len and current_len. For each number, we check threshold and starting parity conditions. If starting a new valid subarray, we set current_len to 1. If alternation holds, we increment current_len. Otherwise, we reset. max_len is updated at each step to track the longest valid subarray.

Go Solution

func longestAlternatingSubarray(nums []int, threshold int) int {
    maxLen := 0
    currentLen := 0

    for i, num := range nums {
        if num > threshold || (currentLen == 0 && num%2 != 0) {
            currentLen = 0
        } else {
            if currentLen == 0 {
                currentLen = 1
            } else {
                if nums[i]%2 != nums[i-1]%2 {
                    currentLen++
                } else {
                    currentLen = 1
                }
            }
        }
        if currentLen > maxLen {
            maxLen = currentLen
        }
    }

    return maxLen
}

Go-specific notes:

Go does not have a native max function for integers, so we use a simple if to update maxLen. The slice index and iteration are similar to Python, and there is no concern for integer overflow due to problem constraints.

Worked Examples

Example 1: nums = [3,2,5,4], threshold = 5

i num current_len max_len Explanation
0 3 0 0 3 is odd, cannot start subarray
1 2 1 1 Start new subarray at even 2
2 5 2 2 Alternates (even → odd) and ≤ threshold
3 4 3 3 Alternates (odd → even) and ≤ threshold

Answer = 3

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

i num current_len max_len Explanation
0 1 0 0 1 is odd, cannot start subarray
1 2 1 1 Start new subarray at even 2

Answer = 1

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

i num current_len max_len Explanation
0 2 1 1 Start subarray
1 3 2 2 Alternates (even → odd)
2 4 3 3 Alternates (odd → even)
3 5 reset 3 5 > threshold 4 → break

Answer = 3

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through the array, constant work per element
Space O(1) Only two integer variables are used

The reasoning is straightforward: the array is traversed once, no additional data structures scale with input size.

Test Cases

# Provided examples
assert Solution().longestAlternatingSubarray([3,2,5,4], 5) == 3  # alternating subarray [2,5,4]
assert Solution().longestAlternatingSubarray([1,2], 2) == 1      # only [2] is valid
assert Solution().longestAlternatingSubarray([2,3,4,5], 4) == 3  # alternating subarray [2,3,4]

# Boundary and edge cases
assert Solution().longestAlternatingSubarray([2,4,6,8], 10) == 1  # all even, length 1 each
assert Solution().longestAlternatingSubarray([1,3,5,7], 10) == 0  # no starting even
assert Solution().longestAlternatingSubarray([2], 2) == 1         # single element, valid
assert Solution().longestAlternatingSubarray([2,3,2,3,2], 3) == 2 # threshold cuts last 2
assert Solution().longestAlternatingSubarray([2,3,4,5,6