LeetCode Solutions Blog

Longest Alternating Subarray

Number: 2870

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an integer array nums, find the maximum length of its contiguous subarrays that are alternating. A subarray is alternating if it has length m >= 2, the second element equals the first plus 1, and then the subarray alternates between two fixed values (i.e. follows the pattern [a, a+1, a, a+1, ...]). If no such subarray exists return -1.

Key Insights

The alternating pattern is rigid: once we identify two consecutive numbers where nums[i+1] == nums[i] + 1, the alternating subarray should keep alternating between these two values.
Once the pattern is broken, reset the alternating subarray length.
A single pass over the array maintaining a current alternating subarray length is sufficient.
Remember to check and update the maximum length found, and return -1 if no alternating subarray (length >= 2) is encountered.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the array, since we only traverse the array once. Space Complexity: O(1) as only a few auxiliary variables are used regardless of input size.

Solution

We approach this problem with a single pass iteration over the array. We maintain a variable to track the current alternating subarray length. For each pair of consecutive elements, if the difference equals 1 and the expected alternating value (which alternates between a and a+1) matches, we extend the current alternating sequence. Otherwise, we check if the pair forms a valid start (i.e., nums[i+1] == nums[i]+1) and restart the count accordingly. We also update the maximum length along the way. Finally, if the maximum length is less than 2 (which would indicate no valid alternating subarray), we return -1.

Code Solutions

# Python solution for Longest Alternating Subarray

def longestAlternatingSubarray(nums):
    # Initialize the max length to keep track of the longest alternating subarray
    max_length = 0
    # Current length of the alternating subarray
    curr_length = 1  # starts with first element
    # Iterate over the array starting from index 1
    for i in range(1, len(nums)):
        # If it is a valid continuation of alternating subarray
        if curr_length == 1 and nums[i] == nums[i-1] + 1:
            # Starting valid alternating sequence with at least two elements.
            curr_length = 2
        elif curr_length >= 2:
            # Determine the expected value based on the alternating pattern.
            # If current length is even, we expect nums[i] to be equal to nums[i-1] - 1,
            # Otherwise, for odd curr_length, we expect nums[i] to be equal to nums[i-1] + 1.
            if curr_length % 2 == 0 and nums[i] == nums[i-1] - 1:
                curr_length += 1
            elif curr_length % 2 == 1 and nums[i] == nums[i-1] + 1:
                curr_length += 1
            else:
                # The current alternating pattern breaks.
                # Update max_length if current sequence qualifies.
                max_length = max(max_length, curr_length)
                # Check if we can start a new alternating sequence beginning at i-1.
                if nums[i] == nums[i-1] + 1:
                    curr_length = 2
                else:
                    curr_length = 1
        else:
            # When curr_length is still 1 and current pair doesn't form a valid start.
            curr_length = 1
    # Final update for the last sequence observed
    max_length = max(max_length, curr_length)
    # If no valid alternating subarray (of length at least 2) was found, return -1
    return max_length if max_length >= 2 else -1

# Example usage:
print(longestAlternatingSubarray([2,3,4,3,4]))   # Output: 4
print(longestAlternatingSubarray([4,5,6]))         # Output: 2