# Longest Alternating Subarray
**Difficulty:** EASY
[External](https://leetcode.com/problems/longest-alternating-subarray)
Canonical: https://scaleengineer.com/dsa/problems/longest-alternating-subarray
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array
---
## 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 all **alternating** subarrays present in_ `nums` _or_ `-1` _if no such subarray exists_ _._

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

**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] <= 104`

# Approaches
## Iterating Through All Starting Points
This approach involves checking every possible starting position in the array for an alternating subarray. For each starting position `i`, we check if an alternating subarray can begin with `nums[i]` and `nums[i+1]`. If it can, we then try to extend this subarray as far as possible to the right, keeping track of the maximum length found.
**Time:** O(n²), where `n` is the length of `nums`. The nested loops give a quadratic time complexity in the worst case (e.g., an array that is entirely alternating). · **Space:** O(1), as we only use a few variables to store lengths and indices, requiring constant extra space.
**Pros:** Relatively simple to understand and implement.; Sufficiently efficient for the given constraints (`n <= 100`).
**Cons:** The time complexity is not optimal. For larger input arrays, this approach could be too slow.
### Explanation
The core idea is to use nested loops. The outer loop selects a starting index `i` for a potential subarray. The first condition for an alternating subarray is `s[1] = s[0] + 1`. So, for each `i`, we first check if `nums[i+1] == nums[i] + 1`. If this condition is met, we have found an alternating subarray of length 2. We initialize a `currentLength` to 2 and update our `maxLength`. Then, we use an inner loop (from `j = i + 2`) to see how far this subarray can be extended. The pattern of an alternating subarray is `[s₀, s₁, s₀, s₁, ...]`. This means that for any element at index `k`, it must be equal to the element at `k-2`. So, we check if `nums[j] == nums[j-2]`. If the pattern continues, we increment `currentLength` and update `maxLength`. If the pattern breaks, we stop extending from the starting index `i` and move to the next potential start. We initialize `maxLength` to -1, and if no alternating subarray is found, this value is returned.

```java
class Solution {
    public int alternatingSubarray(int[] nums) {
        int n = nums.length;
        int maxLength = -1;

        for (int i = 0; i < n - 1; i++) {
            // Check for the start of an alternating subarray
            if (nums[i + 1] == nums[i] + 1) {
                // Found a subarray of at least length 2
                int currentLength = 2;
                if (currentLength > maxLength) {
                    maxLength = currentLength;
                }

                // Try to extend this subarray
                for (int j = i + 2; j < n; j++) {
                    // The pattern is s[k] == s[k-2]
                    if (nums[j] == nums[j - 2]) {
                        currentLength++;
                        if (currentLength > maxLength) {
                            maxLength = currentLength;
                        }
                    } else {
                        // Pattern broken
                        break;
                    }
                }
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength` to -1 to store the maximum length found.
- Iterate through the array with an outer loop using index `i` from `0` to `n-1`. This index `i` represents the starting point of a potential alternating subarray.
- For each `i`, check if a valid alternating subarray of at least length 2 can start. This requires `i+1` to be a valid index and `nums[i+1]` to be equal to `nums[i] + 1`.
- If this condition is met, we have found an alternating subarray of length 2. We update `maxLength` to be at least 2.
- We then start an inner loop with index `j` from `i+2` to `n-1` to try and extend this subarray.
- The condition for extending the subarray is based on the alternating pattern `[s₀, s₁, s₀, s₁, ...]`, which implies that `s[k] == s[k-2]`. In terms of the `nums` array, this means we check if `nums[j] == nums[j-2]`.
- If the pattern holds, we increment the length of the current alternating subarray and update `maxLength` if the new length is greater.
- If the pattern breaks (`nums[j] != nums[j-2]`), we stop extending from the current starting point `i` and break the inner loop.
- After checking all possible starting points, the final value of `maxLength` is the answer.

## Single Pass Linear Scan
A more efficient approach is to iterate through the array just once. We can maintain the length of the current alternating subarray ending at the previous position. At each new position, we determine if we can extend the current subarray or if a new one starts, updating the maximum length found so far in a single pass. This approach can be seen as a space-optimized dynamic programming solution.
**Time:** O(n), where `n` is the length of `nums`. We iterate through the array only once. · **Space:** O(1), as we only use a constant number of extra variables regardless of the input size.
**Pros:** Optimal time complexity, making it efficient for any input size.; Optimal space complexity, as it uses only a constant amount of extra memory.
**Cons:** The logic is slightly more complex to derive compared to the brute-force approach.
### Explanation
We iterate through the array from the second element (`i = 1`). At each step, we decide the length of the alternating subarray ending at the current index `i`. This length depends on the length of the alternating subarray ending at `i-1` and the values of `nums[i]`, `nums[i-1]`, and `nums[i-2]`. Let `currentLength` be the length of the alternating subarray ending at the *previous* index, `i-1`. When we consider index `i`, we first check if we can extend the previous subarray. This is possible if `currentLength > 0` (meaning there was an active alternating subarray) and `nums[i] == nums[i-2]` (the alternating pattern continues). If so, the new length is `currentLength + 1`. If we cannot extend, we check if a new alternating subarray of length 2 starts at `i-1`. This happens if `nums[i] == nums[i-1] + 1`. If so, the new length is 2. If neither of these conditions is met, there is no alternating subarray ending at `i`, so the length is reset. We use a variable `currentLength` to track the length of the alternating subarray ending at the *current* index `i`, and update a `maxLength` variable at each step.

```java
class Solution {
    public int alternatingSubarray(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return -1;
        }
        
        int maxLength = 0;
        int currentLength = 0; // Length of alternating subarray ending at i-1

        for (int i = 1; i < n; i++) {
            int newLength;
            // Check if we can extend the previous alternating subarray
            if (currentLength > 0 && nums[i] == nums[i - 2]) {
                newLength = currentLength + 1;
            } else {
                // If not, check if a new alternating subarray starts here
                if (nums[i] == nums[i - 1] + 1) {
                    newLength = 2;
                } else {
                    // No alternating subarray ending at i
                    newLength = 0;
                }
            }
            currentLength = newLength;
            if (currentLength > maxLength) {
                maxLength = currentLength;
            }
        }

        return maxLength > 1 ? maxLength : -1;
    }
}
```
### Algorithm
- Handle the edge case where the array has fewer than two elements by returning -1.
- Initialize `maxLength = 0` to store the result and `currentLength = 0` to track the length of the alternating subarray ending at the current position.
- Iterate through the array with index `i` from `1` to `n-1`.
- At each `i`, we first check if we can extend the alternating subarray that ended at `i-1`. This is possible if `currentLength > 0` (an alternating subarray was active) and `nums[i] == nums[i-2]` (the pattern `s[k] = s[k-2]` holds). If so, we increment `currentLength`.
- If we cannot extend, we check if a new alternating subarray of length 2 starts at `i-1`. This is true if `nums[i] == nums[i-1] + 1`. If so, we set `currentLength = 2`.
- If neither of the above conditions is met, then no alternating subarray ends at `i`. We reset `currentLength = 0`.
- After determining the `currentLength` for the subarray ending at `i`, we update `maxLength = max(maxLength, currentLength)`.
- After the loop, if `maxLength` is greater than 1, it means we found at least one valid alternating subarray, so we return `maxLength`. Otherwise, we return -1.

# Solutions
### Java

```java
class Solution {
public
  int alternatingSubarray(int[] nums) {
    int ans = -1, n = nums.length;
    for (int i = 0; i < n; ++i) {
      int k = 1;
      int j = i;
      for (; j + 1 < n && nums[j + 1] - nums[j] == k; ++j) {
        k *= -1;
      }
      if (j - i + 1 > 1) {
        ans = Math.max(ans, j - i + 1);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int alternatingSubarray(vector<int> &nums) {
    int ans = -1, n = nums.size();
    for (int i = 0; i < n; ++i) {
      int k = 1;
      int j = i;
      for (; j + 1 < n && nums[j + 1] - nums[j] == k; ++j) {
        k *= -1;
      }
      if (j - i + 1 > 1) {
        ans = max(ans, j - i + 1);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def alternatingSubarray(self, nums: List[int]) -> int: ans, n = - 1, len(nums) for i in range(n): k = 1 j = i while j + 1 < n and nums[j + 1] - nums[j] == k: j += 1 k *= - 1 if j - i + 1 > 1: ans = max(ans, j - i + 1) return ans

```