Count Alternating Subarrays

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 innums.

Examples

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 <= 10^5
• nums[i] is either 0 or 1.

Solution

Method 1 – Sliding Window 1

Intuition

An alternating subarray is one where no two adjacent elements are the same. We can use a sliding window to find the longest alternating segment starting at each index, and count all possible subarrays within that segment.

Approach

1. Initialize two pointers, l and r, both at 0.
2. For each index l, move r as far as possible such that nums[r] != nums[r-1].
3. For each segment [l, r), the number of alternating subarrays starting at l is r - l.
4. Move l to r and repeat until the end of the array.
5. Return the total count.

Code

C++

class Solution {
public:
    long long countAlternatingSubarrays(vector<int>& nums) {
        long long ans = 0;
        int n = nums.size(), l = 0;
        while (l < n) {
            int r = l + 1;
            while (r < n && nums[r] != nums[r-1]) ++r;
            int len = r - l;
            ans += 1LL * len * (len + 1) / 2;
            l = r;
        }
        return ans;
    }
};

Go

func countAlternatingSubarrays(nums []int) int64 {
    var ans int64
    n := len(nums)
    l := 0
    for l < n {
        r := l + 1
        for r < n && nums[r] != nums[r-1] {
            r++
        }
        length := r - l
        ans += int64(length) * int64(length+1) / 2
        l = r
    }
    return ans
}

Java

class Solution {
    public long countAlternatingSubarrays(int[] nums) {
        long ans = 0;
        int n = nums.length, l = 0;
        while (l < n) {
            int r = l + 1;
            while (r < n && nums[r] != nums[r-1]) ++r;
            int len = r - l;
            ans += 1L * len * (len + 1) / 2;
            l = r;
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun countAlternatingSubarrays(nums: IntArray): Long {
        var ans = 0L
        val n = nums.size
        var l = 0
        while (l < n) {
            var r = l + 1
            while (r < n && nums[r] != nums[r-1]) r++
            val len = r - l
            ans += len.toLong() * (len + 1) / 2
            l = r
        }
        return ans
    }
}

Python

class Solution:
    def countAlternatingSubarrays(self, nums: list[int]) -> int:
        ans = 0
        n = len(nums)
        l = 0
        while l < n:
            r = l + 1
            while r < n and nums[r] != nums[r-1]:
                r += 1
            length = r - l
            ans += length * (length + 1) // 2
            l = r
        return ans

Rust

impl Solution {
    pub fn count_alternating_subarrays(nums: Vec<i32>) -> i64 {
        let n = nums.len();
        let mut ans = 0i64;
        let mut l = 0;
        while l < n {
            let mut r = l + 1;
            while r < n && nums[r] != nums[r-1] {
                r += 1;
            }
            let len = r - l;
            ans += (len as i64) * ((len + 1) as i64) / 2;
            l = r;
        }
        ans
    }
}

TypeScript

class Solution {
    countAlternatingSubarrays(nums: number[]): number {
        let ans = 0;
        const n = nums.length;
        let l = 0;
        while (l < n) {
            let r = l + 1;
            while (r < n && nums[r] !== nums[r-1]) r++;
            const len = r - l;
            ans += len * (len + 1) / 2;
            l = r;
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n), where n is the length of nums, as each element is visited at most twice.
• 🧺 Space complexity: O(1), as only a constant amount of space is used.