Longest Even Odd Subarray With Threshold

In this blog, the Longest Even Odd Subarray With Threshold (LeetCode Problem Link) will be solved using the Sliding Window, Explained in detail using a Simple Java Solution & O(N) approach.

Problem 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

Sliding Window Explained | Simple Java Solution | O(N)

Intuition

Use the Sliding Window Technique to find the longest subarray that also satisfies the given conditions.

Approach

• Start at each possible left index and go right as far as you can.
• For each iteration, check whether the conditions are satisfied:
  • If the conditions are not satisfied, store the maximum of the previous and current possible subarray length in the answer.
  • If the conditions are satisfied, increase the length of subarray
• Return the maximum possible subarray length that satisfies the given conditions.

Complexity

• Time complexity: O(N)
• Space complexity: O(1)

Code

class Solution {
    public int longestAlternatingSubarray(int[] nums, int threshold) {
        int answer = 0, i = 1, r = Integer.MAX_VALUE;
        if(nums[0] <= threshold && nums[0] % 2 == 0) {
            r = 0;
        }
        while(i < nums.length){
            if( nums[i] > threshold || ((nums[i] % 2) == (nums[i-1] % 2)) ){
                // Conditions not satisfied
                answer = Math.max(answer, i - r );
                r = Integer.MAX_VALUE;
            }
            if(r == Integer.MAX_VALUE && nums[i] <= threshold && nums[i] % 2 == 0){
                // Conditions satisfied - increase the length of subarray
                r = i;
            }
            i++;
        }
        answer = Math.max(answer, i - r );
        return answer;
    }
}

Resources

• Longest Even Odd Subarray With Threshold: LeetCode Problem Link
• Also check out my LeetCode Solution: Sliding Window Explained | Simple Java Solution | O(N)

Who Am I?

• I’m Aswin Barath, a Software Engineering Nerd who loves building Web Applications and sharing my knowledge through Blogging 
• Connect with me Socials (Linktree)