# Count Alternating Subarrays
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-alternating-subarrays)
Canonical: https://scaleengineer.com/dsa/problems/count-alternating-subarrays
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array
**Companies:** [Capital One](https://scaleengineer.com/companies/capital-one)
---
## Problem
You are given a binary array `nums`.

We call a subarray **alternating** if **no** two **adjacent** elements in the subarray have the **same** value.

Return _the number of alternating subarrays in_ `nums`.

**Example 1:**

**Input:** nums = \[0,1,1,1\]

**Output:** 5

**Explanation:**

The following subarrays are alternating: `[0]`, `[1]`, `[1]`, `[1]`, and `[0,1]`.

**Example 2:**

**Input:** nums = \[1,0,1,0\]

**Output:** 10

**Explanation:**

Every subarray of the array is alternating. There are 10 possible subarrays that we can choose.

**Constraints:**

* `1 <= nums.length <= 105`
* `nums[i]` is either `0` or `1`.

# Approaches
## Brute Force Enumeration
The most straightforward approach is to generate every possible subarray and then, for each one, check if it satisfies the 'alternating' property. An alternating subarray is one where no two adjacent elements are the same.
**Time:** O(n³), where n is the number of elements in `nums`. There are O(n²) subarrays, and checking each one takes up to O(n) time. · **Space:** O(1), as we only use a constant amount of extra space for loop variables and a counter.
**Pros:** Easy to understand and implement.; Correct for small input sizes.
**Cons:** Extremely inefficient due to its cubic time complexity.; Will result in a 'Time Limit Exceeded' error for large inputs as specified in the problem constraints.
### Explanation
This method systematically considers every contiguous block of elements in the input array. It uses two nested loops to define the start (`i`) and end (`j`) indices of a subarray. For each generated subarray, a third loop is employed to traverse its elements and verify the alternating condition. If at any point `nums[k] == nums[k-1]`, the subarray is not alternating. If the entire subarray is traversed without this condition being met, it is counted as a valid alternating subarray. While simple, this approach is computationally expensive because it repeatedly re-scans overlapping parts of the array.

```java
class Solution {
    public long countAlternatingSubarrays(int[] nums) {
        long count = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                // Check if subarray nums[i...j] is alternating
                boolean isAlternating = true;
                for (int k = i + 1; k <= j; k++) {
                    if (nums[k] == nums[k - 1]) {
                        isAlternating = false;
                        break;
                    }
                }
                if (isAlternating) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Use a nested loop to generate all possible subarrays. The outer loop `i` runs from `0` to `n-1` for the start index, and the inner loop `j` runs from `i` to `n-1` for the end index.
- For each subarray `nums[i...j]`, use a third loop `k` from `i+1` to `j` to check if it's alternating.
- Inside the third loop, check if `nums[k] == nums[k-1]`. If they are equal, the subarray is not alternating. Set a flag and break the check.
- If the check completes without finding any adjacent equal elements, the subarray is alternating. Increment `count`.
- After all subarrays are checked, return `count`.

## Optimized Brute Force
This approach improves upon the naive brute-force method by eliminating redundant checks. Instead of re-validating an entire subarray from scratch, we build upon previously validated alternating subarrays. We check if we can extend an alternating subarray by one element at a time.
**Time:** O(n²), where n is the length of `nums`. In the worst-case scenario (a fully alternating array), the inner loop runs O(n) times for each of the O(n) iterations of the outer loop. · **Space:** O(1), as no extra data structures are needed that scale with the input size.
**Pros:** More efficient than the naive O(n³) brute force.; Still relatively straightforward to implement.
**Cons:** While better than the O(n³) approach, it is still too slow for the given constraints and will time out.
### Explanation
We iterate through each element of the array, considering it as a potential start of an alternating subarray. For each starting index `i`, we count the subarray `[nums[i]]` and then try to extend it to the right. We use a second loop with index `j` to move forward. As long as `nums[j]` is different from `nums[j-1]`, the subarray `nums[i...j]` is alternating, and we add it to our count. The moment we find `nums[j] == nums[j-1]`, we know that no further extension from `i` can form an alternating subarray, so we break the inner loop and proceed to the next starting index `i+1`. This optimization reduces the complexity from cubic to quadratic.

```java
class Solution {
    public long countAlternatingSubarrays(int[] nums) {
        long count = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            count++; // For subarray [nums[i]]
            for (int j = i + 1; j < n; j++) {
                if (nums[j] != nums[j - 1]) {
                    count++;
                } else {
                    break;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Use an outer loop `i` from `0` to `n-1` to iterate through all possible starting positions of a subarray.
- For each `i`, we know the subarray of length one, `[nums[i]]`, is always alternating, so we add 1 to `count`.
- Start an inner loop `j` from `i+1` to `n-1` to extend the subarray.
- In each step of the inner loop, check if `nums[j] != nums[j-1]`.
- If they are different, the subarray `nums[i...j]` is also alternating, so increment `count`.
- If they are the same, the alternating property is broken. Any longer subarray starting at `i` will also not be alternating, so we can `break` the inner loop and move to the next starting position `i+1`.
- Return the total `count`.

## Linear Scan (Dynamic Programming / Sliding Window)
The most efficient solution involves a single pass through the array, leveraging a dynamic programming or sliding window concept. The key insight is that the total count can be found by summing up the number of alternating subarrays that *end* at each position `i`.
**Time:** O(n), where n is the length of `nums`, because we iterate through the array just once. · **Space:** O(1), as we only use a few variables to store the current state and total count, regardless of the input size.
**Pros:** Optimal time complexity, making it highly efficient for large inputs.; Optimal space complexity, using only a constant amount of extra memory.
**Cons:** May be slightly less intuitive to derive compared to brute-force methods.
### Explanation
We can observe that the number of alternating subarrays ending at index `i` depends on the element at `i-1`. Let `currentLength` be the length of the longest alternating subarray ending at the current index `i`. 
- If `nums[i]` is different from `nums[i-1]`, then `nums[i]` can be appended to all alternating subarrays ending at `i-1`. The length of the new longest alternating subarray ending at `i` will be `currentLength` at `i-1` plus one. 
- If `nums[i]` is the same as `nums[i-1]`, the alternating sequence breaks. The only alternating subarray ending at `i` is `[nums[i]]` itself, so the length is 1.

An alternating subarray of length `k` contains `k` alternating subarrays that end at its last element. For example, `[1,0,1]` (length 3) has three alternating subarrays ending at the final `1`: `[1]`, `[0,1]`, and `[1,0,1]`. Therefore, by tracking the length of the current alternating sequence (`currentLength`), we can add this length to our total count at each step. This allows us to calculate the result in one pass.

```java
class Solution {
    public long countAlternatingSubarrays(int[] nums) {
        long totalCount = 0;
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        
        int currentLength = 0;
        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] != nums[i - 1]) {
                // The alternating sequence continues.
                currentLength++;
            } else {
                // A new alternating sequence starts.
                currentLength = 1;
            }
            // The number of alternating subarrays ending at index i is currentLength.
            totalCount += currentLength;
        }
        
        return totalCount;
    }
}
```
### Algorithm
- Initialize `totalCount = 0` and `currentLength = 0`.
- Iterate through the array `nums` from index `i = 0` to `n-1`.
- At each index `i`, check if it's the first element (`i == 0`) or if `nums[i] != nums[i-1]`.
- If the condition is true, it means the current alternating sequence continues or a new one starts that includes the previous element. We increment `currentLength`.
- If `nums[i] == nums[i-1]`, the alternating sequence is broken. We must start a new one, so we reset `currentLength` to 1.
- The value of `currentLength` represents the number of alternating subarrays that end at the current index `i`. Add this `currentLength` to `totalCount`.
- After the loop finishes, `totalCount` will hold the total number of alternating subarrays.

# Solutions
### Java

```java
class Solution { public long countAlternatingSubarrays ( int [] nums ) { long ans = 1 , s = 1 ; for ( int i = 1 ; i < nums . length ; ++ i ) { s = nums [ i ] != nums [ i - 1 ] ? s + 1 : 1 ; ans += s ; } return ans ; } }
```

### CPP

```cpp
class Solution {
public:
  long long countAlternatingSubarrays(vector<int> &nums) {
    long long ans = 1, s = 1;
    for (int i = 1; i < nums.size(); ++i) {
      s = nums[i] != nums[i - 1] ? s + 1 : 1;
      ans += s;
    }
    return ans;
  }
};

```

### Python

```python
class Solution : def countAlternatingSubarrays ( self , nums : List [ int ]) -> int : ans = s = 1 for a , b in pairwise ( nums ): s = s + 1 if a != b else 1 ans += s return ans
```