Longest Even Odd Subarray With Threshold

Here is a Ruby function to solve this problem. The function finds the length of the longest subarray that satisfies all the given conditions.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def longest_subarray(nums, threshold)
    max_length = 0
    nums.each_index do |i|
        next if nums[i] % 2 != 0
        j = i
        while j < nums.length && nums[j] <= threshold
            break if j != i && nums[j] % 2 == nums[j-1] % 2
            j += 1
        end
        max_length = [max_length, j-i].max
    end
    max_length
end

Here is how this works:

  • For each index i, check if the number at this index is even. If it’s not, skip to the next index.
  • From index i, move to the next index j as long as the number at j is less than or equal to the threshold.
  • If the number at j and the number at j-1 have the same parity (both even or both odd), break the loop.
  • At the end of each iteration, compare the length of the subarray (j - i) with the current maximum length and keep the larger one.
  • After checking all possible starting points, return the maximum length.

This solution iterates over the array once, so its time complexity is O(n), where n is the length of the array.

Comments added to LC discussion solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int longestAlternatingSubarray(vector<int>& nums, int threshold) {
    int ans = 0, i = 0, last = INT_MAX;
    while(i < nums.size()){
        if(nums[i] > threshold || (i > 0 && (nums[i] % 2) == (nums[i-1] % 2)) ){
            ans = max(ans, i - last );
            last = INT_MAX;
        }
        if(last == INT_MAX && nums[i] <= threshold && nums[i] % 2 == 0) last = i;
        i++;
    }
    ans = max(ans, i - last );
    return ans;
}

This C++ function, longestAlternatingSubarray(nums, threshold), takes a vector of integers nums and an integer threshold, and it returns the length of the longest subarray such that every element is not greater than threshold and the elements alternate between even and odd numbers.

Here is a step-by-step breakdown of the function:

  1. Initialize ans (which will hold the maximum length of the alternating subarray) to 0, i (the counter for the loop) to 0, and last (which will hold the starting index of the current alternating subarray) to INT_MAX.

  2. Start a while loop that continues as long as i is less than the size of the nums vector.

  3. Inside the loop, check if the current element nums[i] is greater than the threshold or if it has the same parity (odd or even) as the previous element. If either condition is true, update ans with the maximum of its current value and the length of the current alternating subarray (i - last), and reset last to INT_MAX.

  4. If last is INT_MAX, nums[i] is less than or equal to threshold, and nums[i] is even, then set last to i.

  5. Increment i to move to the next element.

  6. After the loop, update ans one more time to account for the possibility that the longest alternating subarray ends at the last element of nums.

  7. Finally, return ans.

This function uses a sliding window approach to find the longest subarray that meets the given conditions. It continuously adjusts the window as it iterates over the nums vector, tracking the longest window that it encounters.

Hey, Thanks for the solution and I understood it but I also did somewhat similar that 6061/6873 test cases are passed but I can’t understand where I did it wrong so can you please checkout my solution and tell me what’s wrong.

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

class Solution {
  public: int longestAlternatingSubarray(vector & nums, int threshold) {
    int longestSubarray = 0, subarray = 0;
    for (int i = 0; i < nums.size(); I++) {
      if (nums[i] % 2 == 0)
        while ((i < nums.size()) && (nums[i] <= threshold)) {
          if (i == nums.size() - 1)
            subarray++;

          if (i < nums.size() - 1 && (nums[i] % 2 != nums[i + 1] % 2))
            subarray++;
          I++;
        }
      longestSubarray = max(longestSubarray, subarray);
      subarray = 0;
    }
    return longestSubarray;
  }
};

Upon examining your code, it looks like the problem lies in how the while loop condition and inner if condition are structured. You are incrementing i inside the while loop but the termination condition for the while loop (i < nums.size()) is checked at the start of each iteration, not after you increment i. This could potentially lead to an ArrayOutOfBounds error.

Additionally, your inner if condition checks if the current number and the next number have different parity, but this check is also conducted on the last iteration where i is nums.size() - 1. This also risks an ArrayOutOfBounds error.

Here’s your adjusted code:

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

class Solution {
public:
    int longestAlternatingSubarray(vector<int>& nums, int threshold) {
        int longestSubarray = 0, subarray = 0;
        for(int i = 0; i < nums.size();) {
            if(nums[i] % 2 == 0 && nums[i] <= threshold) {
                subarray = 1;
                i++;
                while(i < nums.size() && nums[i] <= threshold && nums[i] % 2 != nums[i-1] % 2) {
                    subarray++;
                    i++;
                }
            } else {
                i++;
            }
            longestSubarray = max(longestSubarray, subarray);
            subarray = 0;
        }
        return longestSubarray;
    }
};

In this version, the ArrayOutOfBounds error is avoided by modifying the if condition inside the while loop to check that i is not the last index before comparing nums[i] and nums[i+1]. The check to increment subarray when i is the last index is also moved after the other if condition to avoid incorrect incrementing.

It’s important to remember that modifying loop counters inside a loop can often lead to bugs and is generally best avoided. Always double-check your boundary conditions in such cases.