Question

2760. Longest Even Odd Subarray With Threshold

中文文档

Description

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

Solutions

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.

The time complexity is $O(n^2)$, where $n$ is the length of the array $nums$. The space complexity is $O(1)$.

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

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;
  }
}

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;
  }
};

func longestAlternatingSubarray(nums []int, threshold int) (ans int) {
  n := len(nums)
  for l := range nums {
    if nums[l]%2 == 0 && nums[l] <= threshold {
      r := l + 1
      for r < n && nums[r]%2 != nums[r-1]%2 && nums[r] <= threshold {
        r++
      }
      ans = max(ans, r-l)
    }
  }
  return
}

function longestAlternatingSubarray(nums: number[], threshold: number): number {
  const n = nums.length;
  let ans = 0;
  for (let l = 0; l < n; ++l) {
    if (nums[l] % 2 === 0 && nums[l] <= threshold) {
      let 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;
}

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.

The time complexity is $O(n)$, where $n$ is the length of the array $nums$. The space complexity is $O(1)$.

class Solution:
  def longestAlternatingSubarray(self, nums: List[int], threshold: int) -> int:
    ans, l, n = 0, 0, len(nums)
    while l < 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)
        l = r
      else:
        l += 1
    return ans

class Solution {
  public int longestAlternatingSubarray(int[] nums, int threshold) {
    int ans = 0;
    for (int l = 0, n = nums.length; l < n;) {
      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);
        l = r;
      } else {
        ++l;
      }
    }
    return ans;
  }
}

class Solution {
public:
  int longestAlternatingSubarray(vector<int>& nums, int threshold) {
    int ans = 0;
    for (int l = 0, n = nums.size(); l < n;) {
      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);
        l = r;
      } else {
        ++l;
      }
    }
    return ans;
  }
};

func longestAlternatingSubarray(nums []int, threshold int) (ans int) {
  for l, n := 0, len(nums); l < n; {
    if nums[l]%2 == 0 && nums[l] <= threshold {
      r := l + 1
      for r < n && nums[r]%2 != nums[r-1]%2 && nums[r] <= threshold {
        r++
      }
      ans = max(ans, r-l)
      l = r
    } else {
      l++
    }
  }
  return
}

function longestAlternatingSubarray(nums: number[], threshold: number): number {
  const n = nums.length;
  let ans = 0;
  for (let l = 0; l < n; ) {
    if (nums[l] % 2 === 0 && nums[l] <= threshold) {
      let r = l + 1;
      while (r < n && nums[r] % 2 !== nums[r - 1] % 2 && nums[r] <= threshold) {
        ++r;
      }
      ans = Math.max(ans, r - l);
      l = r;
    } else {
      ++l;
    }
  }
  return ans;
}