2765. Longest Alternating Subarray

EasyView on LeetCode

Array

Time: O(n)

Space: O(1)

Problem Overview

Find the longest subarray where consecutive differences strictly alternate between +1 and -1 (not general sign flips).

Intuition

Find the longest subarray where consecutive differences strictly alternate between +1 and -1 (not general sign flips). Track the current run length: extend when the next diff matches the expected +1 or -1; otherwise reset to a new run of length 2 or 1. Return -1 if no alternating subarray of length >= 2 exists.

Algorithm

1Initialize ans = 1, dp = 1 (length of run ending at previous index).
2For i from 1 to n-1: expected diff is +1 if dp is odd length, -1 if even.
3If nums[i] - nums[i-1] == expected: dp++.
4Else if diff == +1: reset dp = 2 (start new run at i-1..i).
5Else: reset dp = 1. Update ans = max(ans, dp).
6Return ans == 1 ? -1 : ans.

Example Walkthrough

Input: nums = [1,2,3,4,3,2,1]

1.Diffs +1,+1 break alternation; best run may be shorter segments like 1,2,3,4,3 (diffs +1,+1,-1).

Output: length of longest valid alternating subarray

Common Pitfalls

•Only +1 and -1 diffs count — zero or larger gaps reset the pattern.
•Return -1 when no subarray of length >= 2 alternates.
•Subarray must be contiguous, not subsequence.

2765.cs

// Approach: DP; dp[i] = run length if alternating diff holds, else reset to 1.
// Time: O(n) Space: O(1)

public class Solution
{
    public int AlternatingSubarray(int[] nums)
    {
        int ans = 1;
        int dp = 1;

        for (int i = 1; i < nums.Length; ++i)
        {
            int targetDiff = dp % 2 == 0 ? -1 : 1;
            // Append nums[i] to the current alternating subarray.
            if (nums[i] - nums[i - 1] == targetDiff)
                ++dp;
            // Reset the alternating subarray to nums[i - 1..i].
            else if (nums[i] - nums[i - 1] == 1)
                dp = 2;
            // Reset the alternating subarray to nums[i].
            else
                dp = 1;
            ans = Math.Max(ans, dp);
        }

        return ans == 1 ? -1 : ans;
    }
}

Was this solution helpful?