2760. Longest Even Odd Subarray With Threshold
Problem Description
The problem presents an integer array nums
and an integer threshold
. The task is to determine the length of the longest subarray starting at index l
and ending at index r
, where 0 <= l <= r < nums.length
. The subarray should satisfy these conditions:
- The first element of the subarray,
nums[l]
, must be even (nums[l] % 2 == 0
). - Adjacent elements in the subarray must have different parity ā that is, one is even and the other is odd. For any two consecutive elements
nums[i]
andnums[i + 1]
within the subarray, their mod 2 results must be different (nums[i] % 2 != nums[i + 1] % 2
). - Every element within the subarray must be less than or equal to the
threshold
(nums[i] <= threshold
).
The goal is to return the length of such the longest subarray meeting these criteria.
Intuition
To find the longest subarray that satisfies the problem conditions, we can iterate through the array. For each potential starting index l
of a subarray, we check whether the starting element is even and less than or equal to the threshold. If it is, we try to extend the subarray by moving the right index r
as far as possible while maintaining the alternating even-odd sequence and ensuring all elements are within the threshold.
The process is as follows:
- We iterate over each index
l
in the arraynums
as a potential start of the subarray. - If
nums[l]
is even and less than or equal to the threshold, we have a potential subarray starting atl
. We initializer
asl + 1
because a subarray must be non-empty. - We now extend the subarray by incrementing
r
as long asnums[r]
alternates in parity withnums[r-1]
andnums[r]
is less than or equal to the threshold. - Once we can no longer extend
r
because the next element violates one of our conditions, we calculate the current subarray length asr - l
. We track the maximum length found throughout this process with the variableans
. - Continue the same process for each index
l
in the array and returnans
, which will hold the maximum length of the longest subarray that meets all the criteria.
By following this approach, we can ensure that we check all possible subarrays that start with an even number and have alternating parities until we either reach the end of the array or encounter elements that do not fulfill the conditions.
Learn more about Sliding Window patterns.
Solution Approach
The implementation uses a straightforward approach, which essentially follows the sliding window pattern. Sliding window is a common pattern used in array/string problems where a subarray or substring is processed, and then the window either expands or contracts to satisfy certain conditions.
Here's a step-by-step breakdown of the algorithm based on the given solution approach:
-
Initialize a variable
ans
to store the maximum length found for any subarray that satisfies the problem conditions. Also, determine the lengthn
of the input arraynums
. -
Start the first for-loop to iterate over the array using the index
l
, which represents the potential start of the subarray. -
Inside this loop, first check whether the element at index
l
is both even (nums[l] % 2 == 0
) and less than or equal to the giventhreshold
. Only if these conditions are met, the element atl
can be the starting element of a subarray. -
If the starting element is suitable, initialize the end pointer
r
for the subarray tol + 1
. This is where the window starts to slide. -
Use a while loop to try expanding this window. The loop will continue as long as
r
is less thann
, the array length, ensuring array bounds are not exceeded. -
In each iteration of the while loop, check two conditions: whether the parity at
nums[r]
is different fromnums[r - 1]
(nums[r] % 2 != nums[r - 1] % 2
) and ifnums[r]
is less than or equal tothreshold
. This ensures the subarray keeps alternating between even and odd numbers with values within the threshold. -
As long as these conditions are satisfied, increment
r
to include the next element in the subarray. If either condition fails, the while loop breaks, and the current window cannot be expanded further. -
Once the while loop ends, calculate the length of the current subarray by
r - l
and updateans
with the maximum of its current value and this newly found length. -
After processing the potential starting index
l
, the for loop moves to the next possible start index and repeats the steps until the whole array is scanned. -
At the end of the for loop,
ans
contains the length of the longest subarray satisfying the given conditions, and it's returned as the final answer.
The solution does not use any additional data structures, and its space complexity is O(1), which represents constant space aside from the input array. The time complexity is O(n^2) in the worst case, where n
is the number of elements in nums
, because for each element in nums
as a starting point, we might need to check up to n
elements to find the end of the subarray.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through an example to illustrate the solution approach.
Consider an array nums = [2, 3, 4, 6, 7]
and a threshold = 5
.
Following the steps outlined in the solution approach:
- Initialize
ans
to0
. The length of the arrayn
is5
. - Start iterating over the array with index
l
ranging from0
ton-1
. - At
l = 0
, we findnums[0] = 2
, which is even and less than the threshold, so this can be the start of a subarray. - Initiate
r
tol+1
, which is1
. - We enter the while loop to expand the window starting at
l = 0
:r = 1
:nums[1] = 3
which is different in parity fromnums[0]
and is also below the threshold. Incrementr
to2
.r = 2
:nums[2] = 4
, which fails the alternating parity condition. Break the while loop.
- Calculate the current subarray length:
r - l = 2 - 0 = 2
. Updateans
tomax(ans, 2) = 2
. - Increment
l
to1
and repeat the steps:nums[1] = 3
is odd, so we skip this as it can't be the start of a subarray.
- Increment
l
to2
. No suitable subarray starting from here sincenums[2] = 4
does not meet the parity alternation condition with any element afterward, and it's above the threshold. - Move on to
l = 3
. Again,nums[3] = 6
is above the threshold, so we skip this index. - Lastly,
l = 4
. Sincenums[4] = 7
is not even, we skip this index.
After iterating through all elements, the maximum subarray length that satisfies the conditions is stored in ans
, which is 2 in this example. So the function returns 2
.
This illustrates the entire process of checking each potential starting index and trying to expand the window to find the longest subarray that satisfies the given criteria.
Solution Implementation
1from typing import List
2
3class Solution:
4 def longest_alternating_subarray(self, nums: List[int], threshold: int) -> int:
5 """
6 Finds the length of the longest subarray where adjacent elements have different parity
7 and each element does not exceed the given threshold.
8
9 :param nums: List of integers to find the longest alternating subarray from.
10 :param threshold: An integer representing the maximum allowed value for array elements.
11 :return: The length of the longest alternating subarray.
12 """
13
14 # Initialize the maximum length of the alternating subarray.
15 max_length = 0
16 # Get the number of elements in the nums list.
17 num_elements = len(nums)
18
19 # Iterate through the list to find all starting points of potential alternating subarrays.
20 for left in range(num_elements):
21 # Check if the current element satisfies the parity and threshold condition.
22 if nums[left] % 2 == 0 and nums[left] <= threshold:
23 # Initialize the right pointer which will try to extend the subarray to the right.
24 right = left + 1
25 # Extend the subarray while the elements alternate in parity and are within the threshold.
26 while (right < num_elements and
27 nums[right] % 2 != nums[right - 1] % 2 and
28 nums[right] <= threshold):
29 right += 1
30 # Update the maximum length if a longer subarray is found.
31 max_length = max(max_length, right - left)
32
33 # Return the maximum length of the subarray found.
34 return max_length
35
1class Solution {
2 // Method to find the length of the longest alternating subarray
3 // given that each element should not exceed a certain threshold.
4 public int longestAlternatingSubarray(int[] nums, int threshold) {
5 int maxLen = 0; // Initialize maximum length of alternating subarray
6 int n = nums.length; // Store the length of the input array
7
8 // Loop through each element in the array as the starting point
9 for (int left = 0; left < n; ++left) {
10 // Check if current starting element is even and lower than or equal to threshold
11 if (nums[left] % 2 == 0 && nums[left] <= threshold) {
12 int right = left + 1; // Initialize the pointer for the end of subarray
13
14 // Extend the subarray towards the right as long as:
15 // 1. The current element alternates in parity with previous (even/odd)
16 // 2. The current element is below or equal to the threshold
17 while (right < n && nums[right] % 2 != nums[right - 1] % 2 && nums[right] <= threshold) {
18 ++right; // Move to the next element
19 }
20
21 // Update the maximum length if a longer alternating subarray is found
22 maxLen = Math.max(maxLen, right - left);
23 }
24 }
25 // Return the length of the longest alternating subarray found
26 return maxLen;
27 }
28}
29
1#include <vector>
2#include <algorithm> // For using the max() function
3
4class Solution {
5public:
6 // Function to find the length of the longest subarray with alternating even and odd numbers
7 // not exceeding a given threshold
8 int longestAlternatingSubarray(vector<int>& nums, int threshold) {
9 int longestLength = 0; // This will hold the maximum length found
10 int size = nums.size(); // Store the size of nums to avoid multiple size() calls
11
12 // Iterate over each element in the nums array
13 for (int left = 0; left < size; ++left) {
14 // Check if the current element is even and within the threshold
15 if (nums[left] % 2 == 0 && nums[left] <= threshold) {
16 int right = left + 1; // Start a pointer to expand the subarray to the right
17
18 // Continue while right pointer is within array bounds and
19 // the subarray satisfies the conditions (alternating and within the threshold)
20 while (right < size && nums[right] % 2 != nums[right - 1] % 2 && nums[right] <= threshold) {
21 ++right; // Move the right pointer to the next element
22 }
23
24 longestLength = max(longestLength, right - left); // Update the maximum length found
25 }
26 }
27 // Return the length of the longest subarray found
28 return longestLength;
29 }
30};
31
1function longestAlternatingSubarray(nums: number[], threshold: number): number {
2 // 'n' is the length of the input array 'nums'
3 const n = nums.length;
4 let maxLength = 0; // Stores the maximum length of the alternating subarray
5
6 // Iterate over the array starting from each index 'left'
7 for (let left = 0; left < n; ++left) {
8 // Check if the current element is even and lesser than or equal to the threshold
9 if (nums[left] % 2 === 0 && nums[left] <= threshold) {
10 let right = left + 1; // Start from the next element
11
12 // Proceed to the right in the array while alternating between odd and even
13 // and ensuring the values are below or equal to the threshold
14 while (right < n && nums[right] % 2 !== nums[right - 1] % 2 && nums[right] <= threshold) {
15 ++right; // Move to the next element
16 }
17
18 // Calculate the length of the current alternating subarray and update the max length
19 maxLength = Math.max(maxLength, right - left);
20 }
21 }
22
23 // Return the length of the longest alternating subarray found
24 return maxLength;
25}
26
Time and Space Complexity
Time Complexity
The time complexity of the given code can be analyzed by considering that there are two nested loops: an outer loop that runs from l
from 0
to n - 1
, and an inner while loop that potentially runs from l + 1
to n
in the worst case when all the elements conform to the specified condition (alternating even and odd values under the threshold).
In the worst-case scenario, the inner loop can iterate n
times for the first run, then n-1
times, n-2
times, and so forth until 1 time. This forms an arithmetic progression that sums up to (n * (n + 1)) / 2
iterations in total.
Hence, the worst-case time complexity of the function is O(n^2)
.
Space Complexity
The space complexity of the given code is constant, O(1)
, as it only uses a fixed number of variables (ans
, n
, l
, r
) and does not allocate any additional space that grows with the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these pictures shows the visit order of a depth-first search?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!