Longest Even Odd Subarray With Threshold - Practice Coding Problems

Longest Even Odd Subarray With Threshold - 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 (first element must be even)
For all indices i in the range [l, r - 1], nums[i] % 2 != nums[i + 1] % 2 (alternating even/odd)
For all indices i in the range [l, r], nums[i] <= threshold (all elements within 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.

Input & Output

Example 1 — Basic Alternating Pattern

$ Input: nums = [3,2,5,4], threshold = 5

› Output: 3

💡 Note: Starting at index 1: [2,5,4] has length 3. Element 2 is even, alternates (2→5→4 = even→odd→even), and all ≤ 5.

Example 2 — Threshold Violation

$ Input: nums = [1,2], threshold = 2

› Output: 1

💡 Note: Starting at index 1: [2] has length 1. Element 2 is even and ≤ 2. Cannot extend to element 1 since we need even start.

Example 3 — No Valid Subarray

$ Input: nums = [2,3,4,5], threshold = 4

› Output: 3

💡 Note: Starting at index 0: [2,3,4] has length 3. Stops at element 5 because 5 > 4 (threshold violation).

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁶
1 ≤ threshold ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Array with threshold constraint and pattern requirements

Pattern Matching

Find subarrays: even start + alternating + threshold

Maximum Length

Return length of longest valid subarray

Key Takeaway

🎯 Key Insight: Use sliding window to efficiently track valid subarrays with three conditions: even start, alternating parity, and threshold constraint

Asked in

a Amazon 15 M Microsoft 12 G Google 8

The key insight is to use a sliding window approach that tracks valid subarrays starting with even numbers, maintaining alternating even/odd pattern, and staying within threshold. The optimal sliding window approach processes the array in a single pass with O(n) time complexity. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window - Single Pass	O(n)	O(1)	Use a single pass with window expansion and reset when conditions break
Brute Force - Check All Subarrays	O(n²)	O(1)	Try every possible starting position and extend while conditions hold

Sliding Window - Single Pass — Algorithm Steps

Step 1: Iterate through array with single pointer
Step 2: When encountering even element ≤ threshold, start new window
Step 3: Extend window while alternating pattern and threshold hold, reset otherwise

Visualization

Tap to expand

Step-by-Step Walkthrough

Expand Window

Extend window when conditions are satisfied

Reset Window

Reset when any condition breaks

Track Maximum

Keep track of longest window seen

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int solution(int* nums, int numsSize, int threshold) {
    int maxLength = 0;
    int currentLength = 0;
    
    for (int i = 0; i < numsSize; i++) {
        // Check if current element exceeds threshold
        if (nums[i] > threshold) {
            currentLength = 0;
            continue;
        }
        
        // Check if we can start/continue a valid subarray
        if (currentLength == 0) {
            // Starting new subarray - must be even
            if (nums[i] % 2 == 0) {
                currentLength = 1;
            }
        } else {
            // Continuing subarray - must alternate parity
            if (nums[i] % 2 != nums[i-1] % 2) {
                currentLength++;
            } else {
                // Reset and check if current can start new subarray
                currentLength = (nums[i] % 2 == 0) ? 1 : 0;
            }
        }
        
        maxLength = max(maxLength, currentLength);
    }
    
    return maxLength;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int threshold;
    scanf("%d", &threshold);
    
    int result = solution(nums, numsSize, threshold);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the array, each element visited exactly once

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables for window tracking

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window - Single Pass — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler