LeetCode 2760. Longest Even Odd Subarray With Threshold Solution in Java, C++, Python & More | Explanation + Code

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] ≤ 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²), where n is the length of the array nums. The space complexity is O(1).

PythonJavaC++GoTypeScript

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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

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; }(code-box)

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).

PythonJavaC++GoTypeScript

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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

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; }(code-box)