Get started

Count Alternating Subarrays — Medium Problem & Solution

A binary subarray is alternating when no two adjacent elements in it are equal. Return the number of alternating subarrays of nums.

Problem statement

A binary subarray is alternating when no two adjacent elements in it are equal.

Return the number of alternating subarrays of nums.

Example 1

Input: nums = [0,1,1,1]
Output: 5
Explanation: The four single elements plus [0,1].

Example 2

Input: nums = [1,0,1,0]
Output: 10
Explanation: Every subarray alternates.

Example 3

Input: nums = [1,1]
Output: 2

Constraints

  • 1 <= nums.length <= 50000
  • nums[i] is 0 or 1

How to solve Count Alternating Subarrays

Let run be the number of alternating subarrays ending at the current index — equivalently the length of the longest alternating run ending there. It either grows by one or resets to one.

Approach

  1. Start with run = 1 and total = 1 for the first element.
  2. For each later index, set run = run + 1 when it differs from its predecessor, otherwise run = 1.
  3. Add run to the total at every step.

Why it works

A subarray ending at i alternates exactly when it lies inside the maximal alternating run ending at i, and there is one such subarray per starting point inside that run — so the count is the run's length. Summing over all right endpoints counts every alternating subarray once, since each has a unique right endpoint.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Forgetting the initial total = 1 for the first element loses one.
  • Resetting run to 0 instead of 1 drops the single-element subarray.
  • The total reaches about 1.25 · 10^9 at the stated size.

Reference solution

Python

from typing import List

def countAlternatingSubarrays(nums: List[int]) -> int:
    total = run = 1
    for i in range(1, len(nums)):
        run = run + 1 if nums[i] != nums[i - 1] else 1
        total += run
    return total

JavaScript

var countAlternatingSubarrays = function(nums) {
    var total = 1, run = 1;
    for (var i = 1; i < nums.length; i++) {
        if (nums[i] !== nums[i - 1]) run++; else run = 1;
        total += run;
    }
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue