algoadvance

Leetcode 2765. Longest Alternating Subarray

Problem Statement

Leetcode Problem 2765: Longest Alternating Subarray

Given an array of integers nums, find the length of the longest subarray with alternating even and odd numbers. An alternating subarray starts with an even number and alternates between even and odd numbers until the end.

Clarifying Questions

  1. Array Size: What is the range of the size of the nums array?
    • Typically, constraints on the problem will define this, but we will assume it can be reasonably large (potentially up to (10^5) elements).
  2. Data Range: What values can the integers in the array take?
    • Usually not an issue, but integers are assumed to cover the typical range of 32-bit integers.
  3. Output: Are we just returning the length of the longest alternating subarray, or do we need to return the subarray itself?
    • The problem asks only for the length of the longest alternating subarray.

Strategy

  1. Initialization:
    • Initialize variables to store the maximum length (max_len) found so far.
    • Another variable to keep track of the current length (curr_len) of the alternating subarray as we traverse the array.
  2. Traversal:
    • Iterate through the array starting from the first element.
    • For each pair of consecutive elements, check if one is even and the other is odd.
    • If the pair alternates, increase the curr_len.
    • If not, compare curr_len to max_len to update the latter if necessary, then reset curr_len.
  3. Edge Case:
    • Single element arrays and arrays without any alternating pattern should be considered.
  4. Final Comparison:
    • After the loop, a final comparison between curr_len and max_len is necessary to check if the longest alternating subarray ends at the last element.

Time Complexity

Code

#include <vector>
#include <algorithm>

using namespace std;

int longestAlternatingSubarray(vector<int>& nums) {
    int n = nums.size();
    
    if (n == 0) return 0; // edge case: empty array
    
    int max_len = 1; // Minimum length of an alternating subarray is 1
    int curr_len = 1; // Starting with the first element
    
    // Traverse through the array
    for (int i = 1; i < n; ++i) {
        if ((nums[i-1] % 2 == 0 && nums[i] % 2 != 0) || (nums[i-1] % 2 != 0 && nums[i] % 2 == 0)) {
            // They alternate
            curr_len++;
        } else {
            // They do not alternate, update max_len and reset curr_len
            max_len = max(max_len, curr_len);
            curr_len = 1; // Start a new subarray from the current element
        }
    }
    
    // Final check in case the longest subarray ends at the last element
    max_len = max(max_len, curr_len);
    
    return max_len;
}

In this implementation, we leverage a single pass through the input array while maintaining counts of alternating subarray lengths and adjusting as necessary. This solution handles the primary task efficiently with linear complexity.

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