Step-by-Step Solution to LeetCode 2765: Longest Alternating Subarray

It’s currently ‘running streak’ week for me, and I’ve been tackling problems related to the maximum subarray sum problems. Today, 14 May 2025, I tackled LeetCode problem 2765: "Longest Alternating Subarray."

Though LeetCode ranks this as "easy," I'd categorize it as medium-easy or even medium difficulty, especially if you're new to the pattern and trying to grasp it.

This problem is similar to the classic maximum subarray problem but with an interesting twist: instead of finding a subarray with the maximum sum, we need to find the longest subarray where elements alternate in a specific pattern.

Here’s how I made sense of LeetCode 2765: Longest Alternating Subarray

Note: This isn’t my original solution; I initially had trouble understanding the approach, but the logic became much clearer after I analyzed what was happening at each step.

Problem

We’re given an array nums. We must find the longest contiguous subarray that:

• Contains at least two elements

• Alternates in differences: +1, -1, +1, -1... i.e, it must start with a +1 jump (i.e., nums[i+1] == nums[i] + 1), and then continue alternating.

Intuition

To solve this problem, we need to identify subarrays where elements alternate in the following pattern:

• If the current length is odd, the next difference should be negative

• If the current length is even, the next difference should be positive

Or more simply, we’re looking for a pattern where differences look like: +1, -1, +1, -1, ...

We'll use a rolling window approach of some sort, keeping track of the current streak length, resetting it when the pattern breaks, and checking if a new valid streak is starting.

Approach

We'll use two variables:

• ansThe length of the longest alternating subarray found so far

• dpThe length of the current alternating subarray we're building

We initialize both to 1 (1 is not a valid answer, but a starting point).

ans, dp = 1, 1

Then we loop through the array from the second element.

This tells us whether we're expecting a +1 or -1 based on the current streak length.

• If dp is odd, the next difference should be negative (nums[i] < nums[i-1])

• If dp is even, the next difference should be positive (nums[i] > nums[i-1])

Remember +1, -1, +1, -1 e.g [3, 4, 3, 4]

Then check for and handle the three possible cases:

1. If the difference between the current and previous element matches the expected target:

    if nums[i]-nums[i-1] == target_diff:
        dp += 1
   

2. If the first condition is not met but we find a new streak (i.e, the current and previous elements form a valid [a, a+1] pair:), we’ll bind the value of the current count to 2.

    elif nums[i]-nums[i-1] == 1:
        dp = 2
   

3. If neither of the above conditions is met, restart from 1.

    else:
        dp = 1
   

At the end of each check, update ans by comparing dp with the maximum value we’ve found so far.

ans = max(dp, ans)

Finally, return ans or return -1 if no valid subarray was found (i.e, answer never got above 1)

return ans if ans != 1 else -1

Example

Consider [3, 4, 3, 4]:

• Start with ans=1, dp=1

• At index 1: nums[1] = 4, nums[0] = 3

  • Difference: +1 (positive)

  • dp is odd (1), we expected a positive difference ✓

  • Update: dp = 2, ans = 2

• At index 2: nums[2] = 3, nums[1] = 4

  • Difference: -1 (negative)

  • dp is even (2), we expected a negative difference ✓

  • Update: dp = 3, ans = 3

• At index 3: nums[3] = 4, nums[2] = 3

  • Difference: +1 (positive)

  • dp is odd (3), we expected a positive difference ✓

  • Update: dp = 4, ans = 4

Final answer: 4

Solution

def longestAlternatingSubarray(nums):
    ans, dp = 1, 1

    for i in range(1, len(nums)):
        # If current length is even, we expect -1 difference
        if dp % 2 == 0 and nums[i] < nums[i-1]:
            dp += 1

        # If current length is odd, we expect +1 difference
        elif dp % 2 == 1 and nums[i] > nums[i-1]:
            dp += 1

        # Start a new streak if nums[i] == nums[i-1] + 1
        elif nums[i] > nums[i-1]:
            dp = 2

        # Otherwise, restart
        else:
            dp = 1

        ans = max(ans, dp)

    # Check if we have a valid subarray (minimum length 2)
    return ans if ans != 1 else -1

Complexity:

Time complexity: O(n). We iterate through the list once.

Space complexity: O(1). We only use a fixed number of variables (dp, ans, loop index) regardless of input size.

If this helped clarify the logic for you, feel free to share or comment. I’ll be documenting more of these solutions as I go.