algoadvance

Leetcode 2760. Longest Even Odd Subarray With Threshold

Problem Statement

You are given an array of integers arr and an integer threshold. You need to find the length of the longest subarray where:

  1. All the subarray elements are less than or equal to threshold.
  2. The elements of the subarray alternate between even and odd numbers.

Return the length of this longest even-odd alternating subarray.

Clarifying Questions

  1. Input Format:
    • Can we assume arr is not empty?
    • Are the elements in arr all positive integers?

    Yes, for this problem, you can assume that arr is not empty and all the elements are positive integers.

  2. Output Format:
    • Should the function return 0 if no such subarray exists?
    • Should we consider subarrays of length 1?

    Yes, return 0 if no such subarray exists, and yes, subarrays of length 1 should be considered, provided they meet the criteria.

Strategy

  1. Initialize variables to keep track of the current longest alternating subarray and the maximum length of any such subarray found.
  2. Traverse the array while keeping a count of the alternating subarray length, and check the given conditions.
  3. Reset the length counter when encountering a value greater than the threshold or when the alternating property is violated.
  4. Continuously update the maximum length during the traversal.

Code

public class LongestEvenOddSubarray {
    public int longestAlternatingSubarray(int[] arr, int threshold) {
        int maxLength = 0;
        int currentLength = 0;
        int n = arr.length;
        
        for (int i = 0; i < n; i++) {
            if (arr[i] > threshold) {
                currentLength = 0; // reset length if element exceeds threshold
                continue;
            }
            
            if (currentLength == 0) { 
                // Start a new subarray
                currentLength = 1;
            } else {
                int prevElem = arr[i - 1];
                if ((prevElem % 2 == 0 && arr[i] % 2 != 0) || (prevElem % 2 != 0 && arr[i] % 2 == 0)) {
                    currentLength++;
                } else {
                    currentLength = 1; // reset length if alternating pattern is broken
                }
            }
            
            maxLength = Math.max(maxLength, currentLength);
        }
        
        return maxLength;
    }

    public static void main(String[] args) {
        LongestEvenOddSubarray obj = new LongestEvenOddSubarray();
        int[] arr = {1, 2, 3, 4, 5};
        int threshold = 5;
        System.out.println(obj.longestAlternatingSubarray(arr, threshold)); // Output should be 5
    }
}

Time Complexity

This approach ensures that we efficiently find the longest subarray that alternates between even and odd numbers and does not exceed the given threshold.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI