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

Examples

Example 1

1
2
3
4
5
6
7


    
    
    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

1
2
3
4
5
6
7
8


    
    
    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

1
2
3
4
5
6
7
8
9


    
    
    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

Solution

Method 1 – Sliding Window (1)

Intuition

We want the longest subarray starting with an even number, alternating even/odd, and all elements ≤ threshold. We can use a sliding window to expand as long as the conditions hold, and reset when broken.

Approach

  1. Initialize two pointers for the window and a variable for the maximum length.
  2. Iterate through the array:
    • If the current number is even, start a new window.
    • Expand the window as long as the parity alternates and all elements are ≤ threshold.
    • Update the maximum length found.
  3. Return the maximum length.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int longestAlternatingSubarray(vector<int>& nums, int threshold) {
        int n = nums.size(), ans = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] % 2 == 0 && nums[i] <= threshold) {
                int j = i, cur = 0, last = nums[i] % 2;
                while (j < n && nums[j] % 2 == last && nums[j] <= threshold) {
                    cur++;
                    last ^= 1;
                    j++;
                }
                ans = max(ans, cur);
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func longestAlternatingSubarray(nums []int, threshold int) int {
    n, ans := len(nums), 0
    for i := 0; i < n; i++ {
        if nums[i]%2 == 0 && nums[i] <= threshold {
            j, cur, last := i, 0, nums[i]%2
            for j < n && nums[j]%2 == last && nums[j] <= threshold {
                cur++
                last ^= 1
                j++
            }
            if cur > ans {
                ans = cur
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int longestAlternatingSubarray(int[] nums, int threshold) {
        int n = nums.length, ans = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] % 2 == 0 && nums[i] <= threshold) {
                int j = i, cur = 0, last = nums[i] % 2;
                while (j < n && nums[j] % 2 == last && nums[j] <= threshold) {
                    cur++;
                    last ^= 1;
                    j++;
                }
                ans = Math.max(ans, cur);
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    fun longestAlternatingSubarray(nums: IntArray, threshold: Int): Int {
        val n = nums.size
        var ans = 0
        for (i in 0 until n) {
            if (nums[i] % 2 == 0 && nums[i] <= threshold) {
                var j = i
                var cur = 0
                var last = nums[i] % 2
                while (j < n && nums[j] % 2 == last && nums[j] <= threshold) {
                    cur++
                    last = last xor 1
                    j++
                }
                ans = maxOf(ans, cur)
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def longestAlternatingSubarray(self, nums: list[int], threshold: int) -> int:
        n = len(nums)
        ans = 0
        i = 0
        while i < n:
            if nums[i] % 2 == 0 and nums[i] <= threshold:
                j = i
                last = nums[i] % 2
                cur = 0
                while j < n and nums[j] % 2 == last and nums[j] <= threshold:
                    cur += 1
                    last ^= 1
                    j += 1
                ans = max(ans, cur)
            i += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn longest_alternating_subarray(nums: Vec<i32>, threshold: i32) -> i32 {
        let n = nums.len();
        let mut ans = 0;
        let mut i = 0;
        while i < n {
            if nums[i] % 2 == 0 && nums[i] <= threshold {
                let mut j = i;
                let mut last = nums[i] % 2;
                let mut cur = 0;
                while j < n && nums[j] % 2 == last && nums[j] <= threshold {
                    cur += 1;
                    last ^= 1;
                    j += 1;
                }
                ans = ans.max(cur);
            }
            i += 1;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    longestAlternatingSubarray(nums: number[], threshold: number): number {
        const n = nums.length;
        let ans = 0;
        for (let i = 0; i < n; i++) {
            if (nums[i] % 2 === 0 && nums[i] <= threshold) {
                let j = i, cur = 0, last = nums[i] % 2;
                while (j < n && nums[j] % 2 === last && nums[j] <= threshold) {
                    cur++;
                    last ^= 1;
                    j++;
                }
                ans = Math.max(ans, cur);
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), where n is the length of nums. For each start, we may scan the rest of the array.
  • 🧺 Space complexity: O(1), only a few variables are used.