Scale Engineer

Longest Even Odd Subarray With Threshold

Easy
#2477Time: O(n^3), where n is the length of `nums`. We have two nested loops to define the start (l) and end (r) of a subarray, which is O(n^2). For each subarray, we iterate through it again to check the conditions, which takes O(n) time in the worst case. This results in a total time complexity of O(n^3).Space: O(1), as we only use a few variables to store indices and the maximum length. No extra space proportional to the input size is required.
Patterns
Sliding Window
Data structures
Array

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves generating every possible subarray of the input array nums and then checking if each subarray satisfies all the given conditions. The length of the longest valid subarray found is tracked and returned.

Algorithm

  • Initialize maxLength to 0.
  • Use a nested loop to generate all possible start l and end r indices for subarrays.
  • For each subarray from l to r:
    • Create a flag isValid, initially true.
    • Check the first condition: nums[l] must be even. If not, the subarray is invalid.
    • If the first condition holds, iterate from l to r to check the other two conditions:
      • All elements nums[i] must be <= threshold.
      • Adjacent elements nums[i] and nums[i-1] must have different parity.
    • If any condition is violated, set isValid to false and break the inner check.
  • If the subarray is isValid after all checks, update maxLength = max(maxLength, r - l + 1).
  • After checking all subarrays, return maxLength.

Walkthrough

The core idea is to check every single contiguous subarray. We use a pair of nested loops, with l representing the starting index and r representing the ending index. This defines a subarray nums[l...r]. For each of these subarrays, we perform a third loop to validate it against the three given conditions:

  1. The first element nums[l] must be even.
  2. All elements in nums[l...r] must be less than or equal to threshold.
  3. Adjacent elements in nums[l...r] must have alternating parity. If a subarray is valid, we update our maxLength with its length (r - l + 1). This process is repeated until all subarrays have been checked.
class Solution {    public int longestAlternatingSubarray(int[] nums, int threshold) {        int n = nums.length;        int maxLength = 0;        for (int l = 0; l < n; l++) {            for (int r = l; r < n; r++) {                // Check the subarray nums[l...r]                boolean isValid = true;                // Condition 1: nums[l] must be even                if (nums[l] % 2 != 0) {                    isValid = false;                } else {                    // Check conditions 2 and 3 for the whole subarray                    for (int i = l; i <= r; i++) {                        // Condition 3: All elements <= threshold                        if (nums[i] > threshold) {                            isValid = false;                            break;                        }                        // Condition 2: Alternating parity                        if (i > l && (nums[i] % 2 == nums[i - 1] % 2)) {                            isValid = false;                            break;                        }                    }                }                                if (isValid) {                    maxLength = Math.max(maxLength, r - l + 1);                }            }        }        return maxLength;    }}

Complexity

Time

O(n^3), where n is the length of `nums`. We have two nested loops to define the start (l) and end (r) of a subarray, which is O(n^2). For each subarray, we iterate through it again to check the conditions, which takes O(n) time in the worst case. This results in a total time complexity of O(n^3).

Space

O(1), as we only use a few variables to store indices and the maximum length. No extra space proportional to the input size is required.

Trade-offs

Pros

  • Simple to understand and implement.

  • Correctly solves the problem by exhaustively checking all possibilities.

Cons

  • Highly inefficient due to its cubic time complexity.

  • Likely to result in a 'Time Limit Exceeded' (TLE) error on larger inputs, although it might pass given the small constraints of this problem.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem