Longest Alternating Subarray

Problem

You are given a 0-indexed integer array nums. A subarray s of length m is called alternating if:

• m is greater than 1.
• s1 = s0 + 1.
• The 0-indexed subarray s looks like [s0, s1, s0, s1,...,s(m-1) % 2]. In other words, s1 - s0 = 1, s2 - s1 = -1, s3 - s2 = 1, s4 - s3 = -1, and so on up to s[m - 1] - s[m - 2] = (-1)m.

Return _the maximum length of allalternating subarrays present in _nums or-1 if no such subarray exists .

A subarray is a contiguous non-empty sequence of elements within an array.

Examples

Example 1

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

Output: 4

Explanation:

The alternating subarrays are `[2, 3]`, `[3,4]`, `[3,4,3]`, and `[3,4,3,4]`.
The longest of these is `[3,4,3,4]`, which is of length 4.

Example 2

Input: nums = [4,5,6]

Output: 2

Explanation:

`[4,5]` and `[5,6]` are the only two alternating subarrays. They are both of
length 2.

Constraints

• 2 <= nums.length <= 100
• 1 <= nums[i] <= 10^4

Solution

Method 1 – Sliding Window/Enumeration (1)

Intuition

We look for the longest subarray where the elements alternate between two values differing by 1, starting with s0 and s1 = s0 + 1. We can check each possible starting point and expand as long as the alternating pattern holds.

Approach

1. Initialize a variable to track the maximum length found (ans).
2. For each index i in nums, if nums[i+1] == nums[i] + 1, start expanding from i:
   • Alternate between +1 and -1 for each step, checking if the pattern holds.
   • Keep track of the current length.
   • Update ans if a longer valid subarray is found.
3. Return ans if at least one valid subarray is found, else return -1.

Code

C++

class Solution {
public:
    int alternatingSubarray(vector<int>& nums) {
        int n = nums.size(), ans = -1;
        for (int i = 0; i < n-1; ++i) {
            if (nums[i+1] != nums[i]+1) continue;
            int len = 2, j = i+2, sign = -1;
            while (j < n && nums[j] - nums[j-1] == sign) {
                len++;
                sign *= -1;
                j++;
            }
            ans = max(ans, len);
        }
        return ans;
    }
};

Go

func alternatingSubarray(nums []int) int {
    n, ans := len(nums), -1
    for i := 0; i < n-1; i++ {
        if nums[i+1] != nums[i]+1 {
            continue
        }
        l, j, sign := 2, i+2, -1
        for j < n && nums[j]-nums[j-1] == sign {
            l++
            sign *= -1
            j++
        }
        if l > ans {
            ans = l
        }
    }
    return ans
}

Java

class Solution {
    public int alternatingSubarray(int[] nums) {
        int n = nums.length, ans = -1;
        for (int i = 0; i < n-1; i++) {
            if (nums[i+1] != nums[i]+1) continue;
            int len = 2, j = i+2, sign = -1;
            while (j < n && nums[j] - nums[j-1] == sign) {
                len++;
                sign *= -1;
                j++;
            }
            ans = Math.max(ans, len);
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun alternatingSubarray(nums: IntArray): Int {
        val n = nums.size
        var ans = -1
        for (i in 0 until n-1) {
            if (nums[i+1] != nums[i]+1) continue
            var len = 2
            var j = i+2
            var sign = -1
            while (j < n && nums[j] - nums[j-1] == sign) {
                len++
                sign *= -1
                j++
            }
            ans = maxOf(ans, len)
        }
        return ans
    }
}

Python

class Solution:
    def alternatingSubarray(self, nums: list[int]) -> int:
        n = len(nums)
        ans = -1
        for i in range(n-1):
            if nums[i+1] != nums[i]+1:
                continue
            l, j, sign = 2, i+2, -1
            while j < n and nums[j] - nums[j-1] == sign:
                l += 1
                sign *= -1
                j += 1
            ans = max(ans, l)
        return ans

Rust

impl Solution {
    pub fn alternating_subarray(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut ans = -1;
        for i in 0..n-1 {
            if nums[i+1] != nums[i]+1 { continue; }
            let mut len = 2;
            let mut j = i+2;
            let mut sign = -1;
            while j < n && nums[j] - nums[j-1] == sign {
                len += 1;
                sign *= -1;
                j += 1;
            }
            ans = ans.max(len);
        }
        ans
    }
}

TypeScript

class Solution {
    alternatingSubarray(nums: number[]): number {
        const n = nums.length;
        let ans = -1;
        for (let i = 0; i < n-1; i++) {
            if (nums[i+1] !== nums[i]+1) continue;
            let len = 2, j = i+2, sign = -1;
            while (j < n && nums[j] - nums[j-1] === sign) {
                len++;
                sign *= -1;
                j++;
            }
            ans = Math.max(ans, len);
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n^2), where n is the length of nums. For each start, we may scan the rest of the array.
• 🧺 Space complexity: O(1), only a few variables are used.